Minimizing Weighted Number of Early and Tardy Jobs with a Common Due Window Involving Location Penalty

W. K. Yeung, Ceyda Oǧuz, Edwin Tai Chiu Cheng

Research output: Journal article publicationJournal articleAcademic researchpeer-review

27 Citations (Scopus)

Abstract

This paper studies a single machine scheduling problem to minimize the weighted number of early and tardy jobs with a common due window. There are n non-preemptive and simultaneously available jobs. Each job will incur an early (tardy) penalty if it is early (tardy) with respect to the common due window under a given schedule. The window size is a given parameter but the window location is a decision variable. The objective of the problem is to find a schedule that minimizes the weighted number of early and tardy jobs and the location penalty. We show that the problem is NP-complete in the ordinary sense and develop a dynamic programming based pseudo-polynomial algorithm. We conduct computational experiments, the results of which show that the performance of the dynamic algorithm is very good in terms of memory requirement and CPU time. We also provide polynomial time algorithms for two special cases.
Original languageEnglish
Pages (from-to)33-54
Number of pages22
JournalAnnals of Operations Research
Volume108
Issue number1-4
DOIs
Publication statusPublished - 1 Dec 2001

Keywords

  • Due window
  • Dynamic programming
  • Early-tardy job
  • NP-completeness
  • Single machine scheduling

ASJC Scopus subject areas

  • Decision Sciences(all)
  • Management Science and Operations Research

Cite this