《1998 Job shop scheduling with group-dependent setups》.pdf

Annals of Operations Research 76(1998)233 – 259 233 Job shop scheduling with group-dependent setups, finite buffers, and long time horizon Peter B. Luh, Ling Gou and Yuanhui Zhang Department of Electrical and Systems Engineering, University of Connecticut, Storrs, CT 06269-2157, USA Takaaki Nagahora and Makoto Tsuji Toshiba HamaKawasaki Works, 2-1, Ukishima-cho, Kawasaki-ku, Kawasaki-shi, 210 Japan Kiyoshi Yoneda, Tetsuo Hasegawa, Yuji Kyoya and Toshiyuki Kano Systems Software Engineering Laboratory, Toshiba Corporation, 70, Yanagi-cho, Saiwai-ku, Kawasaki-shi, 210 Japan 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 implementa- tion 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