Abstract: An decompositionbased optimization algorithm based on operation was presented for large-scale Job Shop scheduling problems in which the total weighted tardiness must be minimized. This algorithm adopted an iterative optimization framework which successively separated part of the operations from the original operation set and determined their processing order. In each iteration, a new sub-problem was firstly defined by a simulated annealing approach and then solved by using a genetic algorithm. Numerical computational experiments were carried out for both randomly generated test problems and real-life production data from a speed reducer factory in China. Results showed that the proposed algorithm could achieve satisfactory solution quality within reasonable computational time for large-scale scheduling problems.

Key words: Job Shop scheduling problem, decompositionbased optimization, simulated annealing, genetic algorithm, total weighted tardiness

摘要： 针对以最小化加权拖期和为目标的大规模作业车间调度问题，提出了一种基于操作的分解优化算法。该算法采用迭代优化的框架，从原问题对应的操作集合中依次分解出部分操作，并确定其加工顺序。在每一次迭代过程中，首先用模拟退火算法搜索较优的操作分解方案，并形成子问题，然后用遗传算法求解该子问题。针对随机生成的测试问题，以及某减速器厂实际生产数据的计算实验表明，该算法能够在合理的计算时间内获得满意的优化质量。

关键词: 作业车间调度问题, 分解优化, 模拟退火, 遗传算法, 加权拖期和