document: Single machine earliness-tardiness scheduling with resource-dependent release dates 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 -LRB- the number of jobs that can be scheduled before the due date is unrestricted -RRB- . An exact dynamic programming -LRB- DP -RRB- 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
doc_bio_tags: O O O O O O O O O O O O O O O O O O O O O O B I I O O O O O O O O O O O O O O O O O O O B I I O O B I I O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O B I I O O O O B I O O O O O O O O O O O O O O O O O O O O