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

Abstract

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