Scheduling of Unrelated Parallel Machines using Two Multi Objective Genetic Algorithms with Sequence-Dependent Setup Times and Precedent Constraints

Abstract: This paper considers the problem of scheduling N jobs on M unrelated parallel machines with sequence-dependent setup times. To better comply with industrial situations, jobs have varying due dates and ready times and there are some precedence relations between them. Furthermore sequence-dependent setup times and anticipatory setups are included in the proposed model. The objective is to determine a schedule that minimizes makespan and number of tardy jobs. The problem is NP-hard, so for obtaining an optimal solution in reasonable computational time, two multi objective genetic algorithms (MOGA) are proposed. To evaluate the proposed algorithms, random test problems are produced in medium and large sizes with tight due dates. After setting the parameters, the performances of these algorithms are evaluated using the concept of data envelopment analysis (DEA), distance method, and a number of non-dominated solutions.Keywords: Genetic algorithm, Makespan, Multi-objective, Parallel machine scheduling, Precedence constraints, Sequence-dependent setup times