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

这项研究是关于作业车间的完工时间最小化问题。最大完工时间是一个调度的长度，它的最小化被称为一个困难的优化问题。在这项研究中，我们试图通过分配从时间零到计划范围结束的工序来生成最小完工时间计划。然而，使用该方法最小化最大完工时间并不那么容易，因为在冲突的操作中分配一个候选操作对最大完工时间的影响往往很难估计，特别是在早期的决策阶段。为了减轻这一困难，我们将重点放在人工调度员的判断上。具有广泛的调度理论知识并具有调度决策经验的人通常可以通过在交互式调度支持系统的帮助下修改初始调度来找到更好的调度。在本研究中，我们首先通过实验提取了一名研究生的典型重调度模式，然后基于这些模式构建了一个程序，并将其与Giffler和Thompson的主动调度生成算法相结合。数值实验表明，该方法取得了较好的效果。为了改进该方法，还研究了拉格朗日松弛技术，以此作为选择最有希望的手术的指导。这种方法通常比基于下限的选择显示出更好的结果。我们的底层优化机制是一种深度优先的分支定界方法，这种方法往往消耗很长的计算时间。通过从所有直接的子节点收集不成功条件的原因，有可能转到两个或更多级别的父节点而不会失去搜索的最优性。虽然管理搜索历史需要额外的计算，但该搜索方法在一些问题实例中实现了有效的搜索。

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.