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.
Job Scheduling on Parallel Machines with Precedence Constraints Using Mathematical Formulation and Genetic Algorithm
Lect. Notes Electrical Eng.
International Conference on Robotics, Control, Automation and Artificial Intelligence ; 2022 November 24, 2022 - November 26, 2022
2023-11-18
13 pages
Article/Chapter (Book)
Electronic Resource
English
An Approach for Scheduling Tasks with Precedence Constraints Based on Similarity Relations
British Library Conference Proceedings | 1995
|Transportation Research Record | 2012
|