Single machine earliness–tardiness scheduling with resource-dependent release dates

Single machine earliness–tardiness scheduling with resource-dependent release dates

0.00 Avg rating0 Votes
Article ID: iaor20031855
Country: Netherlands
Volume: 142
Issue: 1
Start Page Number: 52
End Page Number: 69
Publication Date: Oct 2002
Journal: European Journal of Operational Research
Authors: , ,
Keywords: heuristics, programming: dynamic
Abstract:

This paper deals with the single machine earliness and tardiness scheduling problem with a common due date and resource-dependent release dates. It is assumed that the cost of resource consumption of a job is a non-increasing linear function of the job release date, and this function is common for all jobs. The objective is to find a schedule and job release dates that minimize the total resource consumption, and earliness and tardiness penalties. It is shown that the problem is NP-hard in the ordinary sense even if the due date is unrestricted (the number of jobs that can be scheduled before the due date is unrestricted). An exact dynamic programming algorithm for small and medium size problems is developed. A heuristic algorithm for large-scale problems is also proposed and the results of a computational comparison between heuristic and optimal solutions are discussed.

Reviews

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