Production and manufacturing are two of the most important problems in real industries which is attendant more researches. Generally, the literature of manufacturing could be divided to two separate sub-groups which are qualitative and computational approaches. In qualitative approaches, firstly the effective factors on the performance of manufacturing are determined and then it is attempt to control them. On the other hand, computational efforts use the modeling procedure to describe the manufacturing environment and present some methods so as to solve the constructive models.
Feylizadeh and Bagherpour (2011) accomplished a comprehensive
review related to the application of optimization techniques in production problems
involving single machine scheduling.
Hemamalini et al. (2010) proposed a deep memory
greedy search so as to solve the problem of minimizing makespan in a job shop
Khurana et al. (2011) studied the effective
factors on the performance of a supply chain and presented an AHP approach to
analyze and compare the identified factors. Their factors could be categorized
in six separate groups involving managerial, organizational, technological,
individual, financial, social and cultural.
Iwarere and Lawal (2011) studied a case study related
to maintenance of public facilities in Nigeria. They stated that government,
management and employees are the main effective factors on the performance of
Hammoud et al. (2011) presented a genetic model
and an intelligent agent based system for analyzing the machine learning effect.
Rajarathinam and Parmar (2011) studied the using of
parametric and nonparametric regression models to identify the effective factors
on the production.
Nja and Udofia (2009) proposed a mixed integer goal
programming approach for flour producing companies and presented an applicable
example for a facility with three products. They also claimed that their model
is cost effective and could be used in any factory or facility.
Taleizadeh et al. (2008) developed a new version
of newspapers boy in which the assumptions of multiple products and multiple
constraints were considered simultaneously. Furthermore, the orders were considered
and some batches and sent to their customers. In order to solve the proposed
model, they modified a genetic algorithm which its results were very effective.
Mahdavi and Shirazi (2010) reviewed the application
of decision support systems to improve the performance of flexible manufacturing
This research studied the problem of single machine batch scheduling which depicts a two staged supply chain scheme and contains a manufacturer and a number of customers in which each job may be transmitted to its customer right after its completion or be held to batch with more jobs. Batching the jobs not only may cause the job process to accelerate, but also could decrease the delivery cost of job transmission to their customers.
Mazdeh et al. (2011a) mentioned that the problems
that combines a scheduling function with delivery costs are rather complex and
solving them by simple optimization methods is not commercial.
The literature of single machine batch scheduling can be classified by variant
concepts. For example, based on how the batches are processed on the machine,
the problem would contain serial or parallel batching categories. In serial
batching, it is assumed that each batch is processed based on all the processing
time of its jobs and the processing time of batch is equal to the completion
time of last job assigned to it. Ng et al. (2002)
studied the problem of single machine serial batch scheduling to minimize maximum
lateness by considering the precedence constraints between the batches and presented
an o(n2) polynomial time algorithm. Ng et
al. (2003) also investigated the same problem by total completion time
objective, release date and precedence constraints and presented an o(n5)
Lu and Yuan (2007) considered the serial batch scheduling
when each batch contained exactly k jobs and the objective was to minimize the
total weighted completion time. They showed that the problem is NP-hard and
proposed a polynomial algorithm with some simplified rules.
The other researches in the field of serial batching could be mentioned as:
An o(n log n) algorithm for minimizing total completion time by Coffman
et al. (1990), an o(n2) algorithm for minimizing total
weighted completion time with precedence constraint by Albers
and Bruker (1993) and an o(n14) algorithm for minimizing total
completion time by Baptiste (2000). On the other hand,
the processing time of a parallel batch is calculated by the maximum processing
time of jobs that are apparent to that batch. Nong et
al. (2008) investigated the problem of single machine parallel batching
to minimize makespan by considering family setups and release date. They developed
a polynomial approximation scheme for their problem by some simplifications
the model that yielded an algorithm with worst case ratio of 2.5.
Potts and kovalyov (2000) accomplished an extensive
review in the field of parallel batching literature and gave details of basic
In recent years, researchers have considered the delivery cost as a secondary
objective called combined optimization batch delivery problem. Mazdeh
et al. (2011a, b) studied the problem of
minimizing the number of weighted tardy jobs by considering delivery cost and
used a simulation annealing approach to solve the problem. Tian
et al. (2007) investigated the problem of minimizing the sum of total
weighted flow times with delivery cost. They indicated that the problem is NP-hard
and proposed an optimal algorithm. Mazdeh et al.
(2011b) proposed a branch and bound approach to solve the problem of minimizing
the weighted sum of flow times with delivery cost. Another research related
to Mazdeh et al. (2007) presented a branch and
bound to minimize flow time and delivery cost simultaneously.
One of the most important problems considered in scheduling problem is job deterioration, where there are wide applications in many real-world situations. Deterioration means that the processing time of jobs increases over time.
Browne and Yechiali (1990) introduced a job deterioration
scheduling problem in which the processing time of a job was a function of its
starting time. Mosheiov (1994), who was the first to
apply simple linear deteriorating for single machine scheduling problem, considered
this problem to minimize the makespan, total completion time, total weighted
completion time, total weighted waiting time and total tardiness, number of
tardy jobs, maximum lateness and maximum tardiness.
Wu et al. (2009) solved a single-machine problem
by a branch-and-bound scheme and two heuristic algorithms to minimize the makespan.
Wang et al. (2009) solved the single machine
scheduling problems with learning effect and deteriorating jobs simultaneously
to minimize the total weighted completion time and the maximum lateness. Wang
and Wang (2010) considered a single machine scheduling problem with deteriorating
jobs in which the processing time of a job was defined as a simple linear function
of its starting time to minimize the total weighted earliness penalty subject
to no tardy jobs. Husang et al. (2010) considered
a single machine scheduling problem with deteriorating jobs by a linear function
of time to minimize the total weighted earliness penalty subject to no tardy
jobs. Ji and Cheng (2010) proposed a single machine
scheduling problem in which the jobs were processed in batches and the processing
time of each job was a simple linear function of its waiting time to minimize
the makespan. Al-Anzi et al. (2007) studied the
combination of deteriorating and scheduling objectives with application in computer
communication and reverse logistics.
In this study we propose a mathematical model for the issue of serial batch scheduling problem, where the objective is to minimize the total tardiness and delivery costs and maximizing the job values in makespan simultaneously that based on our knowledge, is less considered in the literature.
Afterwards, a simulation annealing approach is used to get to near optimal
solutions. In order to check the verification of SA, some data sets of problem
are solved optimally using Lingo software and the results are compared with
each other. For larger scales of problem, a lower bound is also generated and
the comparison accomplished based on it.
Consider there is a machine that processes in jobs with no preemption and all of the jobs are available for processing at time zero. The completed jobs can be delivered to the customer immediately after completion or be awaited next jobs to be delivered as a batch. According to number of jobs, N batches are considered and the jobs are assigned to the batches. Clearly any batch that does not have any jobs will be omitted and then the sequence of batches is determined so that the proposed objective function is minimized. As mentioned, the serial batching assumption is considered in this paper, therefore, the processing time of each batch is calculated as sum of the all processing jobs located on it and the due date of batch is the maximum value of due date of jobs which are assigned to it.
The decision variables and parameters of the problem are listed below:
||Number of jobs ready to be scheduled
||The normal processing time of job I
||The due date of ith job
||The priority of job I
||The processing time of batch k
||The due date of batch k
||The priority of batch k
||Number of jobs assigned to batch k
||The tardiness of job where scheduled on jth position
||The completion time of job where scheduled on jth position
||The rate of deterioration
||The decreasing rate of job value
||The value of shipping cost of batch k
||If job I is assigned to batch k
||If batch k is located in jth position in the sequence
||If there is at least one job assigned to batch k
and the proposed model is presented as follows:
Equation 1 introduces the objective function where the first
term corresponds to the delivery cost, the second term corresponds to the sum
of tardiness and the third term is related to the sum of job values in makespan.
Constraint (2) states that the completion time of each batch is equal to the
completion time of prior batches plus the sum of processing times of jobs assigned
to it. Constraint (3) mentions that the machine and all the jobs are available
at time zero. Constraint (4) declares that the completion time of each batch
is equal to the sum of processing times of jobs assigned to it. Constraint (5)
determines how many jobs are located on each batch. Constraint (6) states that
whether batch k is empty or not. Constraint (7) clarifies that the tardiness
of each batch is equal to the gap between the time that the processing of that
batch has been completed and its due date. Clearly, the value of tardiness must
be positive. Equation 8 shows how the due date of each batch
is calculated and Eq. 9 demonstrates how the order of each
batch is considered. Constraint (10) is related to the precedence constraint.
Constraint (11) states that each batch is processed only once at each sequence
and constraint (12) determines each position can be assigned to just one batch.
Constraint (13) mentions if a job can be assigned to exactly one batch to be
processed and constraint (14), (15) shows that x and y are binary variables.
As mentioned, the considered problem is NP-hard; hence it is not reasonable to use ordinary optimization methods. In this case, a simulation annealing meta- heuristic (SA) is implicated to reach the near optimal solutions in suitable run times.
SA that have been applied widely to solve many combinatorial optimization problems
is a class of optimization Meta heuristics and performs a stochastic neighborhood
search through the solution space. It is proved that SA can be considered as
a marcov chain (Van-Laarhoven and Aarts, 1988), so its
sensitivity to the initial solution is much less than the other meta-heuristics
and has a great ability to avoid getting in local optimum solutions.
In this study, the algorithm starts from an initial temperature termed as T0 in which, two random strings are generated as below.
The first string corresponds to assigning the jobs to batches and another is related to find a suitable scheduling of generated batches.
Based on this fact, consider there are five available jobs for processing on the machine. The first string shows that the first and the second jobs are assigned to batch 2, the third job is located on batch 1 and forth and fifth jobs are assigned to batches 3 and 4, respectively. Since, number 5 is not mentioned in this string, therefore, the fifth batch is remained empty and will be removed.
Afterwards, in second string, a random schedule of all the batches that contain at least one job is generated.
This procedure continues while the equilibrium condition in this temperature to be occurred. In this problem, the equilibrium condition is occurred when the gaps between proposed objective functions in consecutive iterations in a certain temperature, are as less as possible. This condition can be demonstrated by:
where, Z[i+1] is the value of objective function in I+1th iteration of algorithm, j is the number of objectives that are considered to calculate the total gap and ε is a very small number.
|| The coding scheme of proposed SA
|| The Taguchi experiment inputs
|| The pseudo-code of proposed SA
By reaching the equilibrium in the temperature, the temperature is decreased and the procedure starts from the lower temperature and continues until the next equilibrium.
Neighborhood search is also implemented by swapping two randomly selected positions
in the second string (batch string) in order to meet other nodes of solution
space (Fig. 1).
The performance of the proposed SA is depicted in Fig. 2.
In order to calibrate the proposed SA, a Taguchi approach is presented in which attempts to identify controllable factors (control factors) that minimize the effect of the noise factors. During the experimentation, the noise factors are manipulated to force variability to occur and then to finding the optimal control factor settings that make the process or product robust, or resistant to variations from the noise factors.
In this study, the S/N ratio which is considered as nominal, is the best of the kind and is calculated by the following equation:
The effective factors and their levels are also described in Table 1.
The associated degree of freedom for these two factors is equal to 8. According to Taguchi standard table of orthogonal array, the L9 which fulfils all the minimum necessary requirements should be selected.
In order to analysis the Taguchi outputs, three important measures are considered as the S/N ratio (as robust measure), the average responses for each combination of control factor and the variability in the response due to the noise (standard deviation).
The results are depicted in Fig. 3-5. A
measure of robustness is used to identify control factors that reduce variability
in a product or process by minimizing the effects of uncontrollable factors.
Figure 3 indicates the robustness of each combination of factors.
|| The results for response based on S/N ratio
|| The results for response based on means
|| The results for response based on standard deviations
Clearly, it is desired to select a pair of factors that generate the maximum
robustness. Therefore, based on this, Fig. 3a and 2b
Figure 4 shows the average responses for each combination of control factors. Since, the objective of the function is minimization, the minimum value for this measure is desired, so 2a and 3b are selected.
Finally, Fig. 5 shows the variability in the response due to the noise that is desired to be minimal, hence, 3a and 2b are selected. Based on the mentioned measures, the most efficient combination of the proposed factors are 3a and 2b which better satisfies the response values.
All the instances for this problem are coded by visual basic 6 and are run on personal computer with CORE I 7 processor and 4 GB of RAM. The required data were generated randomly based on below scheme:
||Processing time of jobs from uniform distribution [1-100]
||Due date of jobs from uniform distribution [1-αΣP] where α
is considered equal to 0.2 manually
The instances are also solved using Lingo 10 software to determine the efficiency
and capability of proposed SA to reach the global optimum.
To make the sensitivity analyze, some important factors including problem dimension (number of considered batches), rate of deterioration and decreasing rate of job values are considered.
Sensitivity analysis based on the problem dimension: In order to implement this analysis first, some instances with small dimensions are considered and the results are compared to equivalent Lingo results. But Lingo is incapable of solving the problem for jobs greater than 5 because of immense complexity of problem. Therefore, a lower bound is generated in order to examine the SA performance for larger scales of problem. Rate of deterioration and rate of job values are also considered as 0.2 and 0.002, respectively.
Table 2 depicts the comparison of the results of SA and Lingo
based on the problem dimension. Where, the second column indicates the number
of batches (jobs) and the third and forth columns show the performance of Lingo
software including VOF (Value of Objective Function) and its run time in seconds.
For each instance, the SA was run 5 times and the best obtained solution was considered as the VOF which has been recorded in column 5.
The gap of results between SA and global optimum is calculated by:
Figure 6 and 7 depict the comparison of
the results and run times, respectively.
Based on Table 2 and depicted figures, the run time of SA and Lingo increases with greater dimensions of problem and the run time of Lingo increases exponentially. For small dimensions of problem, the SA performs very efficient and offers the solutions with low error in a reasonable time.
In order to examine the capability of proposed SA in this field, a lower bound is generated.
|| Sensitivity analyze based on small problem dimension
|| The VOF sensitivity analysis based on small problem dimensions
|| The run time sensitivity analysis based on small problem
Theorem 1: Removing the deterioration yields a lower bound for the objective function of earliness and tardiness problems.
Proof: C1 and C2 are considered as the completion
time of job with and without the deterioration, respectively. L1
and L2 are also considered as the lateness value of job with and
without the deterioration.
|| Sensitivity analyze based on medium and large problem dimension
|| Sensitivity analysis based on rate of deterioration for N
It is obvious that c2 ≤ c1. We must show that L2
≤ L1. The proof is straightforward since:
Table 3 presents the performance of proposed SA against the generated lower bound.
Sensitivity analysis based on the rate of deterioration: The effect of deterioration is evaluated by dimension of 4 jobs and value of 0.002 for the rate of job values. Table 4 illustrates the results of SA and lingo for several rates of deterioration.
According to depicted plots, the rate of deterioration is highly effective on the performance of Lingo and alters its run time clearly. But for SA it does not seem to have any sensitivity to rate of deterioration in the field of run time.
On the other hand, more rates increases the value of objective function in both of the global optimum and SA solution.
For larger number of jobs, the results are shown in Table 5.
Based on presented Fig. 8 and 9, more rate
of deterioration causes the objective function value to increase, but does not
affect the run time.
Sensitivity analysis based on the rate of job values: The effect of rate of job values is evaluated by dimension of 4 jobs and value of 0.2 for rate of deterioration. Table 6 illustrates the results of SA and Lingo for several rates of job values.
|| Sensitivity analyze based on rate of deterioration for N
|| Sensitivity analysis based on rate of job values for N =
|| The VOF sensitivity analysis based on rate of deterioration
for N = 4
According to Fig. 10 and 11, although the rate of job values does not seem an effective factor in field of objective function, but alters the run time clearly especially in the Lingo performance.
For larger number of jobs, the results are shown in Table 7.
Based on Table 7, the rate of job values does not show clear sensitivity in both fields of run time and objective function for large number of jobs.
|| Sensitivity analysis based on rate of deterioration for N
|| The run time sensitivity analysis based on rate of deterioration
for N = 4
|| The VOF sensitivity analysis based on rate of job values
for N = 4
This research studied the problem of single machine batch scheduling with the
objective of minimizing the total tardiness and delivery costs and maximizing
the job values in makespan simultaneously, in which a mathematical model was
presented. The jobs were also considered deteriorated that their processing
times were dependent on the sequence in which the process was accomplished and
some precedence constraints were considered between the jobs.
|| The run time sensitivity analysis based on rate of job values
for N = 4
In order to solve the proposed model, a calibrated simulation annealing was
used and its performance was compared to global optimum for small dimensions
of problem. In addition, a lower bound was generated in order to examine the
performance of SA for larger scales of problem.
Afterwards, a number of sensitivity analyses were implemented, based on effective factors of the problem, including problem dimension, rate of deterioration and decreasing rate of job values.
For future research, the solution method can be considered as the hybrid of meta-heuristics that may perform more powerfully than a single meta-heuristic.
On the other hand in batching phase, some clustering rules and algorithms can be used as suitable tools in order to assign the jobs to the batches.