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

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

0.00 Avg rating0 Votes
Article ID: iaor20042592
Country: United Kingdom
Volume: 30
Issue: 14
Start Page Number: 2081
End Page Number: 2095
Publication Date: Dec 2003
Journal: Computers and Operations Research
Authors:
Keywords: heuristics
Abstract:

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.

Reviews

Required fields are marked *. Your email address will not be published.