Research on optimization of unrelated parallel machine scheduling based on IG-TS algorithm

• Autorzy: Chi Xinfu , Liu Shijing , Li Ce

Identyfikatory

DOI

10.24425/bpasts.2022.141724

• Języki publikacji: EN

Abstrakty

EN

This issue is a typical NP-hard problem for an unrelated parallel machine scheduling problem with makespan minimization as the goal and no sequence-related preparation time. Based on the idea of tabu search (TS), this paper improves the iterative greedy algorithm (IG) and proposes an IG-TS algorithm with deconstruction, reconstruction, and neighborhood search operations as the main optimization process. This algorithm has the characteristics of the strong capability of global search and fast speed of convergence. The warp knitting workshop scheduling problem in the textile industry, which has the complex characteristics of a large scale, nonlinearity, uncertainty, and strong coupling, is a typical unrelated parallel machine scheduling problem. The IG-TS algorithm is applied to solve it, and three commonly used scheduling algorithms are set as a comparison, namely the GA-TS algorithm, ABC-TS algorithm, and PSO-TS algorithm. The outcome shows that the scheduling results of the IG-TS algorithm have the shortest manufacturing time and good robustness. In addition, the production comparison between the IG-TS algorithm scheduling scheme and the artificial experience scheduling scheme for the small-scale example problem shows that the IG-TS algorithm scheduling is slightly superior to the artificial experience scheduling in both planning and actual production. Experiments show that the IG-TS algorithm is feasible in warp knitting workshop scheduling problems, effectively realizing the reduction of energy and the increase in efficiency of a digital workshop in the textile industry.

Słowa kluczowe

EN

warp knitting machine; parallel machine scheduling; iterative greedy algorithm; tabu search

PL

osnowarka; planowanie maszyn równoległych; algorytm zachłanny iteracyjny; przeszukiwanie tabu

• Wydawca: Polska Akademia Nauk, Wydział IV Nauk Technicznych
• Czasopismo: Bulletin of the Polish Academy of Sciences. Technical Sciences
• Rocznik: 2022
• Tom: Vol. 70, nr 4
• Strony: art. no. e141724
• Opis fizyczny: Bibliogr. 28 poz., rys., tab.

Twórcy

autor

Chi Xinfu

• Dong Hua University, College of Mechanical Engineering, Shanghai 201620, China

• https://orcid.org/0000-0002-0460-9126

autor

Liu Shijing

• Dong Hua University, College of Mechanical Engineering, Shanghai 201620, China

autor

Li Ce

• Dong Hua University, College of Mechanical Engineering, Shanghai 201620, China

Bibliografia

