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

Journal of Industrial Engineering International

دوره 8، شماره 1، فروردین 2012   

نویسندگان

Samaneh Noori-Darvish¹؛ Reza Tavakkoli-Moghaddam^{* 2}

¹Department of Industrial Engineering, Allame Mohades Noori University, PC: 46415-451, Noor, Iran

²Department of Industrial Engineering, College of Engineering, University of Tehran, PC: 14399-57131, Tehran, Iran

چکیده

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.

کلیدواژه‌ها

Open shop scheduling؛ Total tardiness؛ Makespan؛ Sequence-dependent setup times؛ NSGA-II؛ SPEA-II