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

Subject Areas : Mechanical Engineering

Sahar Safaei ¹ , Reihane Naderi ² , Amir Sohrabi ³ , Amin Hatami ⁴

1 - Industrial Management Department Faculty of management and Accounting, Shahid Beheshti University,Tehran, Iran.
2 - Industrial Management Department Faculty of Economics and Management, Semnan University, Iran.
3 - Assistant Professor in Molecular Medicine Department of Molecular Biology, Research Center of Health Reference Laboratory, Ministry of Health and Medical Education,Tehran, Iran.
4 - Business Management Department Faculty of Management and Accounting, Farabi College, University of Tehran, Iran

Received: 2015-05-08 Accepted : 2017-10-31 Published : 2015-12-01

Keywords:

Abstract :

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