Minimizing the total tardiness and makespan in an open shop scheduling problem with sequence-dependent setup times

Subject Areas : Mathematical Optimization

Samaneh Noori-Darvish ¹ , Reza Tavakkoli-Moghaddam ²

1 - Department of Industrial Engineering, Allame Mohades Noori University, PC: 46415-451, Noor, Iran
2 - Department of Industrial Engineering, College of Engineering, University of Tehran, PC: 14399-57131, Tehran, Iran

Received: 2020-10-01 Accepted : 2020-10-01 Published : 2012-01-01

Keywords: NSGA-II, makespan, Total tardiness, Sequence-dependent setup times, Open shop scheduling, SPEA-II,

Abstract :

We consider an open shop scheduling problem with setup and processing times separately such that not only the setup times are dependent on the machines, but also they are dependent on the sequence of jobs that should be processed on a machine. A novel bi-objective mathematical programming is designed in order to minimize the total tardiness and the makespan. Among several multi-objective decision making (MODM) methods, an interactive one, called the TH method is applied for solving small-sized instances optimally and obtaining Pareto-optimal solutions by the Lingo software. To achieve Pareto-optimal sets for medium to large-sized problems, an improved non-dominated sorting genetic algorithm II (NSGA-II) is presented that consists of a heuristic method for obtaining a good initial population. In addition, by using the design of experiments (DOE), the efficiency of the proposed improved NSGA-II is compared with the efficiency of a well-known multi-objective genetic algorithm, namely SPEAII. Finally, the performance of the improved NSGA-II is examined in a comparison with the performance of the traditional NSGA-II.