A Comparative Analysis of Heuristic Metaheuristic and Exact Approach to Minimize Make Span of Permutation Flow Shop Scheduling

Tanzila Azad^1, and Asif Ahmed Sarja²

¹Department of Mechanical and Production Engineering, Ahsanullah University of Science and Technology, Dhaka, Bangladesh

²Department of Computer Science and Engineering Islamic University of Technology Gazipur, Bangladesh

Cite this paper:
Tanzila Azad and Asif Ahmed Sarja. A Comparative Analysis of Heuristic Metaheuristic and Exact Approach to Minimize Make Span of Permutation Flow Shop Scheduling. American Journal of Industrial Engineering. 2021; 8(1):1-8. doi: 10.12691/ajie-8-1-1

Abstract

The study of permutation flow shop scheduling issues has proved fascinating. Make span reduction has been explored extensively throughout the years as one of the many factors. If there are more than two machines, finding a schedule that optimizes total completion times for Permutation Flow Shop issues is NP Hard. The well-known Nawaz–Enscore–Ham (NEH) heuristic is acknowledged as the top performing approach for the permutation flow shop scheduling issue till now, according to the make span minimization criteria. For large-scale problems, however, the NEH approach takes a long time to discover an estimated optimum solution. Many researchers have offered heuristics and meta-heuristics as the time it takes to compute grows exponentially in proportion to the size of the problem. For the permutation flow shop scheduling problem, we proposed a genetic algorithm with the criterion of minimizing make span as the criteria. The method's performance is compared to that of the well-known NEH algorithm. Computational experiments on benchmark data sets revealed that the proposed approach produces satisfactory solutions in short computational cycles. Furthermore, it just requires a few user-defined parameters, making it relevant to real-world flow shop scheduling challenges. The findings reveal that, when compared to an exact technique, the proposed genetic algorithm (GA) is capable of rapidly seeking optimal solutions for most small-sized instances. Furthermore, the proposed GA continues to function satisfactorily for medium and large-scale instances and generates solutions in a reasonable period.

Keywords:
minimize permutation flow shop scheduling genetic algorithm NEH algorithm make span

This work is licensed under a Creative Commons Attribution 4.0 International License. To view a copy of this license, visit http://creativecommons.org/licenses/by/4.0/

References:

[1]	Chakraborty UK. (2009). Computational intelligence in flow shop and job shop scheduling. Springer Science & Business Media, Berlin.
[2]	Pinedo M. (2002). Scheduling – theory, algorithms, and systems. Prentice-Hall, Upper Saddle River.
[3]	Wagner HM. (1959). An integer linear-programming model for machine scheduling. Nav Res Logist Q 6:131-140.
[4]	Baker KR. (1974) Introduction to sequencing and scheduling. Wiley, New York.
[5]	Stafford EF. (1988). On the development of a mixed-integer linear programming model for the flowshop sequencing problem. J Oper Res Soc 39: 1163-1174.
[6]	Wilson JM. (1989). Alternative formulations of a flow-shop scheduling problem. J Oper Res Soc 40: 395-399.
[7]	Manne AS. (1960). On the job-shop scheduling problem. Oper Res 8: 219-223.
[8]	Rinnooy Kan AHG. (1976). Machine scheduling problems: classification, complexity, and computations. Nijhoff, The Hague
[9]	Nawaz M, Enscore EE Jr, Ham I. (1983). A heuristic algorithm for the m-machine, n-job flow shop sequencing problem. OMEGA 11(1): 91-95.
[10]	Palmer DS. (1965). Sequencing jobs through a multistage process in the minimum total time: a quick method of obtaining a near optimum. Oper Res Q 16: 101-107.
[11]	Campbell HG, Dudek RA, Smith ML. (1970). A heuristic algorithm for the n job, m machine sequencing problem. Manag Sci 16(10): B630-B637.
[12]	Dong X, Huang H, Chen P. (2008). An improved NEH-based heuristic for the permutation flowshop problem. Comput Oper Res 35: 3962-3968.
[13]	Li XP, Wang YX, Wu C. (2004). Heuristic algorithms for large flowshop scheduling problems. In: Proceedings of the 5th world congress on intelligent control and automation, pp 2999-3003.
[14]	Rizkya, I. et al. (2019). “Nawaz, Enscore, Ham (NEH) Algorithm to Minimization of Makespan in Furniture Company”, IOP Conference Series: Materials Science and Engineering, 505(1).
[15]	Baskar, A. (2016). “Revisiting the NEH algorithm- the power of job insertion technique for optimizing the makespan in permutation flow shop scheduling”, International Journal of Industrial Engineering Computations, 7(2), pp. 353-366.
[16]	Bhatt, P. (2019). “Permutation Flow Shop via Simulated Annealing and NEH”, UNLV Theses, Dissertations, Professional Papers, and Capstones. 3575.
[17]	Liu, W., Jin, Y. and Price, M. (2016). “A new Nawaz–Enscore–Ham-based heuristic for permutation flow-shop problems with bicriteria of makespan and machine idle time”, Engineering Optimization, 48(10), pp. 1808-1822.
[18]	Osman I, Potts C. (1989). Simulated annealing for permutation flow shop scheduling. OMEGA 17(6):551-557.
[19]	Grabowski J, Wodecki M. (2004). A very fast tabu search algorithm for the permutation flowshop problem with makespan criterion. Comput Oper Res 31(11):1891-1909.
[20]	Rajendran C, Ziegler H. (2004). Ant-colony algorithms for permutation flowshop scheduling to minimize makespan/total flowtime of jobs. Eur J Oper Res. 155(2):426-438.
[21]	Stützle T. (1998). Applying iterated local search to the permutation flowshop problem. Technical report, AIDA-98-04, Intellctics Group, Computer Science Department, Darmstad University of Technology, Darmstad, Germany.
[22]	Haq, A. N. et al. (2010). “A hybrid neural network-genetic algorithm approach for permutation flow shop scheduling”, International Journal of Production Research, 48(14), pp. 4217-4231.
[23]	Jeen Robert, R. B. and Rajkumar, R. (2017). “An effective genetic algorithm for flow shop scheduling problems to minimize makespan”, Mechanika, 23(4), pp. 594-603.
[24]	Widyawati and Waliadi, G. (2020). “Improved Genetic Algorithm for Flow Shop Scheduling Problem at PT. XYZ”, Journal of Physics: Conference Series, 1477(2).