An efficient tabu search approach for the two-machine preemptive open shop scheduling problem

This article considers the problem of scheduling two-machine preemptive open shops to minimize total tardiness. The problem is known to be NP-hard. An optimal timing algorithm is presented to determine the completion time of each job in a given job completion sequence. Then a tabu search (TS) approach is adopted together with the optimal timing algorithm to generate job completion sequences and final schedules. An efficient heuristic is developed to obtain an initial solution for the TS approach. Diversification and intensification strategies are suggested. Finally, computational experiments are conducted to demonstrate the performance of the proposed approach. The results show that the proposed TS approach finds extremely high-quality solutions within a reasonable amount of time.