Multi-criteria Scheduling in Parallel Environment with Learning Effect

• Autorzy: Liu Xinbo , Feng Yue , Ding Ning , Li Rui , Chen Xin

Identyfikatory

DOI

10.2478/fcds-2024-0001

• Języki publikacji: EN

Abstrakty

EN

This paper is devoted to the study of a multi-criteria scheduling problem on unrelated processors with machines’ learning effect, with the goal of minimizing makespan, machine cost and maximal flow-time simultaneously, which is an NP-hard problem. An improved particle swarm optimization algorithm equipped with the overloaded operators, as well as a procedure of Levy flight, is proposed to generate the Pareto-optimal solutions. The experimental results show that the Levy flight strategy can effectively improve the performance of the algorithm, which can generate more non-dominated solutions, and slightly reduce the execution time of the process.

Słowa kluczowe

EN

multi-criteria; parallel processors scheduling

• Wydawca: Wydawnictwo Politechniki Poznańskiej
• Czasopismo: Foundations of Computing and Decision Sciences
• Rocznik: 2024
• Tom: Vol. 49, No. 1
• Strony: 3--20
• Opis fizyczny: Bibliogr. 53 poz., rys., tab.

Twórcy

autor

Liu Xinbo

• SolBridge International School of Business Woosong University, Daejeon, South Korea

autor

Feng Yue

• School of Information Engineering, Liaoning Institute of Science and Engineering, Jinzhou, China

autor

Ding Ning

• College of Physical and Health Dalian University of Technology, Panjin, China

autor

Li Rui

• School of Electronics and Information Engineering Liaoning University of Technology, Jinzhou, China

autor

Chen Xin

• School of Electronics and Information Engineering Liaoning University of Technology, Jinzhou, China

Bibliografia

