Please use this identifier to cite or link to this item: http://hdl.handle.net/10397/30882
Title: Minimizing weighted number of early and tardy jobs with a common due window involving location penalty
Authors: Yeung, WK
Oguz, C
Cheng, TCE 
Keywords: Due window
Dynamic programming
Early-tardy job
NP-completeness
Single machine scheduling
Issue Date: 2001
Publisher: Springer
Source: Annals of operations research, 2001, v. 108, no. 1-4, p. 33-54 How to cite?
Journal: Annals of operations research 
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.
URI: http://hdl.handle.net/10397/30882
ISSN: 0254-5330
EISSN: 1572-9338
DOI: 10.1023/A:1016094508744
Appears in Collections:Journal/Magazine Article

Access
View full-text via PolyU eLinks SFX Query
Show full item record

SCOPUSTM   
Citations

22
Last Week
0
Last month
0
Citations as of Sep 23, 2017

WEB OF SCIENCETM
Citations

22
Last Week
0
Last month
0
Citations as of Sep 20, 2017

Page view(s)

47
Last Week
1
Last month
Checked on Sep 24, 2017

Google ScholarTM

Check

Altmetric



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.