Multi-objective scheduling by maximizing machine preferences for unrelated parallel machines

Year 2020, Volume: 38 Issue: 1, 405 - 419, 27.03.2020

İnci Sarıçiçek

Abstract

This work proposes to use the fitness scores of jobs to machines in unrelated parallel machine scheduling to maximize machine preferences by using the fitness scores of jobs. A bi-objective mathematical model for the unrelated parallel machine problem with sequence dependent setup times is designed to minimize makespan and maximize machine preferences of jobs. Bi-objective Simulated Annealing Algorithm is proposed for solving large sized problems. A Decision Support System designed for solving problems with objective function of the maximizing machine preferences in combination with other common scheduling objective functions for unrelated parallel machine scheduling problems. By using the proposed system, non-dominated solutions are compared and one solution is selected by considering trade-offs among performance measures of the solutions.

Keywords

Unrelated parallel machine scheduling, sequence dependent setup times, machine preferences, simulated annealing, tabu search.

References

• [1] Pinedo, M. 2002. Scheduling: theory, algorithms and systems. Third ed. NewJersey: Prentice all.
• [2] Allahverdi, A., J. N. D. Gupta, and T. Aldowaisan. 1999. “A review of scheduling research involving setup considerations.” Omega, no.27:219-239.
• [3] Allahverdi, A., C. T. Ng, T. C. E. Cheng, and M. Kovalyov. 2008. “A survey of scheduling problems with setup times or costs.” European Journal of Operational Research no.187: 985-1032.
• [4] França, P., M. Gendreau, G. Laporte, and F. Muller. 1996. “A tabu search heuristic for the multiprocessor scheduling problem with sequence dependent setup times.” International Journal of Production Economics 43(2-3):79–89.
• [5] Marsh, J.D. and Montgomery, D.C. (1973) ‘Optimal procedures for scheduling jobs with sequence-dependent changeover times on parallel processors’, AIIE Technical Papers, pp.279-286.
• [6] Guinet, A. 1991. “Textile production systems: A succession of non-identical parallel processor shops.” Journal of the Operational Research Society 42(8):655-671.
• [7] Elmaghraby, S.E, A. Guinet, and K.W. Schellenberger. 1993 “Sequencing on parallel processors: An alternate approach.” OR Technical Report no. 273, Raleigh, NC: North Carolina State University.
• [8] Zhu, Z. and R.B. Heady. 2000. “Minimizing the sum of earliness/ tardiness in multi-machine scheduling: A mixed integer programming approach.” Computers and Industrial Engineering no.38: 297–305.
• [9] Weng, M.X., J. Lu, and H. Ren. 2001. “Unrelated parallel machine scheduling with setup consideration and a total weighted completion time objective.” International Journal of Production Economics no.70: 215–226.
• [10] Kim, C.O. and Shin, H.J. (2003) ‘Scheduling jobs on parallel machines: A restricted tabu search approach’, International Journal of Advanced Manufacturing Technology, Vol 22 No.3, pp.278–287.
• [11] Ravetti, M. G., R.M. Geraldo, L.R. Pedro, and M.P. Panos. 2007. “A scheduling problem with unrelated parallel machines and sequence dependent setups.” International Journal of Operational Research, 2(4):380-399.
• [12] Chen, C-L., and C-L. Chen. 2009. “Hybrid metaheuristics for unrelated parallel machine scheduling with sequence-dependent setup times.” International Journal of Advanced Manufacturing Technology 43(1-2):161-169.
• [13] Tavakkoli Moghaddam, R., F. Taheri, M. Bazzazi, and F.Sassani. 2009. “Design of a genetic algorithm for bi-objective unrelated parallel machines scheduling with sequence-dependent setup times and precedence constraints.” Computers and Operations Research 36(12), 3224-3230.
• [14] Arnaout, J-P., G. Rabadi, and R. Musa. 2010. “A two-stage ant colony optimization algorithm to minimize the makespan on unrelated parallel machines with sequence-dependent setup times.” Journal of Intelligent Manufacturing 21 (6):693-701.
• [15] Vallada, E. and R. Ruiz. 2011. “A genetic algorithm for the unrelated parallel machine scheduling problem with sequence dependent setup times.” European Journal of Operational Research 211(3): 612-622.
• [16] Lin, S-W., C-C. Lu, and K-C. Ying. 2011. “Minimization of total tardiness on unrelated parallel machines with sequence- and machine-dependent setup times under due date constraints.” International Journal of Advanced Manufacturing Technology, 53(1-4):353-361.
• [17] Ying, K-C., Z-J. Lee, and S-W. Lin. 2012. “Makespan minimization for scheduling unrelated parallel machines with setup times.” Journal of Intelligent Manufacturing 23(5): 1795-1803.
• [18] Hsu, C-J., M. Ji, J-Y. Guo, and D-L. Yang. 2013. “Unrelated parallel-machine scheduling problems with aging effects and deteriorating maintenance activities.” Information Sciences, no.253:163-169.
• [19] Naderi-Beni, M., E. Ghobadian, S. Ebrahimnejad, and R. Tavakkoli-Moghaddam. 2014. “Fuzzy bi-objective formulation for a parallel machine scheduling problem with machine eligibility restrictions and sequence-dependent setup times dependent setup times.” International Journal of Production Research 52(19):5799-5822.
• [20] Eroglu, D.Y., H.C. Ozmutlu, and S. Ozmutlu. 2014. “Genetic algorithm with local search for the unrelated parallel machine scheduling problem with sequence-dependent set-up times.” International Journal of Production Research 52(19):5841–5856.
• [21] Afzalirad, M., and J. Rezaeian. 2016. “Design of high-performing hybrid meta-heuristics for unrelated parallel machine scheduling with machine eligibility and precedence constraints.” Engineering Optimization 48(4):706-726.
• [22] Arroyo, J.E.C. and J.Y.T. Leung. 2017. “Scheduling unrelated parallel batch processing machines with non-identical job sizes and unequal ready times.” Computers and Industrial Engineering no.78:117-128.
• [23] Ezugwu, A.E., and F. Akutsah. 2018. “An improved firefly algorithm for the unrelated parallel machines scheduling problem with sequence-dependent setup times”, IEEE Access, Vol.6: 54459- 54478.
• [24] Bektur, G. and T. Saraç. 2019. “A mathematical model and heuristic algorithms for an unrelated parallel machine scheduling problem with sequence-dependent setup times, machine eligibility restrictions and a common server”. Computers and Operations Research, no.103:46–63.
• [25] Fanjul-Peyro, L., R. Ruiz, and F. Perea. 2019. “Reformulations and an exact algorithm for unrelated parallel machine scheduling problems with setup times”. Computers and Operations Research, no.101: 173–182.
• [26] Chuang, M-C., C-J. Liao, and C-W. Chao. 2010. “Parallel machine scheduling with preference of machines”. International Journal of Production Research, 48(14):4139–4152.
• [27] Huang, C-J., and L-M. Liao. 2014. “Parallel machines scheduling with machine preference via agent-based approach”, Applied Mathematics and Computation, no.233:298–309.
• [28] Lin, S-W. and K-C. Ying. 2015. “A multi-point simulated annealing heuristic for solving multiple objective unrelated parallel machine scheduling problems’, International Journal of Production Research, Vol.53 No.4, pp.1065–1076.
• [29] Mishra, K.K. and S. Harit. 2010. “A fast algorithm for finding the non-dominated set in multi objective optimization.” International Journal of Computer Applications, 1(25):35-39.