• [1] Abedi M., Chiong R., Noman N., and Zhang R. A multi-population, multiobjective memetic algorithm for energy-efficient job-shop scheduling with deteriorating machines. Expert Systems with Applications, 157: 113348, 2020.
• [2] Achugbue J. O. and Chin F. Y. Scheduling the open shop to minimize mean flow time. SIAM Journal on Computing, 11(4): 709-720, 1982.
• [3] Ahmadian M. M., Khatami M., Salehipour A., and Cheng T. C. E. Four decades of research on the open-shop scheduling problem to minimize the makespan. European Journal of Operational Research, 295(2): 399-426, 2021.
• [4] Ali M. Z., Awad N. H., Reynolds R. G., and Suganthan P. N. A balanced fuzzy cultural algorithm with a modified levy flight search for real parameter optimization. Information Sciences, 447: 12-35, 2018.
• [5] Azzouz A., Ennigrou M., and Ben Said L. Scheduling problems under learning effects: classification and cartography. International Journal of Production Research, 56(4): 1642-1661, 2018.
• [6] Bai D., Bai X., Yang J., Zhang X., Ren T., Xie C., and Liu B. Minimization of maximum lateness in a flowshop learning effect scheduling with release dates. Computers & Industrial Engineering, 158: 107309, 2021.
• [7] Bai D., Tang M., Zhang Z.-H., and Santibanez-Gonzalez E. D. Flow shop learning effect scheduling problem with release dates. Omega, 78: 21-38, 2018.
• [8] Bandyopadhyay S. and Bhattacharya R. Solving multi-objective parallel machine scheduling problem by a modified nsga-ii. Applied Mathematical Modelling, 37(10-11): 6718-6729, 2013.
• [9] Biskup D. Single-machine scheduling with learning considerations. European Journal of Operational Research, 115(1): 173-178, 1999.
• [10] Biskup D. A state-of-the-art review on scheduling with learning effects. European Journal of Operational Research, 188(2): 315-329, 2008.
• [11] Caldeira R. H. and Gnanavelbabu A. A pareto based discrete jaya algorithm for multi-objective flexible job shop scheduling problem. Expert Systems with Applications, 170: 114567, 2021.
• [12] Chen X., Chau V., Xie P., Sterna M., and Błażewicz J. Complexity of late work minimization in flow shop systems and a particle swarm optimization algorithm for learning effect. Computers & Industrial Engineering, 111: 176-182, 2017.
• [13] Choobineh F. F., Mohebbi E., and Khoo H. A multi-objective tabu search for a single-machine scheduling problem with sequence-dependent setup times. European Journal of Operational Research, 175(1): 318-337, 2006.
• [14] Dósa G. and He Y. Scheduling with machine cost and rejection. Journal of Combinatorial Optimization, 12(4): 337-350, 2006.
• [15] Garey M. R. and Johnson D. S. Computers and intractability: A guide to the theory of NP-completeness. New York, W. H. Freeman & Co., 1979.
• [16] Graham R., Lawler E., Lenstra J., and Kan A. R. Optimization and approximation in deterministic sequencing and scheduling: A survey. Annals of Discrete Mathematics, 5: 287-326, 1979.
• [17] Graham R. L. Bounds on multiprocessing timing anomalies. SIAM Journal on Applied Mathematics, 17(2): 416-429, 1969.
• [18] Guo Z., Wong W. K., Li Z., and Ren P. Modeling and pareto optimization of multi-objective order scheduling problems in production planning. Computers & Industrial Engineering, 64(4): 972-986, 2013.
• [19] Haklı H. and Uğuz H. A novel particle swarm optimization algorithm with levy flight. Applied Soft Computing, 23:333–345, 2014.
• [20] Hematian M., Seyyed Esfahani M. M., Mahdavi I., Mahdavi-Amiri N., and Rezaeian J. A multiobjective integrated multiproject scheduling and multiskilled workforce assignment model considering learning effect under uncertainty. Computational Intelligence, 36(1): 276-296, 2020.
• [21] Hosseinzadeh M., Ghafour M. Y., Hama H. K., Vo B., and Khoshnevis A. Multiobjective task and workflow scheduling approaches in cloud computing: a comprehensive review. Journal of Grid Computing, 18: 327-356, 2020.
• [22] Jensi R. and Jiji G. W. An enhanced particle swarm optimization with levy flight for global optimization. Applied Soft Computing, 43: 248-261, 2016.
• [23] Kennedy J. and Eberhart R. Particle swarm optimization. In Proceedings of ICNN’95-international conference on neural networks, volume 4, pages 1942-1948. IEEE, 1995.
• [24] Lee W.-C. and Wu C.-C. Minimizing total completion time in a two-machine flowshop with a learning effect. International Journal of Production Economics, 88(1): 85-93, 2004.
• [25] Lei D. Multi-objective production scheduling: a survey. The International Journal of Advanced Manufacturing Technology, 43(9): 926-938, 2009.
• [26] Lei D., Yuan Y., and Cai J. An improved artificial bee colony for multi-objective distributed unrelated parallel machine scheduling. International Journal of Production Research, 59(17): 5259-5271, 2021.
• [27] Li K., Chen J., Fu H., Jia Z., and Wu J. Parallel machine scheduling with position-based deterioration and learning effects in an uncertain manufacturing system. Computers & Industrial Engineering, 149: 106858, 2020.
• [28] Liu D., Tan K. C., Huang S., Goh C. K., and Ho W. K. On solving multiobjective bin packing problems using evolutionary particle swarm optimization. European Journal of Operational Research, 190(2): 357-382, 2008.
• [29] Luo H., Du B., Huang G. Q., Chen H., and Li X. Hybrid flow shop scheduling considering machine electricity consumption cost. International journal of production economics, 146(2): 423-439, 2013.
• [30] Mantegna R. N. Fast, accurate algorithm for numerical simulation of levy stable stochastic processes. Physical Review E, 49(5): 4677, 1994.
• [31] Marinakis Y., Marinaki M., and Migdalas A. A multi-adaptive particle swarm optimization for the vehicle routing problem with time windows. Information Sciences, 481: 311-329, 2019.
• [32] Marler R. T. and Arora J. S. Survey of multi-objective optimization methods for engineering. Structural and multidisciplinary optimization, 26(6): 369-395, 2004.
• [33] Mokhtari H. and Hasani A. An energy-efficient multi-objective optimization for flexible job-shop scheduling problem. Computers & Chemical Engineering, 104: 339-352, 2017.
• [34] Mönch L., Balasubramanian H., Fowler J. W., and Pfund M. E. Heuristic scheduling of jobs on parallel batch machines with incompatible job families and unequal ready times. Computers & Operations Research, 32(11): 2731-2750,2005.
• [35] Mosheiov G. Parallel machine scheduling with a learning effect. Journal of the Operational Research Society, 52(10): 1165-1169, 2001.
• [36] Mosheiov G. and Sidney J. B. Scheduling with general job-dependent learning curves. European Journal of Operational Research, 147(3): 665-670, 2003.
• [37] Ott A., Bouchaud J.-P., Langevin D., and Urbach W. Anomalous diffusion in “living polymers”: A genuine levy flight? Physical review letters, 65(17): 2201, 1990.
• [38] Ozdagoglu G., Erdem S., and Salum L. A special purpose multi-criteria heuristic function for a single machine scheduling problem with forward dynamic programming. The International Journal of Advanced Manufacturing Technology, 68(5-8): 1875-1886, 2013.
• [39] Ozturk O. A truncated column generation algorithm for the parallel batch scheduling problem to minimize total flow time. European Journal of Operational Research, 286(2): 432-443, 2020.
• [40] Poli R., Kennedy J., and Blackwell T. Particle swarm optimization. Swarm intelligence, 1(1): 33-57, 2007.
• [41] Przybylski B. A new model of parallel-machine scheduling with integral-based learning effect. Computers & Industrial Engineering, 121: 189-194, 2018.
• [42] Saber R. G. and Ranjbar M. Minimizing the total tardiness and the total carbon emissions in the permutation flow shop scheduling problem. Computers & Operations Research, page 105604, 2021.
• [43] Saeedi S., Khorsand R., Bidgoli S. G., and Ramezanpour M. Improved many-objective particle swarm optimization algorithm for scientific workflow scheduling in cloud computing. Computers & Industrial Engineering, 147:106649, 2020.
• [44] Tian Y., Si L., Zhang X., Cheng R., He C., Tan K. C., and Jin Y. Evolutionary large-scale multi-objective optimization: A survey. ACM Computing Surveys, 54(8): 174:1-174:34, 2022.
• [45] Türkyılmaz A., Şenvar Ö., Ünal İ., and Bulkan S. A research survey: heuristic approaches for solving multi objective flexible job shop problems. Journal of Intelligent Manufacturing, 31(8): 1949-1983, 2020.
• [46] Vahedi Nouri B., Fattahi P., and Ramezanian R. Hybrid firefly-simulated annealing algorithm for the flow shop problem with learning effects and flexible maintenance activities. International Journal of Production Research, 51(12): 3501-3515, 2013.
• [47] Wang X., Gao L., Zhang C., and Shao X. A multi-objective genetic algorithm based on immune and entropy principle for flexible job-shop scheduling problem. The International Journal of Advanced Manufacturing Technology, 51(5): 757-767, 2010.
• [48] Wright T. P. Factors affecting the cost of airplanes. Journal of the Aeronautical Sciences, 3(4): 122-128, 1936.
• [49] Wu M.-C. and Sun S.-H. A project scheduling and staff assignment model considering learning effect. International Journal of Advanced Manufacturing Technology, 28(11-12): 1190-1195, 2006.
• [50] Yagmahan B. and Yenisey M. M. Ant colony optimization for multi-objective flow shop scheduling problem. Computers & Industrial Engineering, 54(3): 411-420, 2008.
• [51] Yeh W.-C., Lai P.-J., Lee W.-C., and Chuang M.-C. Parallel-machine scheduling to minimize makespan with fuzzy processing times and learning effects. Information Sciences, 269: 142-158, 2014.
• [52] Zhang L., Deng Q., Lin R., Gong G., and Han W. A combinatorial evolutionary algorithm for unrelated parallel machine scheduling problem with sequence and machine-dependent setup times, limited worker resources and learning effect. Expert Systems with Applications, 175: 114843, 2021.
• [53] Zitzler E., Thiele L., Laumanns M., Fonseca C. M., and Da Fonseca V. G. Performance assessment of multiobjective optimizers: An analysis and review. IEEE Transactions on evolutionary computation, 7(2): 117-132, 2003.