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. We consider the single machine due date assignment problem for scheduling jobs which are ready for processing at different times. The problem under consideration arises in production planning and scheduling concerning the setting of appropriate due dates for a number of customer orders arriving over time. Most of the earlier publications on this subject assumed that the jobs are ready for processing simultaneously. This assumption is too restrictive for real-life production systems where jobs arrive at different times. We show that the problem with unequal ready times is NP-hard and develop fast heuristic algorithms for it, and exact algorithms for two special cases.
Original language | English |
---|---|
Pages (from-to) | 1957-1967 |
Number of pages | 11 |
Journal | Computers and Operations Research |
Volume | 29 |
Issue number | 14 |
DOIs | |
Publication status | Published - 1 Jan 2002 |
Keywords
- Due date assignment
- Earliness
- Single-machine scheduling
- Tardiness
ASJC Scopus subject areas
- General Computer Science
- Modelling and Simulation
- Management Science and Operations Research