Abstract: In unrelated machines scheduling, the initial schedule which minimizes production cost is no longer optimal due to emergent rate-modifying disruptions. A decision-maker needs to adjust the initial optimal schedule and balance between production costs and disruption-caused deviations. A rescheduling model is established which considers both the production costs and deviations. The former objective is total machine load and the latter objective is job's reassignment costs among different machines. An algorithm for obtaining the Pareto front of rescheduling problem is designed. Moreover, by transforming two objectives into one non-linear binary function based on decision-maker's preference, the algorithm which optimizes the binary function and returns a Pareto solution is developed. In numerical experiments compared with whole Pareto front, the algorithm optimizing binary function only needs to search a small portion of Pareto front. The percentage of Pareto solutions searched and CPU running time is greatly reduced, and the efficiency of problem-solving is improved.

Key words: operations research, rescheduling, unrelated machines scheduling, disruption management, pareto solution

摘要： 在变速机生产排序中, 受来自企业外部可改变机器加工效率的突发性干扰事件影响, 初始最小化企业生产成本的加工时间表不再最优,需要对其调整并在生产成本和干扰事件扰动之间进行权衡。建立了同时考虑生产成本和干扰事件扰动的重排序模型, 生产成本为所有机器的负载之和, 干扰事件的扰动为工件在不同机器之间重新安排所产生的运输费用和。设计了求解该重排序问题有效前沿的算法, 以及利用决策者对两个目标的偏好将双目标转化成一个二元非线性函数后, 求解优化该函数的有效解的算法。通过数值算例验证与整个有效前沿相比,优化二元函数的算法只需搜索部分有效前沿即可求出最优解,降低了有效解的搜索比例和运行时间,提高了干扰管理问题的处理效率。

关键词: 运筹学, 重排序, 变速机排序, 干扰管理, 有效解