Heuristics for a coupled-operation scheduling problem

Heuristics for a coupled-operation scheduling problem

0.00 Avg rating0 Votes
Article ID: iaor20083044
Country: United Kingdom
Volume: 58
Issue: 10
Start Page Number: 1375
End Page Number: 1388
Publication Date: Oct 2007
Journal: Journal of the Operational Research Society
Authors: ,
Keywords: combinatorial optimization, heuristics, heuristics: local search, heuristics: tabu search
Abstract:

In this paper, we study a strongly NP-hard single machine scheduling problem in which each job consists of two operations that are separated by a time delay which lies within a specified range. The objective is to minimize the makespan. Determining the feasibility and, if applicable, makespan of any proposed permutation of the operations is non-trivial, requiring a longest path algorithm with O(n2) complexity for each permutation. Several heuristic algorithms are proposed: a deterministic and randomized construction algorithm, three descent algorithms and two reactive tabu search algorithms. The local search algorithms use a first improvement neighbourhood and mainly visit only feasible solutions within the search space. Results of extensive computational tests are reported, showing that the heavy computational burden of testing potential solutions renders the local search algorithms uncompetitive in comparison to the construction algorithms. The iterated descent algorithm performs least well.

Reviews

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