Exploring heuristic techniques for flow shop scheduling

• Autorzy: Soltysova Zuzana , Semanco Pavol , Modrak Jan

Identyfikatory

DOI

10.24425/mper.2019.129598

• Języki publikacji: EN

Abstrakty

EN

This paper explores selected heuristics methods, namely CDS, Palmer’s slope index, Gupta’s algorithm, and concurrent heuristic algorithm for minimizing the makespan in permutation flow shop scheduling problem. Its main scope is to explore how different instances sizes impact on performance variability. The computational experiment includes 12 of available benchmark data sets of 10 problems proposed by Taillard. The results are computed and presented in the form of relative percentage deviation, while outputs of the NEH algorithm were used as reference solutions for comparison purposes. Finally, pertinent findings are commented.

Słowa kluczowe

EN

benchmarking; flow shop; makespan; relative percent deviation; heuristics

• Wydawca: Production Engineering Committee of the Polish Academy of Sciences ; Polish Association for Production Management
• Czasopismo: Management and Production Engineering Review
• Rocznik: 2019
• Tom: Vol. 10, No. 3
• Strony: 54–--60
• Opis fizyczny: Bibliogr. 39 poz., wykr.

Twórcy

autor

Soltysova Zuzana

• Faculty of Manufacturing Technologies, Technical University of Kosice, Bayerova 1, 080 01 Presov, Slovakia

autor

Semanco Pavol

• Lear Corporation Seating Slovakia s.r.o., Slovakia

autor

Modrak Jan

• T-systems, Slovakia s.r.o., Slovakia

Bibliografia

