Single machine scheduling with a variable common due date and resource-dependent processing times

Chi To Ng, Edwin Tai Chiu Cheng, Mikhail Y. Kovalyov, S. S. Lam

Research output: Journal article publicationJournal articleAcademic researchpeer-review

61 Citations (Scopus)


The problem of scheduling n jobs with a variable common due date on a single machine is studied. It is assumed that the job processing times are non-increasing linear functions of an equal amount of a resource allocated to the jobs. The due date and resource values can be continuous or discrete. The objective is to minimize a linear combination of scheduling, due date assignment and resource consumption costs. The resource consumption cost function may be non-monotonous. Algorithms with O(n2log n) running times are presented for scheduling costs involving earliness/tardiness and number of tardy jobs. Computational experiments show that the algorithms can solve problems with n = 5,000 in less than a minute on a standard PC. We study a problem that combines scheduling, common due date assignment and resource allocation decisions. Due date scheduling is an important area of scheduling research because it focuses on customer satisfaction. Variable common due date applies to situations where several items constitute a single customer's order and the due date for the order can be negotiated. Resource-dependent processing times appear whenever resources can be employed to adjust processing requirements. Polynomial time algorithms are presented for minimizing a linear combination of scheduling, due date assignment and resource consumption costs. Computational experiments demonstrate their efficiency in solving large-scale problem instances.
Original languageEnglish
Pages (from-to)1173-1185
Number of pages13
JournalComputers and Operations Research
Issue number8
Publication statusPublished - 1 Jul 2003


  • Common due date assignment
  • Controllable processing times
  • Single machine scheduling

ASJC Scopus subject areas

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

Cite this