Abstract
Jobs need to be scheduled on identical parallel machines and are subjected to machine eligibility restrictions and various complex sequence constraints with the goal of makespan minimization. A mathematical formulation as a Mixed Integer Linear Programming (MILP) is elaborated using two decision variables. The formulation is solved using Integer Programming (IP) solver, which is NP-hard, and there are high chances of not finding an optimal/feasible solution for a bigger data set in the stipulated time. The current article proposes job scheduling using the evolutionary computing approach, specifically the Genetic Algorithm (GA). Simulation experiments are conducted for various scenarios of jobs and machines subjected to different complex constraints. The result of the proposed GA is in good agreement with the results obtained from the IP solver and is achieved at a significantly reduced computational time, especially when a larger number of jobs and machines are involved.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Georgiadis GP, Elekidis AP, Georgiadis MC (2019) Optimization-based scheduling for the process industries: from theory to real-life industrial applications. Processes 7(7). https://doi.org/10.3390/pr7070438
Skutella M, Uetz M (2005) Stochastic machine scheduling with precedence constraints. SIAM J Comput 34(4):788–802. https://doi.org/10.1137/S0097539702415007
Lin L, Gen M (2018) Hybrid evolutionary optimisation with learning for production scheduling: state-of-the-art survey on algorithms and applications. Int J Prod Res 56(1–2):193–223. https://doi.org/10.1080/00207543.2018.1437288
Eiben A, Smith J (2015) Introduction to evolutionary computing. Natural computing series. Springer Berlin Heidelberg, Berlin, Heidelberg. https://doi.org/10.1007/978-3-662-44874-8
Pinedo ML (2008) Scheduling: theory, algorithms, and systems. Springer. https://doi.org/10.1007/978-0-387-78935-4
Kurz ME, Askin RG (2001) Heuristic scheduling of parallel machines with sequence-dependent set-up times. Int J Prod Res 39(16):3747–3769. https://doi.org/10.1080/00207540110064938
Liu C (2013) A hybrid genetic algorithm to minimize total tardiness for unrelated parallel machine scheduling with precedence constraints. Math Probl Eng 2013:1–11. https://doi.org/10.1155/2013/537127
Lee JH, Yu JM, Lee DH (2013) A tabu search algorithm for unrelated parallel machine scheduling with sequence- and machine-dependent setups: minimizing total tardiness. Int J Adv Manuf Technol 69(9–12):2081–2089. https://doi.org/10.1007/s00170-013-5192-6
Chen N, Kang W, Kang N, Qi Y, Hu H (2022) Order processing task allocation and scheduling for e-order fulfilment. Int J Prod Res 60(13):4253–4267. https://doi.org/10.1080/00207543.2021.2018140
Vallada E, Ruiz R (2012) Scheduling unrelated parallel machines with sequence dependent setup times and weighted earliness-tardiness minimization. In: Just-in-time systems, pp. 67–90. No. January 2012 in Springer optimization and its applications. Springer, New York. https://doi.org/10.1007/978-1-4614-1123-9
Afzalirad M, Rezaeian J (2016) Resource-constrained unrelated parallel machine scheduling problem with sequence dependent setup times, precedence constraints and machine eligibility restrictions. Comput Ind Eng 98:40–52. https://doi.org/10.1016/j.cie.2016.05.020
Vallada E, Ruiz R (2011) A genetic algorithm for the unrelated parallel machine scheduling problem with sequence dependent setup times. Eur J Oper Res 211(3):612–622. https://doi.org/10.1016/j.ejor.2011.01.011
Edis EB, Ozkarahan I (2011) A combined integer/constraint programming approach to a resource-constrained parallel machine scheduling problem with machine eligibility restrictions. Eng Optim 43(2):135–157. https://doi.org/10.1080/03052151003759117
Gokhale R, Mathirajan M (2012) Scheduling identical parallel machines with machine eligibility restrictions to minimize total weighted flowtime in automobile gear manufacturing. Int J Adv Manuf Technol 60(9–12):1099–1110. https://doi.org/10.1007/s00170-011-3653-3
AK B, Koc E (2012) A guide for genetic algorithm based on parallel machine scheduling and flexible job-shop scheduling. Procedia Soc Behav Sci 62:817–823. https://doi.org/10.1016/j.sbspro.2012.09.138
Yeh WC, Lai PJ, Lee WC, Chuang MC (2014) Parallel-machine scheduling to minimize makespan with fuzzy processing times and learning effects. Inf Sci 269:142–158. https://doi.org/10.1016/j.ins.2013.10.023
Bathrinath S, Sankar SS, Ponnambalam SG, Kannan BKV (2013) Bi-objective optimization in identical parallel machine scheduling problem. In: Panigrahi BK, Suganthan PN, Das S, Dash SS (eds) Swarm, evolutionary, and memetic computing. Springer International Publishing, Cham, pp 377–388
Van Khanh B, Van Hop N (2021) Genetic algorithm with initial sequence for parallel machines scheduling with sequence dependent setup times based on earliness-tardiness. J Ind Prod Eng 38(1):18–28. https://doi.org/10.1080/21681015.2020.1829111
Guzman E, Andres B, Poler R (2022) Matheuristic algorithm for job-shop scheduling problem using a disjunctive mathematical model. Computers 11(1). https://doi.org/10.3390/computers11010001
Joo CM, Kim BS (2012) Non-identical parallel machine scheduling with sequence and machine dependent setup times using meta-heuristic algorithms. Ind Eng Manage Syst 11(1):114–122. https://doi.org/10.7232/iems.2012.11.1.114
Yeh WC, Chuang MC, Lee WC (2015) Uniform parallel machine scheduling with resource consumption constraint. Appl Math Model 39(8):2131–2138. https://doi.org/10.1016/j.apm.2014.10.012
Lee WC, Chuang MC, Yeh WC (2012) Uniform parallel-machine scheduling to minimize makespan with position-based learning curves. Comput Ind Eng 63(4):813–818. https://doi.org/10.1016/j.cie.2012.05.003
Afzalirad M, Rezaeian J (2016) A realistic variant of bi-objective unrelated parallel machine scheduling problem: NSGA-II and MOACO approaches. Applied Soft Comput 50:109–123. https://doi.org/10.1016/j.asoc.2016.10.039
Sawant V (2016) Genetic algorithm for resource constrained project scheduling. Int J Sci Res (IJSR) 5(6):139–146. https://doi.org/10.21275/v5i6.NOV164087
Sarker R, Newton C (2002) A genetic algorithm for solving economic lot size scheduling problem. Comput Ind Eng 42(2):189–198. https://doi.org/10.1016/S0360-8352(02)00027-X
Pongcharoen P, Hicks C, Braiden P, Stewardson D (2002) Determining optimum genetic algorithm parameters for scheduling the manufacturing and assembly of complex products. Int J Prod Econ 78(3):311–322. https://doi.org/10.1016/S0925-5273(02)00104-4
Coello CC, Lamont GB, van Veldhuizen DA (2007) Evolutionary algorithms for solving multi-objective problems. Genetic and evolutionary computation series. Springer US, Boston, MA (2007). https://doi.org/10.1007/978-0-387-36797-2
Coello CAC (1999) A survey of constraint handling techniques used with evolutionary algorithms. Tech. Rep, Laboratorio Nacional de Informática Avanzada
Hasani K, Kravchenko SA, Werner F (2014) Simulated annealing and genetic algorithms for the two-machine scheduling problem with a single server. Int J Prod Res 52(13):3778–3792. https://doi.org/10.1080/00207543.2013.874607
Xia X, Qiu H, Xu X, Zhang Y (2022) Multi-objective workflow scheduling based on genetic algorithm in cloud environment. Inf Sci
Hartmann S (1998) A competitive genetic algorithm for resource-constrained project scheduling. Naval Res Logist (NRL) 45(7):733–750. https://doi.org/10.1002/(SICI)1520-6750(199810)45:7<733::AID-NAV5>3.0.CO;2-C
Gurobi (2021) Gurobi optimization. https://www.gurobi.com/. Accessed on 22 June 2022
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2023 The Author(s), under exclusive license to Springer Nature Singapore Pte Ltd.
About this paper
Cite this paper
Karadgi, S., Hiremath, P.S. (2023). Job Scheduling on Parallel Machines with Precedence Constraints Using Mathematical Formulation and Genetic Algorithm. In: Sharma, S., Subudhi, B., Sahu, U.K. (eds) Intelligent Control, Robotics, and Industrial Automation. RCAAI 2022. Lecture Notes in Electrical Engineering, vol 1066. Springer, Singapore. https://doi.org/10.1007/978-981-99-4634-1_65
Download citation
DOI: https://doi.org/10.1007/978-981-99-4634-1_65
Published:
Publisher Name: Springer, Singapore
Print ISBN: 978-981-99-4633-4
Online ISBN: 978-981-99-4634-1
eBook Packages: Intelligent Technologies and RoboticsIntelligent Technologies and Robotics (R0)