A study on open shop scheduling to minimise total tardiness

This paper deals with open shop scheduling to minimise total tardiness. Contrary to other scheduling problems (i.e., flow and job shops), the formulation of the open shop is given far less attention in the literature. Therefore, we intend to fulfil this gap by the presentation of four different mixed integer linear programming models. We compare the models on the basis of their complexity sizes. Furthermore, we propose two metaheuristics based on genetic algorithm and variable neighbourhood search. We exhaustively explore the effect of different operators and parameters on the performance of genetic algorithm by means of Taguchi method. Two computational experiments are conducted to evaluate the models and algorithms for performance. The first one includes small-sized instances by which the models and general performance of the algorithms are examined. The second one consists of three well-known benchmarks by which we further evaluate the algorithms. The results show the effectiveness of the proposed models and algorithms.