工件优先级图为非连接图且含环的单机总加权拖期调度问题

为满足实际生产环境对工件加工顺序和工件到达时间的要求,提出了具有新特征的单机总加权拖期调度问题,其特点体现在:工件有动态到达时间,且由工件优先级关系构成的优先级图为非连接图且存在环的情况,对该问题建立数学规划模型,在扩展Tang和Xuan等的基础上,提出了结合双向动态规划的拉格朗日松弛算法求解该问题。在该算法的设计中,提出双向动态规划算法求解拉格朗日松弛问题,使得它可处理优先级图中一个工件可能有多个紧前或紧后工件的情况,采用次梯度算法更新拉格朗日乘子,基于拉格朗日松弛问题的解设计启发式算法构造可行解。实验测试结果显示,所设计的拉格朗日松弛算法能够在较短的运行时间内得到令人满意的近优解,为更复杂的调度问题的求解提供了思路。

用禁忌搜索算法求解单机总加权拖期最小问题

针对以总加权拖期最小为目标的单机调度问题,提出了一个将启发式方法与禁忌搜索算法相结合的混合禁忌搜索算法HTS(Hybrid Tabu Search)。利用启发式方法产生初始解,随后通过禁忌搜索算法逐步提高解的质量。大量实验结果表明,提出的混合禁忌搜索算法能够在较短的时间内得到令人满意的较优解。

一种求解变速机调度问题的混合蚁群优化算法

针对一类变速机总加权拖期调度问题,提出一种混合蚁群优化算法。引入单机拖期调度问题中性能良好的修正预计完成时间的一种修改版本启发式规则,计算信息素初值,有利于算法跳出局部极值,并在局部搜索阶段,采用单亲遗传算法基因移位算子,有效优化当代最优解。通过均匀试验设计和统计分析,确定算法的关键参数组合,将算法应用于随机生成的不同规模的40个算例,并将其结果与同类文献中算法的优化结果进行对比分析。结果表明,在相同迭代次数下,混合算法优于对比算法。

随机返工及重加工情形下的Job-Shop调度问题

针对传统Job-Shop数学模型忽略返工及重加工的因素,构建了考虑该情形下的Job-Shop调度数学模型及相应的求解算法。该模型详细分析了返工及重加工的流程,对问题的定义做了进一步推导,模型以总加权拖期最小为目标,并提出一种改进的遗传算法对该模型进行求解。针对该调度情形,对算法中染色体的编码、种群初始化进行改进。种群数据的仿真实验表明,与传统遗传算法相比,改进后的算法在收敛速度、求出的最小总加权拖期方面均优于前者。最后通过对10×10实例调度方案求解及仿真,并与作业车间实际调度结果比较,模型仿真所得总加权拖期小于实际计划调度结果的46%,本模型得出的调度方案是实用且有效的。

基于嵌套分区算法框架的清洗—炉管区批调度

针对半导体生产线清洗—炉管区存在的Lot动态达到的并行批处理机优化调度问题,提出了嵌套分区差分进化算法,该算法充分利用嵌套分区算法的全局并行搜索的优势和差分进化算法较强的局部寻优能力。差分进化算法用来优化嵌套分区框架各可行域中抽样得到的样本群,使嵌套分区在选区阶段能更精确跟踪最有希望域,减少算法的回溯过程。通过仿真模型和实际生产线数据对该调度方案进行了比较验证,结果表明,所提算法较其他启发式算法能更有效降低总加权拖期交货损失。