Optimization of Two-Stage Hybrid Flow Shop Scheduling Problems Using Genetic Algorithm

Abstract:

The two-stage Hybrid flow shop (HFS) scheduling is characterized n jobs m machines with two-stages in series. The essential complexities of the problem need to solve the hybrid flow shop scheduling using meta-heuristics. The paper addresses two-stage hybrid flow shop scheduling problems to minimize the makespan time with the batch size of 100 using Genetic Algorithm (GA) and Simulated Annealing algorithm (SA). The computational results observed that the GA algorithm is finding out good quality solutions than SA with lesser computational time.

• Periodical: Applied Mechanics and Materials (Volumes 766-767)
• Pages: 962-967
• DOI: https://doi.org/10.4028/www.scientific.net/AMM.766-767.962
• Online since: June 2015
• Authors: M. Saravanan, Sridhar S*, N. Harikannan
• Keywords: Genetic Algorithm, Makespan, Simulated Annealing Algorithm, Two-Stage Hybrid Flow Shop

References

[1] J.N.D. Gupta, Two-stage, hybrid flow shop scheduling problem, Journal of the Operational Research Society, 39 (4) (1998) 359–364.

[2] J.A. Hoogeveen, J.K. Lenstra, B. Veltman, Preemptive scheduling in a two-stage multiprocessor flow shop is np-hard, European Journal of Operational Research, 89 (1) (1996) 172–175.

DOI: 10.1016/s0377-2217(96)90070-3

[3] P. Schuurman, G.J. Woeginger, A polynomial time approximation scheme for the two-stage multiprocessor flow shop problem, Theoretical Computer Science, 237 (1–2) (2000) 105–122.

DOI: 10.1016/s0304-3975(98)00157-1

[4] C. Koulamas, G.J. Kyparisis, Asymptotically optimal linear time algorithms for two-stage and three-stage flexible flow shops, Naval Research Logistics, 47 (3) (2000) 259–268.

DOI: 10.1002/(sici)1520-6750(200004)47:3<259::aid-nav5>3.0.co;2-k

[5] T.P. Hong, T.T. Wang, S.L. Wang, A palmer-based continuous fuzzy flexible flow-shop scheduling algorithm, International Journal of Soft Computing, 5 (6) (2001) 426–433.

DOI: 10.1007/s005000100109

[6] D. He, A. Babayan, Scheduling manufacturing systems for delayed product differentiation in agile manufacturing, International Journal of Production Research, 40 (11) (2002) 2461–2481.

DOI: 10.1080/00207540210136522

[7] C. Oguz, M.F. Ercan, T.C.E. Cheng, and Y.F. Fung, Heuristic algorithms for multiprocessor task scheduling in a two-stage hybrid flow-shop, European Journal of Operational Research, 149 (2) (2003) 390–403.

DOI: 10.1016/s0377-2217(02)00766-x

[8] J.X. Xie, X. J Wang, Complexity and algorithms for two-stage flexible flowshop scheduling with availability constraints, Computers and Mathematics with Applications, 50 (10–12) (2005) 1629–1638.

DOI: 10.1016/j.camwa.2005.07.008

[9] J.X. Xie, W.X. Xing, Z.X. Liu, J.F. Dong, Minimum deviation algorithm for two-stage no-wait flow shops with parallel machines, Computers and Mathematics with Applications, 47 (12) (2004) 1857–1863.

DOI: 10.1016/j.camwa.2003.08.003

[10] C.S. Sung, H.A. Kim, A two-stage multiple-machine assembly scheduling problem for minimizing sum of completion times, International Journal of Production Economics, 113 (2) (2008) 1038–1048.

DOI: 10.1016/j.ijpe.2007.12.007

[11] S. Sridhar, T. Prabaharan, M. Saravanan, Optimisation of sequencing and scheduling in hybrid flow shop environment using heuristic approach, International Journal of Logistics Economics and Globalisation, 2 (4) (2010) 331–351.

DOI: 10.1504/ijleg.2010.037520

[12] M. Saravanan, S. Sridhar, An overview of hybrid flow shop scheduling: sustainability perspective, International Journal of Green Computing, 3 (2) (2012) 78–91.

DOI: 10.4018/jgc.2012070106

[13] C.T. Tsenga, C.J. Liao, T.X. Liao, A note on two-stage hybrid flow shop scheduling with missing operations, Computers and Industrial Engineering, 54 (3) (2008) 695–704.

DOI: 10.1016/j.cie.2007.09.005

[14] F. Jolai, H. Asefi, M. Rabiee, P. Ramezani, Bi-objective simulated annealing approaches for no-wait two-stage flexible flow shop scheduling problem, Scientia Iranica, 20 (3) (2013) 861–872.

DOI: 10.2139/ssrn.3431088

[15] E. Figielska, Heuristic algorithms for preemptive scheduling in a two-stage hybrid flow shop with additional renewable resources at each stage, Computers & Industrial Engineering, 59 (4) (2010) 509-519.

DOI: 10.1016/j.cie.2010.06.006

[16] H.S. Mirsanei, M. Zandieh, M.J. Moayed M.R. Khabbazi, A simulated annealing algorithm approach to hybrid flow shop scheduling with sequence-dependent setup times, Journal of Intelligent Manufacturing, 22 (2011) 965–978.

DOI: 10.1007/s10845-009-0373-8

[17] D. He, A. Babayan, Scheduling manufacturing systems for delayed product differentiation in agile manufacturing, International Journal of Production Research, 40 (11) (2002) 2461–2481.

DOI: 10.1080/00207540210136522

[18] M. Saravanan, S. Sridhar, N. Harikannan, Optimization of realistic multi-stage hybrid flow shop scheduling problems with missing operations using meta-heuristics, International Journal of Engineering and Technology, 6 (1) (2014), 484-496.

DOI: 10.15866/ireme.v8i5.3296

[19] J. H Holland, Adaptation in natural and artificial systems, The University of Michigan Press, Ann Arbor, (1975).

[20] S. Kirkpatrick, C.D. Gelatt, M.P. Vecchi, Optimization by simulated annealing, Science, 220, (4598) (1983), 671-680.

DOI: 10.1126/science.220.4598.671