关键词: 作业车间, 调度算法, 滚动窗, 多瓶颈, 关键路径

Abstract: To solve Large-Scale Job Shop Scheduling Problems（LSJSSP）, a multi-bottleneck scheduling algorithm based on rolling horizon decomposition was proposed. This algorithm adopted critical path method to detect bottlenecks, and solved the LSJSSP by decomposing it into a series of sub-problems according to the process routines of the jobs. In the construction process of the sub-problems, the idea of load balanced distribution was proposed to distribute the load of each job in the sub-problems and to realize the stability of the solution process. In the solving process of the sub-problems. the bottleneck operations were scheduled by genetic algorithm, and the non-bottleneck operations were scheduled by dispatching rules according to the principle of “bottleneck machines lead non-bottleneck machines” in Theory of Constraints(TOC), the solving efficiency was improved. Through re-optimization process for the overlapping operations in the adjacent sub-problems and the strategy of evaluating the chromosome's fitness by the global solution, limitations of the decomposition and solving process were avoided, and the solution quality was improved. Simulation results showed that the proposed algorithm for LSJSSP was with satisfactory solution efficiency and quality.

Key words: Job Shop, scheduling algorithm, rolling horizon, multi-bottleneck, critical path