Single-machine scheduling with a common due window

W. K. Yeung, Ceyda Oguz, Edwin Tai Chiu Cheng

Research output: Journal article publicationJournal articleAcademic researchpeer-review

Abstract

We study several single-machine non-preemptive scheduling problems to minimize the sum of weighted earliness-tardiness, weighted number of early and tardy jobs, common due window location, and flowtime penalties. We allow the due window location to be either a decision variable or a given parameter. We assume that the due window location has a tolerance and the window size is a given parameter. We further make the assumption that the ratios of the job processing times to the earliness-tardiness weights are agreeable for the first problem. We propose pseudo-polynomial dynamic programming algorithms to optimally solve the problems. We also provide polynomial time algorithms for several special cases. Scope and purpose The widespread use of Just-In-Time philosophy in manufacturing to eliminate inventories leads to a new class of scheduling problems in which the earliness and/or number of early jobs are penalized as well as the tardiness and/or tardy jobs. In this type of environments, the jobs are sometimes associated with a period of time within which they incur no penalty since the customers will generally allow a time interval for the delivery of the products. This time period is called a due window. There are a variety of applications with due windows in factory automation, production maintenance, and so on. In this paper, we consider the common due window problems to minimize the weighted earliness-tardiness, weighted number of early-tardy jobs and weighted flowtime on a single machine. The main contributions of this paper are identifying the computational complexity of the problems, developing dynamic programming algorithms to optimally solve them, and providing efficient and exact polynomial algorithms for the special cases.
Original languageEnglish
Pages (from-to)157-175
Number of pages19
JournalComputers and Operations Research
Volume28
Issue number2
DOIs
Publication statusPublished - 1 Feb 2000

Keywords

  • Due window
  • Dynamic programming
  • Earliness-tardiness
  • Early-tardy jobs
  • Flowtime
  • Single-machine scheduling

ASJC Scopus subject areas

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

Cite this