A study of the makespan objective considering processing and machine setup times
GEORGETTE KANARACHOU, VRASIDAS LEOPOULOS
Production Engineering Section
National Technical University of Athens,
Polytechnioupolis Zografou, 15780 Athens
GREECE
Abstract: - The flow shop scheduling problem with the objective of minimizing the makespan is a NP-hard problem, thoroughly studied in the last thirty years. However, few investigations are known for the general nonlinear case considering transport, setup and manufacturing times. In this case, a novel solution methodology, consisting of time simulation, providing the ability to represent a real life manufacturing environment, and of a hybrid combinatorial evolution strategy has been proposed lately. Based on this methodology, a study is conducted in this paper for the case of three machines serving an arbitrary number of jobs. The results are compared with theoretical results from the literature.
Key words: - Makespan; Nonlinear manufacturing environment; Time simulation; Hybrid combinatorial evolution strategy
1 Introduction
The flow shop scheduling problem has been studied from a variety of perspectives in the last years. Some recent publications are mentioned [1]-[6]. The proposed solution methodologies depend on the flow shop and production characteristics. The methods are often concentrated on solving large-scale problems where restrictions of linearity, convexity and differentiability prevail.
In the last years the implementation of discrete optimization methods, such as genetic search [7]-[9], branch and bound techniques [10], etc. is observed. Lately, a novel solution approach has been presented, using time simulation and a hybrid combinatorial evolution strategy [11]. Based on this approach the case of three machines serving an arbitrary number of jobs is investigated in this paper. The job characteristics include processing and machine setup times, a case rarely studied in the literature.
In this context we are especially interested on the influence of the setup times on the makespan objective. We are also interested in studying if the structure of the above problem confirms late results reported in [1]. Actually in [1], the proposed fluid synchronization algorithm (FSA) showed for the makespan objective and considering only processing times, a very interesting performance: The results obtained suggest that FSA has a relative error of about 10% for 10 jobs, 1% for 100 jobs and 0.01% for 1000 jobs, which means that large scale problems have a different structure than small scale ones.
In the following, the makespan problem, the hybrid combinatorial evolution strategy and computational results for the 3-machine problems will be presented and discussed.
2 Problem Formulation
The makespan problem consists of a product volume mix of k=1,..,K jobs Jk to be processed through i=1,..,I machines Mi. Each job Jk is characterized by Nk parts. In addition the following restrictions are imposed:
- The schedule is not pre-emptive. That is, once a machine begins processing a stage of a job, it must complete that stage before doing anything else.
- Each machine may work on at most one task at any given time.
- The stages of each job must be completed in order.
The time simulation is performed considering job depended machine setup times Sik and processing times tik for each part of the job Jk on the machine Mi.
Fig. 1 and 2 show for example the time chart for 4 jobs n and three machines considering setup Sik (matrix S) and processing times tik (matrix T):
(1)
Fig. 1 Time chart for S1.
Fig. 2 Time chart for S2.
The makespan objective “μ”, is defined as:
(2)
In (2) Tc denotes the total completion time:
(3)
with Tci equal to the completion time on each machine i and T0 denoting the theoretical (without idle periods) minimum total manufacturing time of all jobs.
(4)
As μ has to be minimized, the following optimization problem hast to be solved:
(5)
In (5) denotes any sequence of the k=1,.., K jobs.
The completion times Tci and the makespan criterion μ for all sequences of the 4 jobs are shown in Fig. 3-6.
Fig. 3. Completion times Tci as a function of all job sequences for S1.
Fig. 4. Makespan criterion m as a function of all job sequences for S1.
Fig. 5 Completion times Tci as a function of all job sequences for S2.
Fig. 6 Makespan criterion m as a function of all job sequences for S2.
3 Optimization Method
For the solution of the optimization problem (5) a combinatorial Evolution Strategy (ES) with deterministic local search is proposed [11]. The method creates “individuals” through a random permutation of the K jobs, corresponding to the evolution strategy with one parent and one offspring. According to this method:
i) An individual a with pr denoting a random permutation of K is generated
(6)
and is computed.
ii) If , a new individual “anew” is generated.
iii) If , the neighborhood of a is searched, generating deterministically m orthogonal local permutations bm of q-jobs.
iv) If , a new a-individual, else a bm individual is generated.
Test results of the above optimization procedure are shown for the case of Fig. 6. From the test results, a rapid convergence of the algorithm to the optimal solution is observed.
Fig. 7 Makespan criterion μ optimized using [11].
4 Numerical Results
4.1 K=7 Jobs on I=3 Machines
The method is applied to the optimization of a flow shop scheduling problem consisting of K=7 jobs on I=3 machines. The processing times tik and the setup times are shown in Fig. 8 and 9.
Fig. 8. Processing times tik.
Fig. 9. Setup times Sik.
The computed makespan μ is shown for two cases (S=0 and S≠0) in Figures 10 and 11.
Fig. 10. Makespan optimization: μmin=111.93, μmax=133.76, Σtik=1104, ΣSik=0.
Fig. 11. Makespan optimization: μmin=111.59, μmax=134.96, Σtik=1104, ΣSik=220.
4.2 K=21 Jobs on I=3 Machines
The method is applied to the optimization of a similar flow shop scheduling problem consisting of K=21 jobs on I=3 machines. The results are shown in Figures 12 and 13.
Fig. 12. Makespan optimization: μmin=109.87, μmax=130.61, Σtik=3312, ΣSik=0.
Fig. 13. Makespan optimization: μmin=110.80, μmax=126.51, Σtik=3972, ΣSik=660.
4.3 K=42 Jobs on I=3 Machines
Fig. 14. Makespan optimization: μmin=109.64, μmax=124.92, Σtik=6624, ΣSik=0.
Fig. 15. Makespan optimization: μmin=110.68, μmax=122.84, Σtik=6624, ΣSik=1320.
The method is applied to the optimization of a similar flow shop scheduling problem consisting of K=42 jobs on I=3 machines. The results are shown in Figures 14 and 15.
4.4 K=84 Jobs on I=3 Machines
Fig. 16. Makespan optimization: μmin=109.57, μmax=121.57, Σtik=13248, ΣSik=0.
Fig. 17. Makespan optimization: μmin=110.63, μmax=120.24, Σtik=13248, ΣSik=2640
The method is applied to the optimization of a similar flow shop scheduling problem consisting of K=84 jobs on I=3 machines. The results are shown in Figures 16 and 17.
4.5 K=168 Jobs on I=3 Machines
Last, the method is applied to the optimization of a similar flow shop scheduling problem consisting of K=168 jobs on I=3 machines. The results are shown in Figures 17 and 18.
Fig. 17. Makespan optimization: μmin=109.54, μmax=119.49, Σtik=26496, ΣSik=0.
Fig. 18. Makespan optimization: μmin=110.60, μmax=117.71, Σtik=26496, ΣSik=5280.
The results are summarized in the following table:
Case / ΣSik=0 / Σtik/ΣSik=0.199μmin / μmax / μmin / μmax
Κ=7 / 111.93 / 133.76 / 111.59 / 134.96
Κ=21 / 109.87 / 130.61 / 110.80 / 126.51
Κ=42 / 109.64 / 124.92 / 110.68 / 122.84
Κ=84 / 109.57 / 121.57 / 110.63 / 120.24
Κ=168 / 109.54 / 119.49 / 110.60 / 117.71
5 Conclusion
Time simulation and a hybrid combinatorial evolution strategy [11] are applied to compute the optimal/near-optimal solutions of a nonlinear model makespan problem, consisting of 7, 21, 42, 84 and 168 jobs on 3 machines with given processing and machine setup times. The results of this computation are very interesting. First, it is shown that with increasing number of jobs K the ratio μmax/μmin decreases, independent of the ratio Σtik/ΣSik. At the same time the convergence rate of the proposed algorithm increases, indicating that small/medium scale problems are more demanding with respect to the optimization method than large scale problems. Thus, the asymptotical convergence of Bertsimas fluid synchronization algorithm to the optimum is confirmed, at least for this model problem. Last, the proposed optimization algorithm showed for all the investigated cases an unproblematic performance.
References:
[1] D. Bertsimas, J. Sheturaman. From fluid relaxations to practical algorithms for job shop scheduling: the makespan objective. Math. Program., Ser. AQ92:61-102 (2002)
[2] Moehring R.H. Scheduling under uncertainty: bounding the makespan distribution. Computational Discrete Mathematics Springer Verlag LNCS 2122 (2001) 79-97
[3] R.H. Ahmadi, H. Matsuo. A mini line approach for pull production. European Journal of Operational Research 125 (2000) 340-358
[4] J.N.D. Gupta, V.R. Neppalli,, F. Werner. Minimizing total flow time in a two-machine flowshop problem with minimum makespan. Int.J. Production Economics 69 (2001) 323-33
[5] J.N.D. Gupta, J.C. Ho. Minimizing makespan subject to minimum flowtime on two identical parallel machines. Computers & Operations Research 28 (2001) 705-717
[6] C.V. Ivanescu, J. CX. Fransoo, J.W.M. Bertrand. Makespan estimation and order acceptance in batch process industries when processing times are uncertain. OR Spectrum 24 (2002) 467-495
[7] W.H. Ip, Y. Li, K.F. Man, K.S.Tang. Multi-product planning and scheduling using genetic algorithm approach. Computers & Industrial Engineering 38 (2000) 283-296
[8] M.P. Fanti, B. Maione, D. Naso, B. Turchiano. Genetic multi-criteria approach to flexible line scheduling. International Journal of Approximate Reasoning 19 (1998) 5-21
[9] N. Dellaert, J. Jeunet, N. Jonard. A genetic algorithm to solve the general multi-level lot sizing problem with time-varying costs. 47Int. J. Production Economics 568 (2000) 241-257
[10] R. M’Hallah, R.L. Bulfin. Minimizaing the weighted number of tardy jobs on a single machine. European Journal of Operational Research 145 (2003) 45-56
[11] G. Kanarachou, V. Leopoulos. Flow shop scheduling using hybrid combinatorial evolutionary optimization. Subjected for publication in the 3rd WSEAS Int. Conf. on Simulation, Modeling and Optimization (ICOSMO 2003), Greece