车间生产调度算法研究

　　摘要：本文对柔性加工路径的车间生产调度问题提出了一种新的算法，即遗传算法与
启发式算法相结合的混合算法。经实验结果表明，这种算法可以大大提高企业制造资源的利
用率和生产效率。

 

　　关键词：柔性

 车间生产调度 遗传算法 启发式算法 

　　

 

　　车间生产调度可以描述为：用

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 的时刻；