Abstract: In this study, consider three general flowshop scheduling problems: (1) with the objective function of the total weighted tardiness and the assumption of having ready times for jobs, (2) with the objective function of the makespan and the constraints of time lags and (3) with the makespan as objective and the constraints of the Sequence Dependent Setup Times (SDST). We present a Mixed Integer Linear Programming (MILP) model for each of them. The modeling formulations of this paper can generate the non-permutation schedules and cover the missing operations assumption. The implementation of the proposed formulations is demonstrated using some numerical examples.
INTRODUCTION
There are many mathematical formulations for modeling the flowshop scheduling problem in the literature (Stafford et al., 2002, 2005; Rios-Mercado and Bard, 2003). But these models generate only the permutation schedules. One reason is that in a m-machine n-job non-permutation flowshop scheduling problem, the total number of feasible schedules tends to (n!)m and in the permutation case, the number of feasible solutions is reduced to n! (Pugazhendhi et al., 2002), since in the problem under the permutation assumption, the sequence of jobs on all machines are the same. Therefore, modeling and solving the non-permutation problems are much more difficult. Another reason is that there is little improvement made by non-permutation schedules over permutation schedules with respect to completion-time based criteria. But the improvement is significant with respect to some special constraints such as SDST, missing operations of jobs, time lags and so on, or due-date based criteria like maximum tardiness or total weighted tardiness (Liao et al., 2006). However, there is a lack of mathematical programming models for the non-permutation flowshop scheduling problem with these assumptions and objectives in the literature.
An important assumption in the flowshop scheduling problem which is seen in many of the real problems is the missing operations of jobs which allow the jobs to pass some machines with any processing. Pugazhendhi and Rajendran have done extensive researches on this kind of problem and presented several heuristics and meta-heuristics for solving the problem with some objectives separately, for example see (Pugazhendhi et al., 2002; Rajendran and Ziegler, 2001). But there is not any mathematical formulation to model the problem. Although, it can use the regular flowshop scheduling models for this type of problem by setting the processing time of missing operations to zero, but they do not have the desired performance with respect to the objective function value, because of the specific type of this problem which would be described later. Therefore, the missing operations assumption is highlighted in this paper and its proposed models.
In this study, consider three non-permutation flowshop scheduling problems: (1) with the objective function of the total weighted tardiness and the jobs having ready times, (2) with the objective function of the makespan and the constraints of the start-start and stop-start time lags (Fondrevelle et al., 2006), (3) with the objective function of the makespan and the constraints of SDST. These problems are very applicable in the real world and usually denoted as F/ri/ΣwiTi, F/tl/Cmax, F/STsd/Cmax, respectively (Allahverdi et al., 2008). Here, present a MILP model for each problem. The modeling formulations of this paper can generate the non-permutation schedules and cover the missing operations assumption. They are also linear models and linearity may lead to lower complexity and higher performance. Finally, the conclusion remarks of this study are presented at the end to summarize the contribution of the study.
General notations used throughout the study are:
| I | : | The No. of jobs |
| K | : | The No. of machines |
| i | : | Denotes i`th job, i = 1,...,I |
| k | : | Denotes k`th machine, k = 1,...,K |
| Tik | : | The processing time of job i on machine k, |
| xijk | : | Binary variable taking value 1 if i`th job on k`th machine is processed in j`th order and 0 otherwise. If tik = 0, then the operation really does not exist. However, a rank is given. |
| qijk | : | The completion time of job i on machine k if it is processed in j`th order. |
PROBLEM 1
In this problem, the objective is to minimize the total weighted tardiness. It assume that the jobs may reach to the shop after the time zero. Let ri, di and qi be the ready time, the due date and the completion time (i.e. the completion time of the final operation of job i on the last machine) of job i, respectively, then the tardiness of job i is denoted as Di, Di = max (0, qi!di). The proposed MILP model is as follows. M is an upper bound of the makespan (It has not to be tight and can be set to the sum of all processing times).
Subject to:
(1) |
(2) |
(3) |
(4) |
(5) |
(6) |
(7) |
(8) |
(9) |
Note that the sum
Numerical example: Let us consider, the following instance of a 5-machine, 4-job problem:
To compare the best solution with the best permutation solution of the problem, Here, first present the optimal permutation solution of the above test problem which is shown in Fig. 1. The objective value of this solution is equal to 66.
To understand the role of considering the missing operations assumption in improving the objective value, we also solve the problem 1 model without considering this assumption, i.e., the constraint set 2 changes as follows:
The optimal solution of this model is shown in Fig. 2. In this solution, the objective value is equal to 60 and for two missing operations, i.e., (1, 2) and (4, 1), we have q122 = 9 and q441 = 9.
| Fig. 1: | The optimal permutation solution of the example of problem 1 |
| Fig. 2: | The optimal solution of the example of problem 1 without considering the missing operations assumption |
| Fig. 3: | The optimal solution of the example of problem 1 |
The optimal solution of the test problem is shown in Fig. 3 where, the objective value of this solution is equal to 58.
In the above optimal solution reported by a solver, q122 is equal to 9. Because the constraint set 2 of the model does not affect the missing operation (1, 2) and so the completion time of this operation is determined based on the other constraints. In this example, the optimal solution is a non-permutation schedule.
PROBLEM 2
In this problem, it is assumed that there are given time lags. These time lags are the waiting times between two consecutive operations of the same job. Here, assumes that the gap between the starting time of i`th job on k`th machine and its starting time on (k+1)`th machine (start-start time lag) must be greater or equal to ai(k+1) and the gap between the finishing time of i`th job on k`th machine and its starting time on (k+1)`th machine (stop-start time lag) must be greater or equal to bi(k+1). Therefore, if job i starts on machine k at (qijk!tik) then it can start on machine k+1 at (qij`(k+1)!ti(k+1)) such that,
and similarly,
The MILP model of this problem is as follows. y is the makespan, i.e., the largest completion time.
min z = y
subject to:
(10) |
(11) |
(12) |
(13) |
(14) |
And the constraints 2, 5 to 7 and 9 of the problem 1 model are added to the above constraints with no changes. Constraint set 10 affects the objective function. Note that the makespan may be not achieved on machine I because of missing operations on this machine. Hence these constraints involve all machines. Constraint (11) affects the completion time of the first operation on machine 1. The constraint sets 12 and 13 are related to the start-start and stop-start time lags described above. The constraint set 14 is the same as the constraint set 1 in the model of the first problem.
Numerical example: Consider a 5-machine 4-job test problem one more time where the values of processing times are the same as those of the example of problem 1 and the parameter values for the start-start and stop-start time lags constraints are as follows:
|
|
If we have ai(k+1) > 0 (or bi(k+1) > 0) and tik = 0 or ti(k+1) = 0, then this processing time of zero does not mean a missing operation, i.e., the operation really exists, but its processing time is very little and near to zero.
The optimal solution of the test problem is shown in Fig. 4.
And the optimal permutation schedule of the test problem is shown in Fig. 5.
| Fig. 4: | The optimal solution of the example of problem 2 |
| Fig. 5: | The optimal permutation solution of the example of problem 2 |
PROBLEM 3
Here, it consider the case of SDST where the objective is to minimize the makespan. Let sii`k be the setup time between two consecutive jobs i, i` on machine k. Therefore, the proposed model is formulated as follows:
min z = y
subject to:
(15) |
(16) |
(17) |
(18) |
(19) |
(20) |
(21) |
(22) |
(23) |
And the constraints 5 to 7 and 9 of the problem 1 model are added to the above constraints with no changes. y is the makespan, i.e., the largest completion time. The constraint set 15 is related to the makespan. The constraint 16 insures that the first job on the first machine does not start earlier than the time zero. The constraint sets 17 and 18 insure that a job does not start on a machine until it has finished processing on the previous machine and its predecessor has completed processing on that machine and, that machine has set up for processing the job. The constraint sets 19 to 22 are added to the model for converting the nonlinear expressions to linear (Schrijver, 1998).
| Fig. 6: | The optimal solution of the example of problem 3 |
Numerical example: Here, consider a 3-machine 3-job example with the following data.
And all other sii`k variables are equal to zero.
The optimal solution of this test problem is shown in Fig. 6.
CONCLUSION
In this study, it is presented some MILP models for some general flowshop scheduling problems. The proposed models of this paper can generate the non-permutation schedules and cover the missing operations assumption which can be found in many real world problems. The implementation of the proposed models on some numerical examples has shown that the proposed models could present better solutions compared with the optimal permutation solutions and even compared with the optimal non-permutation solutions which are obtained from the proposed models without considering the missing operations assumption.