遗传算法在多品种装配生产排序中的应用

针对多品种装配顺序的安排问题,以总工艺辅助时间最小为目标,表达为求解旅行商问题(TSP),提出并设计了合理的遗传算法。计算和仿真结果显示,该遗传算法的实用性和有效性。

等待时间受限的两阶段流水车间调度问题性质研究

对等待时间受限的两阶段流水车间调度问题的基本性质进行了研究。在问题的复杂性方面,证明了任何基于排列排序的调度规则都不能保证具有最优性,而且问题是强NP难的。在原问题和排列排序问题之间的关系方面,证明了满足排列排序要求的任一工件加工序列均可构成相应的可行调度;当满足一定条件时,排列排序的最优解也是原问题的最优解。这些性质为设计求解算法提供了理论基础。

多品种装配顺序的一种改进遗传算法

多品种装配顺序的安排问题属于旅行商问题(TSP),具有NP计算复杂性,针对该问题,以工艺辅助时间需求为优化目标,对遗传算法的边重组交叉算子(ER)作了改进.将基因的邻接关系分为左邻接关系和右邻接关系,通过抛弃基因的左邻接关系,将ER改进为右边重组算子(R-ER),仿真表明改进后的遗传算法寻优能力更强、收敛性更佳.

关于“Fm|prmu|C_(max)问题”的算法

Fm|prmu|Cmax,即m(m>2)台机器同顺序加工n个工件问题是一类重要的车间作业排序问题.对于给定加工顺序的n个工件的排列排序,排序时间表长即任务的最后完工时间的计算可以通过与问题对应的有向图的关键路的计算得到.本文从关键路的结构特点和性质出发,提出了在关键路的基础上将前后相邻的两个工件的加工时间进行比较,然后择优排序的方法,使Johnson SM算法可以在多台机器上得到一定程度的推广,从而使该问题的解法得到明显简化.

等待时间受限的流水车间调度问题的若干性质

等待时间受限的流水车间调度问题广泛存在于高温连续作业或中间产品不稳定的流水车间生产管理过程中,要求工件在相邻机器上的等待时间不能超过一定的上限.针对以最小化最大完工时间为目标函数的该类问题,研究了加工机器上的工件序列特征,并在此基础上分析了基于排列排序进行问题求解的可行性和有效性,为算法求解提供了理论依据.

两机无等待流水车间调度问题的性质

针对两机无等待流水车间调度问题,提出目标函数最大完工时间最小化的快速算法,并给出算法的复杂度.分析两机无等待流水车间调度问题的排列排序性质,证明了两机无等待流水车间调度问题的可行解只存在于排列排序中,排列排序的最优解一定是两机无等待流水车间调度问题的最优解.最后研究了同时包含普通工件和无等待工件的两机流水车间调度问题的复杂性,为进一步研究两机无等待流水车间调度问题提供了理论依据.