Robustness optimisation of the minimum makespan schedules in a job shop
Robustness optimisation of the minimum makespan schedules in a job shop
复制标题
作业车间最小完工进度的鲁棒性优化
DOI：
10.1504/ijmtm.2003.002524
复制
发表时间：
2003
期刊：
影响因子：
--
通讯作者：
N. Nakamura
中科院分区：
文献类型：
--
作者：
Y. Kawata;K. Morikawa;Katsuhiko Takahashi;N. Nakamura
一般来说，作业车间中存在许多最小完工时间计划。因此，根据二次准则选择最优方案是非常重要的。在本文中，我们采用了一种称为调度稳健性的度量作为选择标准。调度的稳健性是灵敏度的最大值，灵敏度是对所有操作的完成时间延迟一个时间单位的度量。由于通常存在许多最小完工时间调度，因此很难列举所有完工时间最小的活动调度，然后找到最稳健的调度。基于析取图模型和Carlier和Pinson提出的命题，引入分支定界法来最小化最大完工时间，同时优化健壮性。使用相应的析取图计算每个部分调度的稳健性下界。通过对测试问题的求解，验证了该方法的有效性。
In general, many minimum makespan schedules exist in job shops. Therefore, it is important to select the best one based on secondary criterion. In this paper, we adopt a measure called robustness of the schedule as the selection criterion. The robustness of the schedule is the maximum value of the sensitivity, which is a measure for the delay of completion times by one time unit, for all of the operations. As there are generally many minimum makespan schedules, it is difficult to enumerate all makespan-minimum active schedules and then to find the most robust schedule. A branch and bound method is introduced to the minimisation of makespan while optimising robustness based on a disjunctive graph model and the propositions proposed by Carlier and Pinson. A lower bound of robustness for each partial schedule is calculated using the corresponding disjunctive graph. The effectiveness of the proposed approach is clarified by solving test problems.