Two meta-heuristic algorithms for scheduling on unrelated machines with the late work criterion

Wang, Wen ; Chen, Xin ; Musial, Jędrzej ; Blazewicz, Jacek

International Journal of Applied Mathematics and Computer Science, Tome 30 (2020) no. 3, pp. 573-584.

Résumé

A scheduling problem in considered on unrelated machines with the goal of total late work minimization, in which the late work of a job means the late units executed after its due date. Due to the NP-hardness of the problem, we propose two meta-heuristic algorithms to solve it, namely, a tabu search (TS) and a genetic algorithm (GA), both of which are equipped with the techniques of initialization, iteration, as well as termination. The performances of the designed algorithms are verified through computational experiments, where we show that the GA can produce better solutions but with a higher time consumption. Moreover, we also analyze the influence of problem parameters on the performances of these metaheuristics.

Détail

Keywords: late work minimization, unrelated machines, tabu search, genetic algorithm
Mots-clés : minimalizacja opóźnienia, przeszukiwanie tabu, algorytm genetyczny

Bibliographie

[1] Abasian, F., Ranjbar, M., Salari, M., Davari, M. and Khatami, S.M. (2014). Minimizing the total weighted late work in scheduling of identical parallel processors with communication delays, Applied Mathematical Modelling 38(15): 3975–3986.

[2] Błażewicz, J. (1984). Scheduling preemptible tasks on parallel processors with information loss, Technique et Science Informatiques 3(6): 415–420.

[3] Błażewicz, J., Ecker, K.H., Pesch, E., Schmidt, G., Sterna, M. and Weglarz, J. (2019). Handbook on Scheduling: From Theory to Practice, Springer, Cham.

[4] Błażewicz, J. and Finke, G. (1987). Minimizing mean weighted execution time loss on identical and uniform processors, Information Processing Letters 24(4): 259–263.

[5] Błażewicz, J., Kovalyov, M.Y., Musiał, J., Urbański, A.P. and Wojciechowski, A. (2010). Internet shopping optimization problem, International Journal of Applied Mathematics and Computer Science 20(2): 385–390, DOI: 10.2478/v10006-010-0028-0.

[6] Blażewicz, J., Pesch, E. and Sterna, M. (2000). The disjunctive graph machine representation of the job shop scheduling problem, European Journal of Operational Research 127(2): 317–331.

[7] Błażewicz, J., Pesch, E., Sterna,M. and Werner, F. (2004). Open shop scheduling problems with late work criteria, Discrete Applied Mathematics 134(1): 1–24.

[8] Błażewicz, J., Pesch, E., Sterna, M. and Werner, F. (2005). The two-machine flow-shop problem with weighted late work criterion and common due date, European Journal of Operational Research 165(2): 408–415.

[9] Błażewicz, J., Pesch, E., Sterna, M. and Werner, F. (2007). A note on the two machine job shop with the weighted late work criterion, Journal of Scheduling 10(2): 87–95.

[10] Blazewicz, J., Pesch, E., Sterna, M. and Werner, F. (2008). Metaheuristic approaches for the two-machine flow-shop problem with weighted late work criterion and common due date, Computers Operations Research 35(2): 574–599.

[11] Chen, R., Yuan, J., Ng, C. and Cheng, T. (2019). Single-machine scheduling with deadlines to minimize the total weighted late work, Naval Research Logistics (NRL) 66(7): 582–595.

[12] Chen, X., Chau, V., Xie, P., Sterna, M. and Błażewicz, J. (2017). Complexity of late work minimization in flow shop systems and a particle swarm optimization algorithm for learning effect, Computers Industrial Engineering 111: 176–182.

[13] Chen, X., Kovalev, S., Sterna, M. and Błażewicz, J. (2020a). Mirror scheduling problems with early work and late work criteria, Journal of Scheduling, DOI:10.1007/s10951-020-00636-9.

[14] Chen, X., Liang, Y., Sterna, M., Wang, W. and Błażewicz, J. (2020b). Fully polynomial time approximation scheme to maximize early work on parallel machines with common due date, European Journal of Operational Research 284(1): 67–74.

[15] Chen, X., Sterna, M., Han, X. and Błażewicz, J. (2016). Scheduling on parallel identical machines with late work criterion: Offline and online cases, Journal of Scheduling 19(6): 729–736.

[16] Gerstl, E., Mor, B. and Mosheiov, G. (2019). Scheduling on a proportionate flowshop to minimise total late work, International Journal of Production Research 57(2): 531–543.

[17] Glover, F. (1989). Tabu search. Part I, ORSA Journal on Computing 1(3): 190–206.

