NP-hardness of the single-variable-resource scheduling problem to minimize the total weighted completion time

NP-hardness of the single-variable-resource scheduling problem to minimize the total weighted completion time

0.00 Avg rating0 Votes
Article ID: iaor20084403
Country: Netherlands
Volume: 178
Issue: 2
Start Page Number: 631
End Page Number: 633
Publication Date: Apr 2007
Journal: European Journal of Operational Research
Authors: , ,
Keywords: computational analysis
Abstract:

Baker and Nuttle studied the following single-variable-resource scheduling problem: sequencing n jobs for processing by a single-resource to minimize a function of job completion times, when the availability of the resource varies over time. When the objective function to be minimized is the total weighted completion time, Baker and Nuttle conjectured that the problem is NP-hard. We show in this note that the conjecture is true.

Reviews

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