Development of makespan minimization techniques involving scheduling patterns for a job shop

点击翻译按钮获取中文摘要

This study deals with makespan minimization of a job shop. The makespan is the length of a schedule and its minimization is known as a hard optimization problem. In this study we have tried to generate a minimum makespan schedule by assigning operations from time zero toward the end of the planning horizon. However the minimization of makespan using this method is not so easy as it is often difficult to estimate the effect of assigning one candidate operation among conflicting operations on the makespan with enough accuracy, especially in earlier decision stages. To alleviate this difficulty we focus on the human scheduler's judgments. A person having extensive knowledge of scheduling theory and having experience in scheduling decisions can often find a better schedule by modifying an initial schedule with the aid of an interactive scheduling support system. In this study we first extracted typical rescheduling patterns of a graduate student experimentally, then constructed a procedure based on these patterns, and combined it with the active schedule generation algorithm of Giffler and Thompson. Numerical experiments showed favorable results of the proposed approach. To enhance the proposed approach, the Lagrangean relaxation technique was also investigated as a guide of selecting the most promising operation. This approach often showed better results than the lower-bound-based selection. Our underlying optimization mechanism is a depth-first branch and bound method, and this method often consumes a long computation time. By collecting the reasons of unsuccessful conditions from all immediate child nodes, it may be possible to go to a parent node two or more levels above without losing optimality of the search. Although managing the search history requires additional computations, this search method realized an effective search in some problem instances.