IJE TRANSACTIONS C: Aspects Vol. 27, No. 6 (June 2014) 899-910   

downloaded Downloaded: 143   viewed Viewed: 2068

E. Ghafari and R. Sahraeian
( Received: April 30, 2013 – Accepted in Revised Form: December 12, 2013 )

Abstract    In this paper the problem of serial batch scheduling in a two-stage hybrid flow shop environment with minimizing Makesapn is investigated. In serial batching it is assumed that jobs in a batch are processed serially, and their completion time is defined to be equal to the finishing time of the last job in the batch. The analysis and implementation of the prohibited transference of jobs among the machines of stage one in serial batch is the main contribution of this research. Machine set-up and released time for all jobs are assumed to be zero and no Preemption is allowed. Machines may not breakdown but at times they may be idle. As the problem is NP-hard, a simulated annealing (SA) is developed to give near optimal solutions. Since this problem has also not been studied previously, therefore, a lower bound is developed for evaluating the performance of the proposed SA. Many test problems have been solved using SA and results compared with lower bound. Results showed SA can provide a good near optimal solution for small, median and large size problems in reasonable time.


Keywords    Scheduling, Hybrid Flowshop, Serial Batching, Simulated Annealing, Taguchi Method


چکیده    در این مقاله مسأله زمان‏بندی دسته‏ای سری، در محیط کارگاهی ترکیبی و دو مرحله‏ای به منظور حداقل کردن زمان کل انجام کار، بررسی می‏شود. فرض بر این است که پردازش کارها در یک دسته به صورت سری است و زمان تکمیل آن دسته برابر با زمان پایان آخرین کار در آن دسته است. نوآوری اصلی این تحقیق، تحلیل و اجرای ممنوعیت جابجایی کارهای میان ماشین‏های مرحله اوّل است. فرض می‏شود که زمان آماده‏سازی ماشین‏ها و زمان آماده کار بودن کارها، صفر است و انقطاع کار نیز مجاز نیست. احتمال توقف ماشین‏ها صفر است اما احتمال بیکاری در برخی اوقات وجود دارد. چون پیچیدگی مسأله بالاست (NP-hard)، به منظور رسیدن به جواب نزدیک به بهینه، از روش شبیه سازی تبرید استفاده می‏شود. همچنین، چون این مسأله قبلا مطالعه نشده است، لذا برای ارزیابی عملکرد روش حل SA پیشنهادی، یک کران پایین ارائه می‏شود. چندین مسأله نمونه با روش شبیه سازی تبرید حل و نتایج آن با کران پایین مقایسه می‏شود. نتایج به دست آمده نشان می‏دهد که روش شبیه سازی تبرید می‏تواند برای مسائل کوچک، متوسط و بزرگ، یک جواب نزدیک به جواب بهینه خوب ارائه کند.



1.     Ribas, I., Leisten, R. and Framiñan, J.M., "Review and classification of hybrid flow shop scheduling problems from a production system and a solutions procedure perspective", Computers & Operations Research,  Vol. 37, No. 8, (2010), 1439-1454.

2.     Botta-Genoulaz, V., "Hybrid flow shop scheduling with precedence constraints and time lags to minimize maximum lateness", International Journal of Production Economics,  Vol. 64, No. 1, (2000), 101-111.

3.     Sawik, T., "Mixed integer programming for scheduling flexible flow lines with limited intermediate buffers", Mathematical and Computer Modelling,  Vol. 31, No. 13, (2000), 39-52.

4.     Riane, F., Artiba, A. and Iassinovski, S., "An integrated production planning and scheduling system for hybrid flowshop organizations", International Journal of Production Economics,  Vol. 74, No. 1, (2001), 33-48.

5.     Gupta, J.N., Krüger, K., Lauff, V., Werner, F. and Sotskov, Y.N., "Heuristics for hybrid flow shops with controllable processing times and assignable due dates", Computers & Operations Research,  Vol. 29, No. 10, (2002), 1417-1439.

