An Efficient Tabu Search Approach for the Two-Machien Preemptive Open Shop Scheduling Problem

摘要

This article considers the problem of scheduling two-machine preemptive open sheep 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 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 tabu search approach. Diversification and intensification strategies are suggested. Finally, computational experiments are conducted to demonstrate the performance of the proposed approach. The rusts show that the proposed tabu search approach finds extremely high quality solutions within a reasonable amount of time.