具有可分离准备时间和无等待约束的流水调度优化算法

广泛存在于冶金、制药、食品加工等应用中的具有可分离准备时间和无等待约束流水调度优化是NP难问题。无等待流水调度中任务加工路线确定且一致，要求任务一旦开始加工便不能中断。分析可分离准备时间独立于调度顺序(SIST)的无等待调度问题的任务间距离，推导算法基本操作的独立变化性质；构造任务间全局/局部支配关系，设计基于此类关系的局部重排等优化策略。比较SIST问题与可分离准备时间依赖于调度顺序(SDST) 无等待调度问题，建立后者的数学模型；构造基于机器空闲时间和准备时间的加权代价函数和紧邻任务矩阵，提出结合紧邻关系判断机制的邻域搜索方法，设计基于多元因子性能评估的启发式算法搜索策略，提高算法性能；提出包含初始解、邻域搜索和局部解改善等三阶段的全局优化复合启发式算法和元启发式算法，为两类调度问题提供快速、有效的求解方法。本项目可推广到实际工程应用，具有重要的科学意义和应用价值。

分析具有顺序独立可分离准备时间（SIST）和顺序依赖可分离准备时间（SDST）的无等待调度问题性质，推导任务间距离与加工时间和准备时间等参数之间的函数关系，构造任务完工时间计算模型，并给出基于插入、删除、移位、对换等基本算子的多种操作的性质定理，设计m-机SIST问题任务间支配规则； 结合设计出的支配规则、优化策略和具有SDST/SIST约束的最小化总完工时间/最大完工时间无等待调度问题等目标函数的特点，提出多项式复杂度初始解生成算法；试验分析高效的构造解方法；试验分析不同插入或对换方法组合对提高解的效果，得到高效的提高解方法；试验分析多种搜索算子及其组合方式，构建合理的优化机制，设计高效的元启发式方法。