Single-machine scheduling with dynamic arrivals: Decomposition results and an improved algorithm

Single-machine scheduling with dynamic arrivals: Decomposition results and an improved algorithm

0.00 Avg rating0 Votes
Article ID: iaor1997554
Country: United States
Volume: 43
Issue: 5
Start Page Number: 709
End Page Number: 720
Publication Date: Aug 1996
Journal: Naval Research Logistics
Authors: , ,
Abstract:

This article considers the single-machine dynamic scheduling problem where the jobs have different arrival times and the objective is to minimize the sum of completion times. This problem is known to be strongly NP-hard. The authors develop decomposition results for this problem such that a large problem can be solved by combining optimal solutions for several smaller problems. The decomposition results can be used with any implicit enumeration method to develop an optimal algorithm. The present computational experiment indicates that the computational efficiency of the currently best available branch-and-bound algorithm can be improved with the use of our decomposition results.

Reviews

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