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

Placeholder

School / College / Institute

Program

KU-Authors

KU Authors

Co-Authors

Yeung, Wing-Kwan
Cheng, Tai Chiu Edwin

Publication Date

Language

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

item.page.datauri

Link

Rights

Copyrights Note

Endorsement

Review

Supplemented By

Referenced By

0

Views

0

Downloads

View PlumX Details