• [1] S.-W. Lin and K.-C. Ying, “A multi-point simulated annealing heuristic for solving multiple objective unrelated parallel machine scheduling problems,” Int. J. Prod. Res., vol. 53, no. 4, pp. 1065–1076, 2015, doi: 10.1080/00207543.2014.942011.
• [2] H.R. Lewis, Michael R., Garey and David S. Johnson. “Computers and intractability. A guide to the theory of NP-completeness.” W.H. Freeman and Company, San Francisco 1979, x+338 pp.,” J. Symb. Log., vol. 48, no. 2, pp. 498–500, 1983, doi: 10.2307/2273574.
• [3] W. Bożejko, M. Uchroński, and M. Wodecki, “Blocks for two-machines total weighted tardiness flow shop scheduling problem,” Bull. Pol. Acad. Sci. Tech. Sci., vol. 68, no. 1, pp. 31–41, 2020, doi: 10.24425/bpasts.2020.131829.
• [4] V. Suresh and S. Senthil Kumar, “Research on hybrid modified pathfinder algorithm for optimal reactive power dispatch,” Bull. Pol. Acad. Sci. Tech. Sci., vol. 69, no. 4, pp. e137733, 2021 2021, doi: 10.24425/bpasts.2021.137733.
• [5] G. Rabadi, R.J. Moraga, and A. Al-Salem, “Heuristics for the Unrelated Parallel Machine Scheduling Problem with Setup Times,” J. Intell. Manuf., vol. 17, no. 1, pp. 85–97, 2006, doi: 10.1007/s10845-005-5514-0.
• [6] S.A. Torabi, N. Sahebjamnia, S.A. Mansouri, and M.A. Bajestani, “A particle swarm optimization for a fuzzy multi-objective unrelated parallel machines scheduling problem,” Appl. Soft Comput., vol. 13, no. 12, pp. 4750–4762, 2013, doi: 10.1016/j.asoc.2013.07.029.
• [7] R. Gedik, D. Kalathia, G. Egilmez, and E. Kirac, “A constraint programming approach for solving unrelated parallel machine scheduling problem,” Comput. Ind. Eng., vol. 121, pp. 139–149, 2018, doi: 10.1016/j.cie.2018.05.014.
• [8] L. Fanjul-Peyro, R. Ruiz, and F. Perea, “Reformulations and an exact algorithm for unrelated parallel machine scheduling problems with setup times,” Comput. Oper. Res., vol. 101, pp. 173–182, 2019, doi: 10.1016/j.cor.2018.07.007.
• [9] E. Vallada, F. Villa, and L. Fanjul-Peyro, “Enriched metaheuristics for the resource constrained unrelated parallel machine scheduling problem,” Comput. Oper. Res., vol. 111, pp. 415–424, 2019, doi: 10.1016/j.cor.2019.07.016.
• [10] J. Gao, “A novel artificial immune system for solving multiobjective scheduling problems subject to special process constraint,” Comput. Ind. Eng., vol. 58, no. 4, pp. 602–609, 2010, doi: 10.1016/j.cie.2009.12.009.
• [11] A. Guinet, “Scheduling sequence-dependent jobs on identical parallel machines to minimize completion time criteria,” Int. J. Prod. Res., vol. 31, no. 7, pp. 1579–1594, 1993, doi: 10.1080/00207549308956810.
• [12] R. Ruiz and T. Stützle, “A simple and effective iterated greedy algorithm for the permutation flowshop scheduling problem,” Eur. J. Oper. Res., vol. 177, no. 3, pp. 2033–2049, 2007, doi: 10.1016/j.ejor.2005.12.009.
• [13] C. Yu, Q. Semeraro, and A. Matta, “A genetic algorithm for the hybrid flow shop scheduling with unrelated machines and machine eligibility,” Comput. Oper. Res., vol. 100, pp. 211–229, 2018, doi: 10.1016/j.cor.2018.07.025.
• [14] H. Soleimani, H. Ghaderi, P.-W. Tsai, N. Zarbakhshnia, and M. Maleki, “Scheduling of unrelated parallel machines considering sequence-related setup time, start time-dependent deterioration, position-dependent learning and power consumption minimization,” J. Cleaner Prod., vol. 249, p. 119428, 2020, doi: 10.1016/j.jclepro.2019.119428.
• [15] Y.-B. Woo, S. Jung, and B.S. Kim, “A rule-based genetic algorithm with an improvement heuristic for unrelated parallel machine scheduling problem with time-dependent deterioration and multiple rate-modifying activities,” Comput. Ind. Eng., vol. 109, pp. 179–190, 2017, doi: 10.1016/j.cie.2017.05.007.
• [16] H. Zhang, F. Liu, Y. Zhou, and Z. Zhang, “A hybrid method integrating an elite genetic algorithm with tabu search for the quadratic assignment problem,” Inf. Sci., vol. 539, pp. 347–374, 2020, doi: 10.1016/j.ins.2020.06.036.
• [17] J. Xiao, J. Pachl, B. Lin, and J. Wang, “Solving the block-totrain assignment problem using the heuristic approach based on the genetic algorithm and tabu search,” Transp. Res. Part B, Methodol., vol. 108, pp. 148–171, 2018, doi: 10.1016/j.trb.2017.12.014.
• [18] W. Sukkerd and T. Wuttipornpun, “Hybrid genetic algorithm and tabu search for finite capacity material requirement planning system in flexible flow shop with assembly operations,” Comput. Ind. Eng., vol. 97, pp. 157–169, 2016, doi: 10.1016/j.cie.2016.05.006.
• [19] T. Thongwan, A. Kangrang, and H. Prasanchum, “Multiobjective future rule curves using conditional tabu search algorithm and conditional genetic algorithm for reservoir operation,” Heliyon, vol. 5, no. 9, p. e02401, 2019, doi: 10.1016/j.heliyon.2019.e02401.
• [20] H. Tehzeeb ul, T. Alquthami, S.E. Butt, M.F. Tahir, and K. Mehmood, “Short-term optimal scheduling of hydro-thermal power plants using artificial bee colony algorithm,” Energy Rep., vol. 6, pp. 984–992, 2020, doi: 10.1016/j.egyr.2020.04.003.
• [21] H. Li, X. Li, and L. Gao, “A discrete artificial bee colony algorithm for the distributed heterogeneous no-wait flowshop scheduling problem,” Appl. Soft Comput., vol. 100, p. 106946, 2021, doi: 10.1016/j.asoc.2020.106946.
• [22] S. Su, F. Zhou, and H. Yu, “An artificial bee colony algorithm with variable neighborhood search and tabu list for long-term carpooling problem with time window,” Appl. Soft Comput., vol. 85, p. 105814, 2019, doi: 10.1016/j.asoc.2019.105814.
• [23] S. Lu, X. Liu, J. Pei, M.T. Thai, and P.M. Pardalos, “A hybrid ABC–TS algorithm for the unrelated parallel-batching machines scheduling problem with deteriorating jobs and maintenance activity,” Appl. Soft Comput., vol. 66, pp. 168–182, 2018, doi: 10.1016/j.asoc.2018.02.018.
• [24] D.C. Hop, N. Van Hop, and T.T.M. Anh, “Adaptive particle swarm optimization for integrated quay crane and yard truck scheduling problem,” Comput. Ind. Eng., vol. 153, p. 107075, 2021, doi: 10.1016/j.cie.2020.107075.
• [25] H. Ding and X. Gu, “Hybrid of human learning optimization algorithm and particle swarm optimization algorithm with scheduling strategies for the flexible job-shop scheduling problem,” Neurocomputing, vol. 414, pp. 313–332, 2020, doi: 10.1016/j.neucom.2020.07.004.
• [26] M.K. Marichelvam, M. Geetha, and Ö. Tosun, “An improved particle swarm optimization algorithm to solve hybrid flowshop scheduling problems with the effect of human factors – A case study,” Comput. Oper. Res., vol. 114, p. 104812, 2020, doi: 10.1016/j.cor.2019.104812.
• [27] I. Alharkan, M. Saleh, M. A. Ghaleb, H. Kaid, A. Farhan, and A. Almarfadi, “Tabu search and particle swarm optimization algorithms for two identical parallel machines scheduling problem with a single server,” J. King Saud Univ. Eng. Sci., vol. 32, no. 5, pp. 330–338, 2020, doi: 10.1016/j.jksues.2019.03.006.
• [28] G. Lin, J. Guan, Z. Li, and H. Feng, “A hybrid binary particle swarm optimization with tabu search for the set-union knapsack problem,” Expert Syst. Appl., vol. 135, pp. 201–211, 2019, doi: 10.1016/j.eswa.2019.06.007.

Uwagi

Opracowanie rekordu ze środków MEiN, umowa nr SONP/SP/546092/2022 w ramach programu "Społeczna odpowiedzialność nauki" - moduł: Popularyzacja nauki i promocja sportu (2022-2023).