基于目标增量的大规模无等待调度复合启发式算法

无等待调度是存在于轧钢、化工、食品加工等企业和JIT、FMS及机器之间高度协作加工环境的一类约束流水调度，每个任务一旦开始加工便不能间断，即工序之间无等待时间。分析无等待调度的特点，将优化目标等价转化为相邻任务间距离的加权和；提出目标增量法来评价优化算法中新调度的优劣，直接计算新调度和原调度序列中任务变化点的距离加权和（目标增量），如果目标增量值与优化方向一致，则新调度优于原调度，否则新调度劣于原调度；目标增量法仅计算少数几个变化点的目标变化量，改变传统逐步计算调度目标函数值来评价新调度的优劣，可降低算法的时间复杂度。基于目标增量法分别提出不同的全局优化复合启发式算法求解最小化最长完工时间、最小化总完工时间和最长完工时间的双目标大规模无等待调度问题。项目的研究可为其它大规模无等待调度问题提供快速有效的求解方法，也可推广到求解中小规模问题的遗传算法等元启发式算法。