Publication: Two-machine flow shop scheduling with common due window to minimize weighted number of early and tardy jobs
Program
KU-Authors
KU Authors
Co-Authors
Yeung, Wing-Kwan
Cheng, Tai Chiu Edwin
Publication Date
Language
Type
Embargo Status
Journal Title
Journal ISSN
Volume Title
Alternative Title
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.
Source
Publisher
Wiley
Subject
Operations research, Management science
Citation
Has Part
Source
Naval Research Logistics
Book Series Title
Edition
DOI
10.1002/nav.20356