基于GA的工序排序优化中约束调整算法设计

基于遗传算法的工序排序优化,在进化过程中需要保证其个体的有效性,也就是工序之间存在的各优先级约束应该在每个个体中得到满足。通过将遗传算法进化中得到的随机个体的工序排序与预定的各优先级约束进行比较,调整个体的工序顺序关系直到满足全部的优先级约束。采用面向对象技术和双向链表数据结构,开发了约束调整算法的通用程序,并将其嵌入到遗传算法中。实例验证了该算法的可行性。

基于贪婪元胞遗传算法的工序排序优化问题

工序排序优化问题是一类以最小化总成本为目标,工序受到优先关系约束的NP问题。为了寻求此类问题的最优解,在元胞遗传算法的基础上提出了一种贪婪元胞遗传算法(GCGA)。该算法首先使用拓扑排序算法生成初始方案的工序顺序;然后引入贪婪算法生成初始可行工序序列的加工资源;最后分别在交叉和变异后设置精英个体保留策略。GCGA算法能够使初始种群的工序顺序满足优先关系的约束,降低初始方案的总成本,保持迭代过程中加工方案的可行性,提高收敛速度和收敛精度。为了验证算法的有效性,将算法应用于实际案例,与7种典型算法进行对比。实验结果表明:该算法获得的解的平均质量优于已知对比算法。

基于机动时间的可分解平行工序顺序优化研究

平行工序的顺序优化是解决资源有限项目进度计划问题的最有效、最普遍的方法之一。对于该类问题的研究目前主要基于工序的不可分解性,而现实情况下有些工序是任意可分的。基于此,本文首先提出了最小路长定理,在其基础上,建立了任意可分的两个平行工序调整为顺序工序的亏值模型,并进行了理论证明,此外,针对从n个可分解平行工序中选取一个与指定工序调整为顺序工序的优化问题进行了研究,在已给亏值模型的基础上设计出了优化算法,越是大型网络,该方法的优越性越明显。

可分解工序的顺序优化方法

利用工序的可分解性,提出将资源限制项目计划管理中的工序分解后,再进行网络优化的思想,分析了分解后工序的时间参数的特点,并给出了将可分解平行工序改为顺序工序的一种顺序排序优化方法。