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

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journalpeer-review

31 Scopus Citations
View graph of relations

Author(s)

  • W. K. Yeung
  • Ceyda Oǧuz
  • T. C. Edwin Cheng

Detail(s)

Original languageEnglish
Pages (from-to)33-54
Journal / PublicationAnnals of Operations Research
Volume108
Issue number1-4
Publication statusPublished - 2001
Externally publishedYes

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.

Research Area(s)

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

Citation Format(s)

Minimizing Weighted Number of Early and Tardy Jobs with a Common Due Window Involving Location Penalty. / Yeung, W. K.; Oǧuz, Ceyda; Cheng, T. C. Edwin.

In: Annals of Operations Research, Vol. 108, No. 1-4, 2001, p. 33-54.

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journalpeer-review