6.     Oğuz, C., Fikret Ercan, M., Edwin Cheng, T. and Fung, Y.-F., "Heuristic algorithms for multiprocessor task scheduling in a two-stage hybrid flow-shop", European Journal of Operational Research,  Vol. 149, No. 2, (2003), 390-403.

7.     Engin, O. and Döyen, A., "A new approach to solve hybrid flow shop scheduling problems by artificial immune system", Future Generation Computer Systems,  Vol. 20, No. 6, (2004), 1083-1095.

8.     Oğuz, C., Zinder, Y., Ha Do, V., Janiak, A. and Lichtenstein, M., "Hybrid flow-shop scheduling problems with multiprocessor task systems", European Journal of Operational Research,  Vol. 152, No. 1, (2004), 115-131.

9.     Morita, H. and Shio, N., "Hybrid branch and bound method with genetic algorithm for flexible flowshop scheduling problem", JSME International Journal Series C,  Vol. 48, No., (2005), 46-52.

10.   Tang, L. and Zhang, Y., Heuristic combined artificial neural networks to schedule hybrid flow shop with sequence dependent setup times, in Advances in neural networks–isnn, Springer (2005), 788-793.

11.   Ruiz, R. and Maroto, C., "A genetic algorithm for hybrid flowshops with sequence dependent setup times and machine eligibility", European Journal of Operational Research,  Vol. 169, No. 3, (2006), 781-800.

12.   Tang, L.-x. and Xuan, H., "Lagrangian relaxation algorithms for real-time hybrid flowshop scheduling with finite intermediate buffers", Journal of the Operational Research Society,  Vol. 57, No. 3, (2006), 316-324.

13.   Zandieh, M., Fatemi Ghomi, S. and Moattar Husseini, S., "An immune algorithm approach to hybrid flow shops scheduling with sequence-dependent setup times", Applied Mathematics and Computation,  Vol. 180, No. 1, (2006), 111-127.

14.   Voss, S. and Witt, A., "Hybrid flow shop scheduling as a multi-mode multi-project scheduling problem with batching requirements: A real-world application", International Journal of Production Economics,  Vol. 105, No. 2, (2007), 445-458.

15.   Chen, C.-L. and Chen, C.-L., "A bottleneck-based heuristic for minimizing makespan in a flexible flow line with unrelated parallel machines", Computers & Operations Research,  Vol. 36, No. 11, (2009), 3073-3081.

16.   Figielska, E., "A genetic algorithm and a simulated annealing algorithm combined with column generation technique for solving the problem of scheduling in the hybrid flowshop with additional resources", Computers & Industrial Engineering,  Vol. 56, No. 1, (2009), 142-151.

17.   Naderi, B., Zandieh, M., Khaleghi Ghoshe Balagh, A. and Roshanaei, V., "An improved simulated annealing for hybrid flowshops with sequence-dependent setup and transportation times to minimize total completion time and total tardiness", Expert Systems with Applications,  Vol. 36, No. 6, (2009), 9625-9633.

18.   Jabbarizadeh, F., Zandieh, M. and Talebi, D., "Hybrid flexible flowshops with sequence-dependent setup times and machine availability constraints", Computers & Industrial Engineering,  Vol. 57, No. 3, (2009), 949-957.

19.   Behnamian, J. and Fatemi Ghomi, S., "Hybrid flowshop scheduling with machine and resource-dependent processing times", Applied Mathematical Modelling,  Vol. 35, No. 3, (2011), 1107-1123.

20.   Sawik, T., "An exact approach for batch scheduling in flexible flow lines with limited intermediate buffers", Mathematical and Computer Modelling,  Vol. 36, No. 4, (2002), 461-471.

21.   Yuan, J., Liu, Z., Ng, C. and Cheng, T.E., "The unbounded single machine parallel batch scheduling problem with family jobs and release dates to minimize makespan", Theoretical Computer Science,  Vol. 320, No. 2, (2004), 199-212.