• [1] Ruiz R., Stützle T., A simple and effective iterated greedy algorithm for the permutation flowshop scheduling problem, European Journal of Operational Research, 177(3), 2033–2049, 2007.
• [2] Agarwal A., Colak S., Eryarsoy E., Improvement heuristic for the flow-shop scheduling problem: An adaptive-learning approach, European Journal of Operational Research, 169(3), 801–815, 2006.
• [3] Johnson S.M., Optimal two- and three-stage production schedules with setup times included, Nav Res Log Q 1, pp. 61–68, 1954.
• [4] Campbell H.G., Dudek R.A., Smith M.L., A heuristic algorithm for the n-job,m-machine sequencing problem, Management Science, 16, 10, 630–637, 1970.
• [5] Koulamas C., A new constructive heuristic for the flowshop scheduling problem European, Journal of Operational Research Society, 105, 66–71, 1998.
• [6] Yinga K.C., Liao C.J., An ant colony system for permutation flow-shop sequencing, Computing Operation Research, 31(5), 791–801, 2004.
• [7] Taillard E, Benchmarks for basic scheduling problems, European Journal of Operation Research, 64, 278–285, 1993.
• [8] Lin S.W., Ying K.C., Optimization of makespan for no-wait flowshop scheduling problems using efficient matheuristics, Omega, 64, 115–125, 2015.
• [9] Nowicki E., Smutnicki C., A fast tabu search algorithm for the permutation flow-shop problem, European Journal of Operational Research, 91(1), 160– 175, 1996.
• [10] Modrak V., Pandian R.S., Flow shop scheduling algorithm to minimize completion time for n-jobs m-machines problem, Tehnicki Vjesnik, 17(3), 273– 278, 2010.
• [11] Boukef H., Benrejep M., Borne P., A proposed genetic algorithm coding forflow-shop scheduling problems, International Journal Computing Communication Control, 2(3), 229–240, 1953.
• [12] Dima I.C., Gabrara J., Modrak V., Piotr P., Popescu C., Using the expert systems in the operational management of production, 11th WSEAS International Conference on Mathematics and Computers in Business and Economics, pp. 307–312, 2010.
• [13] Chandra P., Mehta P., Tirupati D., Permutation flow shop scheduling withearliness and tardiness penalties, International Journal of Production Research, 47(20), 5591–5610, 2009.
• [14] Semanco P., Modrak V. A comparison of constructive heuristics with the objective of minimizing makespan in the flow-shop scheduling problem, Acta Polytechnica Hungarica, 9(5), 177–190, 2012.
• [15] Papadimitriou C.H., Kanellakis P.C., Flowshop scheduling with limited temporary storage, Journal of the ACM (JACM), 27(3), 533–549, 1980.
• [16] Modrak V., Mandulak J., Mapping Development of MES Functionalities, ICINCO-SPSMC – 6th International Conference on Informatics in Control, Automation and Robotics, pp. 244–247, 2009.
• [17] Yenisey M.M., Yagmahan B., Multi-objective permutation flow shop scheduling problem: Literature review, classification and current trends, Omega, 45, 119–135, 2014.
• [18] Arroyo J.C., Souza Pereira A.A., A GRASP heuristic for the multi-objective permutation flowshop scheduling problem, International Journal of Advanced Manufacturing Technology, 55, 741–753, 2011.
• [19] Framinan J.M., Leisten R., A multi-objective iterated greedy search for flowshop scheduling with makespan and flowtime criteria, OR Spectrum, 30, 787–804, 2008.
• [20] Allahverdi A., A new heuristic for m-machine flowshop scheduling problem with bicriteria of makespan and maximum tardiness, Computers & Operations Research, 31(2), 157–180, 2004.
• [21] Chou F.D., Lee C.E., Two-machine flowshop scheduling with bicriteria problem, Computers & Industrial Engineering, 36, 549–564, 1999.
• [22] Gupta J.N.D., Hennig K., Werner F., Local search heuristics for two-stage flow shop problems with secondary criterion, Computers & Operations Research, 29(2), 123–149, 2002.
• [23] T’kindt V., Gupta J.N.D., Billaut J.C., Twomachine flowshop scheduling with a secondary criterion, Computers & Operations Research, 30(4), 505–526, 2003.
• [24] Arroyo J.C., Armentano V.A., A partial enumeration heuristic for multi-objective flowshop scheduling problems, Journal of the Operational Research Society, 55, 1000–1007, 2004.
• [25] Minella G., Ruiz R., Ciavotta M., Restarted Iterated Pareto Greedy algorithm for multi-objective flowshop scheduling problems, Computers & Operations Research, 38, 1521–1533, 2011.
• [26] Pasupathy T., Rajendran C., Suresh R.K., A multiobjective genetic algorithm for scheduling in flow shops to minimize the makespan and total flow time of jobs, International Journal of Advanced Manufacturing Technology, 27, 804–815, 2006.
• [27] Rahimi-Vahed A.R., Mirghorbani S.M., A multiobjective particle swarm for a flowshop scheduling problem, Journal of Combinatorial Optimization, 13(1), 79–102, 2007.
• [28] Allouche M.A., Aouni B., Martel J.M., Loukil T., Rebaż A., Solving multi-criteria scheduling flow shop problem through compromise programming and satisfaction functions, European Journal of Operational Research, 192, 460–467, 2009.
• [29] Tran T.H., Ng K.M., A water-flow algorithm for flexible flow shop scheduling with intermediate buffers, Journal Scheduling, 4(5), 483–500, 2010.
• [30] Godard D., Laborie P., Nuitjen W., Randomized large neighborhood search for cumulative scheduling, Proceedings of ICAPS-05, pp. 81–89, 2005.
• [31] Dupont de Dinechin B., Time-indexed formulations and a large neighborhood search for the resourceconstrained modulo scheduling problem, Baptiste P., Kendall G., Munier-Kordon A., Sourd F. [Eds], 3rd Multidisciplinary International Scheduling conference: Theory and Applications (MISTA), 2007.
• [32] Lu C., Gao L., Li X., Pan Q., Wang Q., Energyefficient permutation flow shop scheduling problem using a hybrid multi-objective backtracking search algorithm, Journal of Cleaner Production, 144, 228– 238, 2017.
• [33] Bai D., Liang J., Liu B., Tang M., Zhang Z.H., Permutation flow shop scheduling problem to minimize nonlinear objective function with release dates, Computers & Industrial Engineering, 112, 336–347, 2017.
• [34] Rajendran S., Rajendran C., Leisten R., Heuristic rules for tie-breaking in the implementation of the NEH heuristic for permutation flow-shop scheduling, International Journal of Operational Research, 28(1), 87–97, 2017.
• [35] Deng J., Wang L., A competitive memetic algorithm for multi-objective distributed permutation flow shop scheduling problem, Swarm and Evolutionary Computation, 32, 121–131, 2017.
• [36] Li X., Ma S., Multiobjective Discrete Artificial Bee Colony Algorithm for Multiobjective Permutation Flow Shop Scheduling Problem With Sequence Dependent Setup Times, IEEE Transactions on Engineering Management, 64(2), 149–165, 2017.
• [37] Qian B., Li Z.C., Hu R., A copula-based hybrid estimation of distribution algorithm for m-machinereentrant permutation flow-shop scheduling problem, Applied Soft Computing, 61, 921–934, 2017.
• [38] Rossit D.A., Tohm´e F., Frutos M., The nonpermutation flow-shop scheduling problem: a literature review, Omega, 2017.
• [39] Grabowski J., Pempera J., Sequencing of jobs in some production system, European Journal of Operation Research, 125(3), 535–550, 2000.

Uwagi

Opracowanie rekordu ze środków MNiSW, umowa Nr 461252 w ramach programu "Społeczna odpowiedzialność nauki" - moduł: Popularyzacja nauki i promocja sportu (2020).