IDEAS home Printed from https://ideas.repec.org/a/spr/annopr/v70y1997i0p171-18910.1023-a1018970020599.html
   My bibliography  Save this article

Scheduling permutation flow shops using the Lagrangian relaxation technique

Author

Listed:
  • Guandong Liu
  • Peter Luh
  • Richard Resch

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

Suggested Citation

  • Guandong Liu & Peter Luh & Richard Resch, 1997. "Scheduling permutation flow shops using the Lagrangian relaxation technique," Annals of Operations Research, Springer, vol. 70(0), pages 171-189, April.
    • Handle: RePEc:spr:annopr:v:70:y:1997:i:0:p:171-189:10.1023/a:1018970020599
    DOI: 10.1023/A:1018970020599
    as

    Download full text from publisher

    File URL: http://hdl.handle.net/10.1023/A:1018970020599
    Download Restriction: Access to full text is restricted to subscribers.
    File URL: https://libkey.io/10.1023/A:1018970020599?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:spr:annopr:v:70:y:1997:i:0:p:171-189:10.1023/a:1018970020599. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    We have no bibliographic references for this item. You can help adding them by using this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.