Two‐machine flow shop scheduling with common due window to minimize weighted number of early and tardy jobs

Wing‐Kwan Yeung, Ceyda Oğuz and Tai‐Chiu Edwin Cheng

Naval Research Logistics (NRL), 2009, vol. 56, issue 7, 593-599

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 Johnsos 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. © 2009 Wiley Periodicals, Inc. Naval Research Logistics, 2009

Date: 2009
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://doi.org/10.1002/nav.20356

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:wly:navres:v:56:y:2009:i:7:p:593-599

Access Statistics for this article

More articles in Naval Research Logistics (NRL) from John Wiley & Sons
Bibliographic data for series maintained by Wiley Content Delivery ().