A fuzzy multi-objective tabu-search method for a new bi-objective open shop scheduling problem

This paper proposes a novel, bi-objective mixed-integer mathematical programming for an open shop scheduling problem (OSSP) that minimizes the mean tardiness and the mean completion time. To obtain the efficient (Pareto-optimal) solutions, a fuzzy multi-objective decision making (MODM) approach is applied. By the use of this approach, the related auxiliary single objective formulation can be achieved. Since the OSSP are known as a class of NP-hard problems, a tabu search (TS) method is thus used to solve several medium to large-sized instances in reasonable runtime. The efficiency of the results obtained by the proposed TS for small, medium and large-sized instances is evaluated by considering the corresponding overall satisfactory level of all objectives. Futhermore, the adaptability of the yielded solutions of the proposed TS for the small-sized instances is evaluated by comparing the results reported by the LINGO software. Several experiments on different-sized test problems are considered, and the related results show the ability of the proposed TS algorithm to converge to the efficient solutions.