تعداد نشریات | 43 |
تعداد شمارهها | 1,658 |
تعداد مقالات | 13,563 |
تعداد مشاهده مقاله | 31,147,378 |
تعداد دریافت فایل اصل مقاله | 12,271,785 |
An effective new heuristic algorithm for solving permutation flow shop scheduling problem | ||
Transactions on Combinatorics | ||
دوره 11، شماره 1، خرداد 2022، صفحه 15-27 اصل مقاله (538.82 K) | ||
نوع مقاله: Research Paper | ||
شناسه دیجیتال (DOI): 10.22108/toc.2021.126406.1795 | ||
نویسنده | ||
Shahriar Farahmand rad* | ||
Department of Mathematics, Payame Noor University of ABCD, P.O.Box 19395-3697, Tehran, Iran | ||
چکیده | ||
The deterministic permutation flow shop scheduling problem with makespan criterion is not solvable in polynomial time. Therefore, researchers have thought about heuristic algorithms. There are many heuristic algorithms for solving it that is a very important combinatorial optimization problem. In this paper, a new algorithm is proposed for solving the mentioned problem. The presented algorithm chooses the weighted path that starts from the up-left corner and reaches the down-right in the matrix of jobs processing times and calculates the biggest sum of the times in the footprints of this path. The row with the biggest sum permutes among all the rows of the matrix for locating the minimum of makespan. This method was run on Taillard’s standard benchmark and the solutions were compared with the optimum or the best ones as well as 14 famous heuristics. The validity and effectiveness of the algorithm are shown with tables and statistical evaluation. | ||
کلیدواژهها | ||
Heuristic؛ flowshop؛ scheduling؛ makespan؛ total completion time | ||
مراجع | ||
[1] M. Ancău, On Solving Flowshop Scheduling Problems, Proc. Rom. Acad. Ser. A Math. Phys. Tech. Sci. Inf. Sci., 13 (2012) 71–79. [2] R. E. Bellman, A. O. Esogbue and I. Nabeshima, Mathematical aspects of scheduling and applications, International Series in Modern Applied Mathematics and Computer Science, 4 (2014) [3] M. C. Bonney and S. W. Gundry, Solutions to the constrained flowshop sequencing problem, Journal of the Opera- tional Research Society, 27 (1976) 869–883. [4] A. Brum and M. Ritt, Automatic Design of Heuristics for Minimizing the Makespan in Permutation Flow Shops, In 2018 IEEE Congress on Evolutionary Computation (CEC), (2018) 1–8. IEEE. [5] H. G. Campbell, R. A. Dudek and M. L. Smith, A heuristic algorithm for the n job, m machine sequencing problem, Management Sci., 16 (1970) B–630. [6] D. G. Dannenbring, An evaluation of flow shop sequencing heuristics, Management Sci., 23 (1977) 1174–1182.
[7] V. Fernandez-Viagas and J. M. Framinan, NEH-based heuristics for the permutation flowshop scheduling problem to minimise total tardiness, Comput. Oper. Res., 60 (2015) 27–36. [8] V. Fernandez-Viagas, J. M. Molina-Pariente and J. M. Framinan, Generalised accelerations for insertion-based heuristics in permutation flowshop scheduling, European J. Oper. Res., 282 (2020) 858–872. [9] V. Fernandez-Viagas, R. Ruiz and J. M. Framinan, A new vision of approximate methods for the permutation flowshop to minimise makespan: State-of-the-art and computational evaluation, European J. Oper. Res., 257 (2017) 707–721. [10] J. M. Framinan, J. N. Gupta and R. Leisten, A review and classification of heuristics for permutation flow-shop scheduling with makespan objective, Journal of the Operational Research Society, 55 (2004) 1243–1255. [11] M. R. Garey, D. S. Johnson and R. Sethi, The complexity of flowshop and jobshop scheduling, Math. Oper. Res., 1 (1976) 117–129. [12] R. L. Graham, E. L. Lawler, J. K. Lenstra and A. R. Kan, Optimization and approximation in deterministic sequencing and scheduling: a survey, Ann. Discrete Math., 5 (1979) 287–326. [13] J. N. Gupta, A functional heuristic algorithm for the flowshop scheduling problem, Journal of the Operational Research Society, 22 (1971) 39–47. [14] S. Hejazi and S. Saghafian, Flowshop-scheduling problems with makespan criterion: a review, International Journal of Production Research, 43 (14) (2005) 2895–2929. [15] J. C. Ho and Y. L. Chang, A new heuristic for the n-job, M-machine flow-shop problem, European J. Oper. Res., 52 (1991) 194–202. [16] T. S. Hundal and J. Rajgopal, An extension of Palmer’s heuristic for the flow shop scheduling problem, International Journal Of Production Research, 26 (1988) 1119–1124. [17] F. Jin, S. Song and C. Wu, An improved version of the NEH algorithm and its application to large-scale flow-shop scheduling problems, IIE Trans., 39 (2007) 229–234. [18] Johnson, S. M. Optimal twoand threestage production schedules with setup times included, Naval Res. Logist. Quart., 1 (1954) 61-68. [19] Kalczynski, P. J., & Kamburowski, J. On the NEH heuristic for minimizing the makespan in permutation flow shops, Omega, 35 (2007) 53-60. [20] King, J. R., & Spachis, A. S. Heuristics for flow-shop scheduling, International Journal of Production Research, 18 (1980) 345-357. [21] Koulamas, C. A new constructive heuristic for the flowshop scheduling problem, European J. Oper. Res., 105 (1998) 66-71. [22] Liu, W., Jin, Y., & Price, M. A new NawazEnscoreHam-based heuristic for permutation flow-shop problems with bicriteria of makespan and machine idle time, Eng. Optim., 48 (2016) 1808-1822. [23] Malik, A., & Dhingra, A. K. Comparative analysis of heuristics for make span minimizing in flow shop scheduling, International Journal of Innovations in Engineering and Technology, 2 (2013) 263-269. [24] Nawaz, M., Enscore, Jr, E. E., & Ham, I. A heuristic algorithm for the m-machine, n-job flow-shop sequencing problem, Omega, 11 (1983) 91-95. [25] Nurdiansyah, R., Rijanto, O. A. W., Santosa, B., & Wiratno, S. E. An Improved Differential Evolution Algorithm for Permutation Flow Shop Scheduling Problem, Int. J. Oper. Res. (Taichung), 16 (2019) 37-44. [26] Page, E. S. An approach to the scheduling of jobs on machines, J. Roy. Statist. Soc. Ser. B (Methodological), 23 (1961) 484-492. [27] Palmer, D. S. Sequencing jobs through a multi-stage process in the minimum total time–a quick method of obtaining a near optimum, Journal of the Operational Research Society, 16 (1965) 101-107.
[28] Potts, C. N., & Strusevich, V. A. Fifty years of scheduling: a survey of milestones, Journal of the Operational Research Society, 60 (2009) S41-S68. [29] Rad, S. F., Ruiz, R., & Boroojerdian, N. New high performing heuristics for minimizing makespan in permutation flowshops, Omega, 37 (2009) 331-345. [30] Ruiz, R., & Maroto, C. A comprehensive review and evaluation of permutation flowshop heuristics, European J. Oper. Res., 165 (2005) 479-494. [31] Sarin, S., & Lefoka, M. Scheduling heuristic for the n-jobm-machine flow shop, Omega, 21 (1993) 229-234.
[32] Sauvey, C., & Sauer, N. Two NEH Heuristic Improvements for Flowshop Scheduling Problem with Makespan Criterion, Algorithms, 13 (2020) 112. [33] Singhal, E., Singh, S., & Dayma, A. An Improved Heuristic for Permutation Flow Shop Scheduling, In (NEH ALGORITHM). International Journal of Computational Engineering Research, 2 (2012) 95-100. [34] STINSON, J. P., & SMITH, A. W. A heuristic prorammin procedure for sequencin the static flowshop, The Inter- national Journalof Production Research, 20 (1982) 753-764. [35] Suliman, S. M. A. A two-phase heuristic approach to the permutation flow-shop scheduling problem, International Journal of Production Economics, 64 (2000) 143-152. [36] Taillard, E. Benchmarks for basic scheduling problems, European J. Oper. Res., 64 (1993) 278-285.
[37] Taillard, E. Some efficient heuristic methods for the flow shop sequencing problem, European J. Oper. Res., 47 (1990) 65-74. [38] T’kindt, V., & Billaut, J. C. Multicriteria scheduling: theory, models and algorithms, Springer Science & Business Media, (2006). [39] E. Vallada, R. Ruiz and J. M. Framinan, New hard benchmark for flowshop scheduling problems minimising makespan, European J. Oper. Res., 240 (2015) 666-677. [40] J. Xu, Y. Yin, T. C. E. Cheng, C. C. Wu and S. Gu, An improved memetic algorithm based on a dynamic neighbourhood for the permutation flowshop scheduling problem, Int. J. Prod. Res., 52 (2014) 1188–1199. | ||
آمار تعداد مشاهده مقاله: 495 تعداد دریافت فایل اصل مقاله: 422 |