Common due date assignment and scheduling with ready times

Edwin Tai Chiu Cheng, Z. L. Chen, N. V. Shakhlevich

Research output: Journal article publicationJournal articleAcademic researchpeer-review

26 Citations (Scopus)

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 languageEnglish
Pages (from-to)1957-1967
Number of pages11
JournalComputers and Operations Research
Volume29
Issue number14
DOIs
Publication statusPublished - 1 Jan 2002

Keywords

  • Due date assignment
  • Earliness
  • Single-machine scheduling
  • Tardiness

ASJC Scopus subject areas

  • Computer Science(all)
  • Modelling and Simulation
  • Management Science and Operations Research

Cite this