Please use this identifier to cite or link to this item: http://hdl.handle.net/10397/19936
Title: Two-machine flow shop scheduling with common due window to minimize weighted number of early and tardy jobs
Authors: Yeung, WK
Oguz, C
Cheng, TCE 
Keywords: Due window
Dynamic programming
Early and tardy jobs
Flow shop scheduling
NP-hardness
Issue Date: 2009
Publisher: John Wiley & Sons
Source: Naval research logistics, 2009, v. 56, no. 7, p. 593-599 How to cite?
Journal: Naval research logistics 
Abstract: This article studies two due window scheduling problems to minimize the weighted number of early and tardy jobs in a two-machine flow shop, where the window size is externally determined. These new scheduling models have many practical applications in real life. However, results on these problems have rarely appeared in the literature because of a lack of structural and optimality properties for solving them. In this article, we derive several dominance properties and theorems, including elimination rules and sequencing rules based on Johnson's order, lower bounds on the penalty, and upper bounds on the window location, which help to significantly trim the search space for the problems. We further show that the problems are NP-hard in the ordinary sense only. We finally develop efficient pseudopolynomial dynamic programming algorithms for solving the problems.
URI: http://hdl.handle.net/10397/19936
ISSN: 0894-069X
EISSN: 1520-6750
DOI: 10.1002/nav.20356
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 Oct 11, 2017

WEB OF SCIENCETM
Citations

19
Last Week
0
Last month
0
Citations as of Oct 16, 2017

Page view(s)

44
Last Week
1
Last month
Checked on Oct 22, 2017

Google ScholarTM

Check

Altmetric



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