Minimizing total completion time and total deviation of job completion times from a restrictive due-date

Minimizing total completion time and total deviation of job completion times from a restrictive due-date

0.00 Avg rating0 Votes
Article ID: iaor20061687
Country: Netherlands
Volume: 165
Issue: 1
Start Page Number: 20
End Page Number: 33
Publication Date: Aug 2005
Journal: European Journal of Operational Research
Authors:
Keywords: programming: dynamic, programming: multiple criteria
Abstract:

We study a single-machine scheduling problem with the objective of minimizing a linear combination of total job completion times and total deviation of job completion times from a common due-date. The due-date is assumed to be restrictive, i.e., it may be sufficiently small to have an impact on the optimal sequence. When more weight is allocated to total job completion times, the problem is shown to have a polynomial time solution. When more weight is allocated to total completion time deviations from the due-date, the problem is NP-hard in the ordinary sense. For the latter case, we introduce an efficient dynamic programming algorithm, which is shown numerically to perform well in all our tests.

Reviews

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