Scheduling to minimize the total compression and late costs

Scheduling to minimize the total compression and late costs

0.00 Avg rating0 Votes
Article ID: iaor19982714
Country: United States
Volume: 45
Issue: 1
Start Page Number: 83
End Page Number: 98
Publication Date: Feb 1998
Journal: Naval Research Logistics
Authors: , , ,
Keywords: programming: dynamic
Abstract:

We consider a single-machine scheduling model in which the job processing times are controllable variables with linear costs. The objective is to minimize the sum of the cost incurred in compressing job processing times and the cost associated with the number of late jobs. The problem is shown to be NP-hard even when the due dates of all jobs are identical. We present a dynamic programming solution algorithm and a fully polynomial approximation scheme for the problem. Several efficient heuristics are proposed for solving the problem. Computational experiments demonstrate that the heuristics are capable of producing near-optimal solutions quickly.

Reviews

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