Improving the preemptive bound for the one-machine dynamic total completion time scheduling problem

Improving the preemptive bound for the one-machine dynamic total completion time scheduling problem

0.00 Avg rating0 Votes
Article ID: iaor2004183
Country: Netherlands
Volume: 31
Issue: 2
Start Page Number: 142
End Page Number: 148
Publication Date: Mar 2003
Journal: Operations Research Letters
Authors: ,
Keywords: combinatorial analysis
Abstract:

We consider the single machine dynamic total completion time scheduling problem. This problem is known to be NP-hard in the strong sense. The currently best available lower bound for the problem is known to be the optimal solution value of the corresponding preemptive problem which can be computed in O(n log n) time. We propose an improvement on this bound by exploiting the properties of the preemptive solution. The proposed improvement reduces by approximately 44% on the average the gap between the preemptive solution value and the optimal solution value.

Reviews

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