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

Peter Luh, Ling Gou, Yuanhui Zhang, Takaaki Nagahora, Makoto Tsuji, Kiyoshi Yoneda, Tetsuo Hasegawa, Yuji Kyoya and Toshiyuki Kano

Annals of Operations Research, 1998, vol. 76, issue 0, 233-259

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

Keywords: job shop scheduling; optimization-based scheduling; Lagrangian relaxation; machines with setups; finite buffers; long time horizon (search for similar items in EconPapers)
Date: 1998
References: Add references at CitEc
Citations: View citations in EconPapers (5)

Downloads: (external link)
http://hdl.handle.net/10.1023/A:1018948621875 (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:76:y:1998:i:0:p:233-259:10.1023/a:1018948621875

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

DOI: 10.1023/A:1018948621875

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 ().