求解作业排序问题的一种改进修复约束满足算法

修复约束满足算法(修复法)是在完整初始解的基础上不断对变量进行修复,最终得到可行解.对此,提出一种求解flow shop排序问题的改进修复法(IRCS_WT),通过采用新的变量表达方式,设计了一种以启发式优化规则为指导的变量选择算法(LWT),并采用一种变量互换算法(LTEE)保证算法的全局搜索性能.将新算法应用于31个标准算例,与传统算法及遗传算法的优化结果进行比较,结果表明在相同运算时间下改进算法具有明显的优越性.

考虑中断损失的E/T问题

考虑了加工任务中带中断损失允许空闲时间插入的E T问题 .证明了具有共同完工时间允许中断的非限制模型的E T问题可以转化为不允许中断的问题来考虑 ;讨论了完工期限不一致的允许中断的E T问题 ,提出了可解的方法 。

基于块结构性质的花粉算法求解可重入作业车间调度问题

针对可重入作业车间调度问题(Reentrant job shop scheduling problem, RJSSP),提出一种基于块结构性质的花粉算法(Flower pollination algorithm based on block structure properties,FPA_BSP),用于最小化总加权延误时间(Totalweighted tardiness, TWT)。首先,建立RJSSP基于析取图的数学模型,并证明在确定析取弧方向后,该模型的对偶模型为最大费用流问题模型。其次,设计扩展RSOV (Reentrant-smallest-order-value, RSOV)编码规则,将花粉算法的实数矢量个体转变为排列矢量,使其可对问题解空间进行全局搜索,以发现存在优质解的区域。然后,定义8种邻域结构,并基于最大费用流问题特性分析块结构内部性质,得到前4种邻域结构能改进TWT的判定条件,可用于避免对无效区域的搜索,进而提出融合多种邻域的高效局部搜索,对全局搜索发现的优质解区域进行细致搜索。试验和算法比较验证FPA_BSP的有效性。提出RJSSP的块结构性质,并将其与花粉算法结合得到求解RJSSP的有效算法FPA_BSP,首次将花粉算法用于求解车间调度问题。