论文部分内容阅读
摘要：本文对柔性加工路径的车间生产调度问题提出了一种新的算法，即遗传算法与启发式算法相结合的混合算法。经实验结果表明，这种算法可以大大提高企业制造资源的利用率和生产效率。
关键词：柔性 车间生产调度 遗传算法 启发式算法
车间生产调度可以描述为：用m台机床来加工n个工件，每个工件都有多个工序且每个工序可以在多个并不相同的机床上加工。怎样把有限的制造资源分配给这些要被加工的工件，使其某种指标最优化，这样的一个决策过程就是车间的生产调度。实际生产中经常会出现机床设备安排不当而造成加工工期延迟、导致企业重大损失的现象。因此，如何将稀缺的制造资源有效地分配给被加工工件，就成了制造行业的重要研究课题。
一、生产调度算法研究现状
自20世纪50年代开始到现在，关于调度问题的解决方法有很多，如：运筹学方法、遗传算法、启发式方法、粒子群优化算法、DNA算法、Petri网、摄动分析法和仿真调度法等等。现将几种经典的调度算法的特点总结如下。
1.启发式方法
此方法简单易行，在生产中得到了广泛的应用，但它也有缺点：一是不能考虑车间所有资源；二是由于分派规则的单一性导致多目标调度不能实现，而这个问题又是车间调度的基本问题；三是分派规则的选择决定调度性能，但是不存在一个分派规则能适应多个车间环境。
2.遗传算法
遗传算法是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法。其主要特点有三：一是直接对结构对象进行操作，不存在求导和函数连续性的限定；二是具有内在的隐并行性和更好的全局寻优能力；三是采用概率化的寻优方法，能自动获取和指导优化的搜索空间，自适应地调整搜索方向，不需要确定的规则。这种方法是解决搜索问题的一种通用算法，已被人们广泛应用。
3.拉氏松弛法
拉氏松弛法一般能在较短时间内对复杂的规划问题提供一个次优解，但是，大多情况下，要得到满意的调度结果，就要对所求解进行修改[5]。
人们所研究的各种调度算法都有各自的特点，但由于实际生产车间调度的复杂性、实时性和动态性等特点，车间调度问题还有待寻求更为优化的解法。
二、车间调度新算法
很多研究已经表明，要解决一个柔性加工路径的车间调度问题，单单仅靠传统的遗传算法进行优化，是很难得到满意结果的。因此，本文提出采用遗传算法与启发式算法相结合的混合算法来解决，具体步骤如下：
第一步：初始化，把可以使用机床k的时间Rk和工件i的第一道工序可被加工的时间Di1均设置为零；
第二步：使用优先规则挑出还没有被调度的工序，且它还是排在第一位的工序，并已经进入第三步运算的工序；否则时间跨度=min(Oi)（i=1，2，…，n），其中，Oi表示工件i的完工时间;
第三步：利用Fijk=max[Rk，Dij] dijk更新工件下一道工序的开始加工时间和机床的利用时间，这里的Fijk表示工件i在机床k上完成工序j的时刻；
第四步：设工件i的第j道工序的最早完工时间Eij=min(Fijk)，那么Oi=Eij；否则，工件的下一道工序的可加工时间Oi(j h)=Oi(j h) (Eij-Oi(j 1))，其中h=1，2，…，(Ji-j)；
第五步：使机床k的可使用时刻Rk等于工件i的第j道工序的最早完工时间Eij；
第六步：判断是否还有没有被调用的工序，要是还有就从第二步重新开始，否则跨度时间就等于min(Oi)。
三、结束语
本文针对企业中常见的柔性加工路径的车间调度问题，提出了一种新的优化算法，即遗传算法与启发式算法相结合的混合算法。实践证明，该方法对于提高制造企业的资源利用率和生产效率是有效的。
参考文献：
[1]徐俊刚,戴国忠,王洪安.生产调度理论和方法研究综述.计算机应用与发展,2004,41(2):257-266．
[2]戴绍剁，谭跃进,汪浩.生产调度系统研究.系统工程,1999,17(1):41-45．
[3]Jeffrey Dean Kelly. Chronological decomposition heuristic for scheduling：Divide and conquer Method.AICHE Journal.2002，48(12):2995-2999．
[4]纪树新,钱积新,孙优贤.车间作业调度遗传算法中的编码研究.信息与控制,1997.5:393-400．
[5]熊锐,吴澄.车间生产调度问题的技术现状与发展趋势.清华大学学报:自然科学版,1998,38(10):55-59．
（作者单位：江西技师学院）
关键词：柔性 车间生产调度 遗传算法 启发式算法
车间生产调度可以描述为：用m台机床来加工n个工件，每个工件都有多个工序且每个工序可以在多个并不相同的机床上加工。怎样把有限的制造资源分配给这些要被加工的工件，使其某种指标最优化，这样的一个决策过程就是车间的生产调度。实际生产中经常会出现机床设备安排不当而造成加工工期延迟、导致企业重大损失的现象。因此，如何将稀缺的制造资源有效地分配给被加工工件，就成了制造行业的重要研究课题。
一、生产调度算法研究现状
自20世纪50年代开始到现在，关于调度问题的解决方法有很多，如：运筹学方法、遗传算法、启发式方法、粒子群优化算法、DNA算法、Petri网、摄动分析法和仿真调度法等等。现将几种经典的调度算法的特点总结如下。
1.启发式方法
此方法简单易行，在生产中得到了广泛的应用，但它也有缺点：一是不能考虑车间所有资源；二是由于分派规则的单一性导致多目标调度不能实现，而这个问题又是车间调度的基本问题；三是分派规则的选择决定调度性能，但是不存在一个分派规则能适应多个车间环境。
2.遗传算法
遗传算法是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法。其主要特点有三：一是直接对结构对象进行操作，不存在求导和函数连续性的限定；二是具有内在的隐并行性和更好的全局寻优能力；三是采用概率化的寻优方法，能自动获取和指导优化的搜索空间，自适应地调整搜索方向，不需要确定的规则。这种方法是解决搜索问题的一种通用算法，已被人们广泛应用。
3.拉氏松弛法
拉氏松弛法一般能在较短时间内对复杂的规划问题提供一个次优解，但是，大多情况下，要得到满意的调度结果，就要对所求解进行修改[5]。
人们所研究的各种调度算法都有各自的特点，但由于实际生产车间调度的复杂性、实时性和动态性等特点，车间调度问题还有待寻求更为优化的解法。
二、车间调度新算法
很多研究已经表明，要解决一个柔性加工路径的车间调度问题，单单仅靠传统的遗传算法进行优化，是很难得到满意结果的。因此，本文提出采用遗传算法与启发式算法相结合的混合算法来解决，具体步骤如下：
第一步：初始化，把可以使用机床k的时间Rk和工件i的第一道工序可被加工的时间Di1均设置为零；
第二步：使用优先规则挑出还没有被调度的工序，且它还是排在第一位的工序，并已经进入第三步运算的工序；否则时间跨度=min(Oi)（i=1，2，…，n），其中，Oi表示工件i的完工时间;
第三步：利用Fijk=max[Rk，Dij] dijk更新工件下一道工序的开始加工时间和机床的利用时间，这里的Fijk表示工件i在机床k上完成工序j的时刻；
第四步：设工件i的第j道工序的最早完工时间Eij=min(Fijk)，那么Oi=Eij；否则，工件的下一道工序的可加工时间Oi(j h)=Oi(j h) (Eij-Oi(j 1))，其中h=1，2，…，(Ji-j)；
第五步：使机床k的可使用时刻Rk等于工件i的第j道工序的最早完工时间Eij；
第六步：判断是否还有没有被调用的工序，要是还有就从第二步重新开始，否则跨度时间就等于min(Oi)。
三、结束语
本文针对企业中常见的柔性加工路径的车间调度问题，提出了一种新的优化算法，即遗传算法与启发式算法相结合的混合算法。实践证明，该方法对于提高制造企业的资源利用率和生产效率是有效的。
参考文献：
[1]徐俊刚,戴国忠,王洪安.生产调度理论和方法研究综述.计算机应用与发展,2004,41(2):257-266．
[2]戴绍剁，谭跃进,汪浩.生产调度系统研究.系统工程,1999,17(1):41-45．
[3]Jeffrey Dean Kelly. Chronological decomposition heuristic for scheduling：Divide and conquer Method.AICHE Journal.2002，48(12):2995-2999．
[4]纪树新,钱积新,孙优贤.车间作业调度遗传算法中的编码研究.信息与控制,1997.5:393-400．
[5]熊锐,吴澄.车间生产调度问题的技术现状与发展趋势.清华大学学报:自然科学版,1998,38(10):55-59．
（作者单位：江西技师学院）