Common due date assignment and scheduling with ready times

Common due date assignment and scheduling with ready times

0.00 Avg rating0 Votes
Article ID: iaor20031400
Country: United Kingdom
Volume: 29
Issue: 14
Start Page Number: 1957
End Page Number: 1967
Publication Date: Dec 2002
Journal: Computers and Operations Research
Authors: , ,
Keywords: combinatorial analysis, heuristics
Abstract:

We consider the problem of scheduling a set of nonsimultaneously available jobs on one machine. Each job has a ready time only at or after which the job can be processed. All the jobs have a common due date, which needs to be determined. The problem is to determine a due date and a schedule so as to minimize a total penalty depending on the earliness, tardiness and due date. We show that this problem is strongly NP-hard and give an efficient algorithm that finds an optimal due date and schedule when either the job sequence is predetermined or all jobs have the same processing time. We also propose three approximation algorithms for the general and special cases together with their experimental analysis.

Reviews

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