IDEAS home Printed from https://ideas.repec.org/a/spr/annopr/v76y1998i0p233-25910.1023-a1018948621875.html
   My bibliography  Save this article

Job shop scheduling with group-dependent setups, finite buffers, and long time horizon

Author

Listed:
  • Peter Luh
  • Ling Gou
  • Yuanhui Zhang
  • Takaaki Nagahora
  • Makoto Tsuji
  • Kiyoshi Yoneda
  • Tetsuo Hasegawa
  • Yuji Kyoya
  • Toshiyuki Kano

Abstract

Scheduling is a key factor for manufacturing productivity. Effective scheduling can improve on-time delivery of products, reduce inventory, cut lead times, and improve the utilization of bottleneck resources. This study was motivated by the design and implementation of a scheduling system for the manufacturing of Toshiba's gas insulated switchgears. The manufacturing is characterized by significant machine setup times, strict local buffer capacities, the option of choosing a few alternative processing routes, and long horizon as compared to the time resolution required. This problem has been recognized to be extremely difficult because of the combinatorial nature of integer optimization and the large size of the real problem. Our goal is thus to obtain near-optimal schedules with quantifiable quality in a computationally efficient manner. To achieve this goal, a novel integer optimization formulation with a separable structure is developed, and a solution methodology based on a combined Lagrangian relaxation, dynamic programming, and heuristics is developed. The method has been implemented using the object-oriented programming language C++, and numerical testing shows that the method generates high-quality schedules in a timely fashion to achieve on-time delivery of products and low inventory. Through explicit consideration of setups, tanks with the same processing requirements tend to be processed together to avoid excessive setups. The integrated treatment of machines and buffers facilitates the smooth flow of parts through the system. The embedded routing selection mechanism also balances the load among candidate routes. Finally, the newly developed "time step reduction technique" implicitly establishes two time scales to reduce computational requirements without much loss of modeling accuracy and scheduling performance, thereby enabling the resolution of long horizon problems with controllable computational requirements. Copyright Kluwer Academic Publishers 1998

Suggested Citation

  • Peter Luh & Ling Gou & Yuanhui Zhang & Takaaki Nagahora & Makoto Tsuji & Kiyoshi Yoneda & Tetsuo Hasegawa & Yuji Kyoya & Toshiyuki Kano, 1998. "Job shop scheduling with group-dependent setups, finite buffers, and long time horizon," Annals of Operations Research, Springer, vol. 76(0), pages 233-259, January.
    • Handle: RePEc:spr:annopr:v:76:y:1998:i:0:p:233-259:10.1023/a:1018948621875
    DOI: 10.1023/A:1018948621875
    as

    Download full text from publisher

    File URL: http://hdl.handle.net/10.1023/A:1018948621875
    Download Restriction: Access to full text is restricted to subscribers.
    File URL: https://libkey.io/10.1023/A:1018948621875?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.

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. L Tang & H Xuan, 2006. "Lagrangian relaxation algorithms for real-time hybrid flowshop scheduling with finite intermediate buffers," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 57(3), pages 316-324, March.
    2. N Nekoiemehr & G Moslehi, 2011. "Minimizing the sum of maximum earliness and maximum tardiness in the single-machine scheduling problem with sequence-dependent setup time," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 62(7), pages 1403-1412, July.
    3. Luo, Xiaochuan & Chu, Chengbin, 2007. "A branch-and-bound algorithm of the single machine schedule with sequence-dependent setup times for minimizing maximum tardiness," European Journal of Operational Research, Elsevier, vol. 180(1), pages 68-81, July.
    4. Anne Benoit & Mathias Coqblin & Jean-Marc Nicod & Veronika Rehn-Sonigo, 2016. "Optimizing memory allocation for multistage scheduling including setup times," Journal of Scheduling, Springer, vol. 19(6), pages 641-658, December.
    5. Neumann, Klaus & Schwindt, Christoph & Trautmann, Norbert, 2005. "Scheduling of continuous and discontinuous material flows with intermediate storage restrictions," European Journal of Operational Research, Elsevier, vol. 165(2), pages 495-509, September.

    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:76:y:1998:i:0:p:233-259:10.1023/a:1018948621875. 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.