22.   Li, W. and Yuan, J., "Single machine parallel batch scheduling problem with release dates and three hierarchical criteria to minimize makespan, machine occupation time and stocking cost", International Journal of Production Economics,  Vol. 102, No. 1, (2006), 143-148.







23.   Kashan, A.H., Karimi, B. and Jenabi, M., "A hybrid genetic heuristic for scheduling parallel batch processing machines with arbitrary job sizes", Computers & Operations Research,  Vol. 35, No. 4, (2008), 1084-1098.

24.   Nong, Q., Yuan, J., Fu, R., Lin, L. and Tian, J., "The single-machine parallel-batching on-line scheduling problem with family jobs to minimize makespan", International Journal of Production Economics,  Vol. 111, No. 2, (2008), 435-440.

25.   Bellanger, A. and Oulamara, A., "Scheduling hybrid flowshop with parallel batching machines and compatibilities", Computers & Operations Research,  Vol. 36, No. 6, (2009), 1982-1992.

26.   Gupta, J.N., "Two-stage, hybrid flowshop scheduling problem", Journal of the Operational Research Society,  Vol. 39, No. 4, (1988), 359-364.

27.   Hoogeveen, J., Lenstra, J. and Veltman, B., "Minimizing makespan in a multiprocessor flowshop is strongly np-hard", European Journal of Operational Research,  Vol. 89, No. 1, (1996), 172-175.

28.   Garey, M.R. and Johnson, D.S., "``strong''np-completeness results: Motivation, examples, and implications", Journal of the ACM (JACM),  Vol. 25, No. 3, (1978), 499-508.

29.   Haouari, M., Gharbi, A. and Jemmali, M., "Tight bounds for the identical parallel machine scheduling problem", International Transactions in Operational Research,  Vol. 13, No. 6, (2006), 529-548.

30.   Kolonko, M., "Some new results on simulated annealing applied to the job shop scheduling problem", European Journal of Operational Research,  Vol. 113, No. 1, (1999), 123-136.

31.   Kurz, M.E. and Askin, R.G., "Scheduling flexible flow lines with sequence-dependent setup times", European Journal of Operational Research,  Vol. 159, No. 1, (2004), 66-82.

32.   Norman, B.A. and Bean, J.C., "A genetic algorithm methodology for complex scheduling problems", Naval Research Logistics,  Vol. 46, No. 2, (1999), 199-211.

33.   Nawaz, M., Enscore Jr, E.E. and Ham, I., "A heuristic algorithm for the m-machine, n-job flow-shop sequencing problem", Omega,  Vol. 11, No. 1, (1983), 91-95.

34.   Wang, L. and Zheng, D.-Z., "An effective hybrid optimization strategy for job-shop scheduling problems", Computers & Operations Research,  Vol. 28, No. 6, (2001), 585-596.

35.   Lundy, M. and Mees, A., "Convergence of an annealing algorithm", Mathematical programming,  Vol. 34, No. 1, (1986), 111-124.

36.   Haupt, R.L. and Haupt, S.E., "Practical genetic algorithms, John Wiley & Sons,  (2004).

37.   Cochran, W.G. and Cox, G.M., "Experimental designs", (1957).

38.   Bement, T.R., "Taguchi techniques for quality engineering", Technometrics,  Vol. 31, No. 2, (1989), 253-255.

39.   Phadke, M.S., "Quality engineering using robust design, prentice hall", Englewood Cliffs, NJ, (1989).

40.   Al-Aomar, R., "Incorporating robustness into genetic algorithm search of stochastic simulation outputs", Simulation Modelling Practice and Theory,  Vol. 14, No. 3, (2006), 201-223.

41.   Wang, X. and Cheng, T., "Heuristics for parallel-machine scheduling with job class setups and delivery to multiple customers", International Journal of Production Economics,  Vol. 119, No. 1, (2009), 199-206.  

International Journal of Engineering
E-mail: office@ije.ir
Web Site: http://www.ije.ir