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

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