Bi-criterion single-machine scheduling and duewindow assignment with common flow allowances and resource-dependent processing times

Yunqiang Yin, Du Juan Wang, T. C.E. Cheng, Chin Chia Wu

Research output: Journal article publicationJournal articleAcademic researchpeer-review

20 Citations (Scopus)


This paper addresses single-machine scheduling and due-window assignment with common flow allowances and resource-dependent processing times. Due-window assignment with common flow allowances means that each job has a job-dependent due window, the start time and finish time of which are equal to its actual processing time plus individual job-independent parameters shared by all the jobs, respectively. The processing time of each job can be controlled by extra resource allocation as a linear function of the amount of a common continuously divisible resource allocated to the job. Two criteria are considered, where one criterion is an integrated cost consisting of job earliness, weighted number of tardy jobs, and due-window assignment cost, while the other criterion is the resource consumption cost. Four different models are considered for treating the two criteria. It is shown that the problem under the model where the two criteria are integrated into a single criterion is polynomially solvable, while the problems under the other three models are all NP-hard and an optimal solution procedure is developed for them. Two polynomially solvable cases are also identified and investigated. Finally, numerical studies with randomly generated instances are conducted to assess the performance of the proposed algorithms.

Original languageEnglish
Pages (from-to)1169-1183
Number of pages15
JournalJournal of the Operational Research Society
Issue number9
Publication statusPublished - 1 Dec 2016


  • Controllable processing times
  • Due-window assignment
  • Resource allocation
  • Scheduling

ASJC Scopus subject areas

  • Management Information Systems
  • Strategy and Management
  • Management Science and Operations Research
  • Marketing

Cite this