摘要：为克服现有算法求解工件数较多的单机调度问题计算量大的缺点,分析了加工时间为阶梯函数的工件排序规则,以极小化最大完工时间为目标,提出了基于局部搜索的改进遗传算法,对基于工序编码方式的染色体设计了线性顺序交叉算子和融合工件排序性质的局部变异算子,并引入局部搜索策略,提高了算法局部搜索能力和收敛速度.算例测试结果表明:工件数为40件时,与模拟退火算法相比,本文算法求得的最大完工时间平均减少了56.6%,显著缩短了制造周期,并有效地避免了局部最优解,收敛速度显著提高.

摘要：研究了以最小化最大完工时间为目标的不相关并行机环境下带恶化工件的车间调度问题,工件的加工时间随着开始时间的不同而改变,将其表示为开始时间的增函数,假设每个工件在不同机器上有各自的恶化系数。针对该NP-hard问题,建立数学规划模型,设计基于两段式编码和遗传参数自适应调节策略的改进遗传算法以合理地进行工件排序及机器分配。通过测试不同规模问题的仿真实验,对比结果表明所设计的算法在求解时间和求解质量上均具有较大优势。

摘要：研究了带恶化工件的置换流水车间调度问题,其中工件的加工时间是与开始时间有关的线性函数,考虑不同工件在不同机器上具有不同的恶化率,以最小化最大完工时间为目标,建立数学规划模型,进而提出了一种混合遗传算法来求解。该算法引入一种启发式规则以产生m-1条染色体改进初始种群的40%,结合遗传算法的初始种群产生方法共同生成种群,设计遗传参数自适应调节。仿真实验测试和对比了启发式法、遗传算法和混合遗传算法三种求解方法,实验结果表明所提出的混合遗传算法能更有效地求解这类NP-hard问题。