Scheduling permutation flow shops using the Lagrangian relaxation technique

Guandong Liu, Peter Luh and Richard Resch

Annals of Operations Research, 1997, vol. 70, issue 0, 189 pages

Abstract: Flow shop is a common manufacturing environment for the production of multiple types of similar products. A permutation flow shop is a special kind of flow shop where processing sequences at all production stages are physically constrained to be the same. These "identical sequence constraints" couple the processing sequences of various production stages, making it difficult to have a separable problem formulation which is critical for obtaining near-optimal schedules by using the Lagrangian relaxation technique. This paper presents a novel "separable" integer programming formulation for permutation flow shops. The objective is to minimize penalties on production tardiness and on releasing raw materials too early subject to relevant constraints. After coupling constraints are relaxed by using Lagrange multipliers, the problem is decomposed into individual subproblems that can be solved without much enumeration. The multipliers are updated at the high level by using the recently developed Reduced Complexity Bundle Method. The "inherent duality gap" is proved to exist in general, implying that the quality of a schedule generated may be higher than what is indicated by its relative duality gap. Testing results show that the algorithm can be effectively used to solve practical scheduling problems. Copyright Kluwer Academic Publishers 1997

Keywords: Scheduling; permutation flow shop; Lagrangian relaxation; inherent duality gap (search for similar items in EconPapers)
Date: 1997
References: Add references at CitEc
Citations:

Downloads: (external link)
http://hdl.handle.net/10.1023/A:1018970020599 (text/html)
Access to full text is restricted to subscribers.

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:spr:annopr:v:70:y:1997:i:0:p:171-189:10.1023/a:1018970020599

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10479

DOI: 10.1023/A:1018970020599

Access Statistics for this article

Annals of Operations Research is currently edited by Endre Boros

More articles in Annals of Operations Research from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().