[18] Glover, F. (1990). Tabu search. Part II, ORSA Journal on Computing 2(1): 4–32.

[19] Graham, R., Lawler, E., Lenstra, J. and Kan, A.R. (1979). Optimization and approximation in deterministic sequencing and scheduling: A survey, Annals of Discrete Mathematics 5: 287–326.

[20] Hariri, A.M., Potts, C.N. and Van Wassenhove, L.N. (1995). Single machine scheduling to minimize total weighted late work, ORSA Journal on Computing 7(2): 232–242.

[21] Holland, J.H. (1962). Outline for a logical theory of adaptive systems, Journal of the ACM 9(3): 297–314.

[22] Kovalyov, M.Y., Potts, C.N. and Van Wassenhove, L.N. (1994). A fully polynomial approximation scheme for scheduling a single machine to minimize total weighted late work, Mathematics of Operations Research 19(1): 86–93.

[23] Kundakcı, N. and Kulak, O. (2016). Hybrid genetic algorithms for minimizing makespan in dynamic job shop scheduling problem, Computers Industrial Engineering 96: 31–51.

[24] Labib, N.S., Danoy, G., Musial, J., Brust, M.R. and Bouvry, P. (2019). Internet of unmanned aerial vehicles—A multilayer low-altitude airspace model for distributed UAV traffic management, Sensors 19(21): 4779.

[25] Leung, J.Y. (2004). Minimizing total weighted error for imprecise computation tasks and related problems, in J.Y. Leung (Ed.), Handbook of Scheduling: Algorithms, Models, and Performance Analysis, Chapman and Hall/CRC, Boca Raton, FL.

[26] Lin, B.M. and Hsu, S. (2005). Minimizing total late work on a single machine with release and due dates, SIAM Conference on Computational Science and Engineering, Orlando, FL, USA.

[27] Lin, B.M., Lin, F. and Lee, R. (2006). Two-machine flow-shop scheduling to minimize total late work, Engineering Optimization 38(04): 501–509.

[28] Lopez-Loces, M.C., Musial, J., Pecero, J.E., Fraire-Huacuja, H.J., Blazewicz, J. and Bouvry, P. (2016). Exact and heuristic approaches to solve the Internet shopping optimization problem with delivery costs, International Journal of Applied Mathematics and Computer Science 26(2): 391–406, DOI: 10.1515/amcs-2016-0028.

[29] Pesch, E. and Sterna, M. (2009). Late work minimization in flow shops by a genetic algorithm, Computers Industrial Engineering 57(4): 1202–1209.

[30] Piroozfard, H., Wong, K.Y. and Wong, W.P. (2018). Minimizing total carbon footprint and total late work criterion in flexible job shop scheduling by using an improved multi-objective genetic algorithm, Resources, Conservation and Recycling 128: 267–283.

[31] Potts, C.N. and Van Wassenhove, L.N. (1992a). Approximation algorithms for scheduling a single machine to minimize total late work, Operations Research Letters 11(5): 261–266.

[32] Potts, C.N. and Van Wassenhove, L.N. (1992b). Single machine scheduling to minimize total late work, Operations Research 40(3): 586–595.

[33] Rybarczyk, A., Hertz, A., Kasprzak, M. and Blazewicz, J. (2017). Tabu search for the RNA partial degradation problem, International Journal of Applied Mathematics and Computer Science 27(2): 401–415, DOI: 10.1515/amcs-2017-0028.

[34] Servranckx, T. and Vanhoucke, M. (2019). A tabu search procedure for the resource-constrained project scheduling problem with alternative subgraphs, European Journal of Operational Research 273(3): 841–860.

[35] Sterna, M. (2007). Metaheuristics for late work minimization in two-machine flow shop with common due date, Computers Industrial Engineering 52(2): 210–228.

[36] Sterna, M. (2011). A survey of scheduling problems with late work criteria, Omega 39(2): 120–129.

[37] Talbi, E.-G. (2009). Metaheuristics: From Design to Implementation, Wiley Sons, Hoboken, NJ.

[38] Whitley, D. (1994). A genetic algorithm tutorial, Statistics and Computing 4(2): 65–85.

[39] Wu, C.-C., Yin, Y., Wu, W.-H., Chen, H.-M. and Cheng, S.-R. (2016). Using a branch-and-bound and a genetic algorithm for a single-machine total late work scheduling problem, Soft Computing 20(4): 1329–1339.

[40] Yan, F., Dridi, M. and El Moudni, A. (2013). An autonomous vehicle sequencing problem at intersections, International Journal of Applied Mathematics and Computer Science 23(1): 183–200, DOI: 10.2478/amcs-2013-0015.