大规模流水线调度的瓶颈分解算法研究

为了克服大规模流水线调度问题的计算复杂度，提出一种瓶颈分解启发式算法．利用瓶颈特性将流水线分解为瓶颈机和非瓶颈机，对瓶颈机建立带有到达时间和传递时间约束的单机调度模型，并优化求解，而在非瓶颈机上则采用简单的分派规则，通过不断修正瓶颈机上工件的到达时间和传递时间来协调瓶颈机与非瓶颈机之间的关联．仿真结果验证了算法的有效性．

Bottleneck-based Decomposition Algorithm for Large-scale Flow Shop Scheduling Problems

A bottleneck-based decomposition heuristic algorithm is proposed for dealing with computational complexity in large-scale flow shop scheduling problems. Based on the characteristic of bottleneck, the flow shop is decomposed into bottleneck and non-bottleneck machines. A single-machine scheduling problem with release time and delivery time is built for the bottleneck machine, which is solved optimally, while simple priority rules are used for scheduling the non-bottlenecks. The correlations between the bottleneck and non-bottleneck machines are coordinated by adjusting the release time and delivery time of jobs on the bottleneck machine. Simulation results show that the heuristic algorithm can obtain better solution in quite short time and be suitable to large-scale problems.