Solving and optimizing a bi-objective open shop scheduling problem by a modified genetic algorithm

This paper presents a new bi-objective mixed-integer linear programming model for open shop scheduling problem. The main constraints of this model are considering independent setup times and sequence-dependent transportation times. Two objectives are presented, minimizing sum of the makespan for all jobs and minimizing sum of the machines' workload. Because of the complexity of this problem, it is known as a NP-hard problem; so, it cannot obtain an optimal solution in a reasonable time by using traditional methods. According to classic approach, some small- and medium- to large-sized instances are generated. For the small-sized ones, the Pareto-optimal solutions are produced exactly, and for the medium- to large-sized instances, we proposed a non-dominated sorting genetic algorithm (NSGA-II). To evaluate the performance of the proposed NSGA-II, the augmented epsilon-constraint method is used for the small-sized instances, and three performance metrics are proposed for the medium- to large-sized instances.