含运输时间的柔性作业车间调度问题研究_柔性作业车间调度问题

含运输时间的柔性作业车间调度问题研究由刀豆文库小编整理，希望给你工作、学习、生活带来方便，猜你可能喜欢“柔性作业车间调度问题”。

含运输时间的柔性作业车间调度问题研究

摘要：在工厂实际生产中，零件加工的运输时间占整个加工时间的比例是很大的，这个时间在生产调度时不可忽略。为了更合理的研究柔性作业车间调度问题，本文将运输时间考虑进调度模型之中，并在经典遗传算法的基础上进行改进，设计了一种新的启发式规则算法，嵌入在遗传算法中，用于该问题的求解。通过计算结果的比较，证明本文调度模型更符合实际生产情况，改进后的算法能够得出更高质量的解，且效率更高。

关键词：柔性作业车间调度运输时间遗传算法

Research on Flexible Job-shop Scheduling Problem with

Transport Time

Abstract: In the actual production, transport time always accounted for a large proportion of entire proceing time.So the transport time should not be ignored when production scheduling.In order to reasonably research flexible job-shop scheduling problem, this paper took the transport time into account when modeling, and designed a new heuristic rules, which was embedded in the genetic algorithm, to solve the problem based on claical genetic algorithm.Through comparing calculate results，the scheduling model is proved more accord with actual production situation.And the improved genetic algorithm is more efficient and can get higher quality solutions.Key words: Flexible job-shop scheduling problemTransport timeGenetic algorithm

引言

在实际生产中，通常一道工序能在多台机器上进行加工，需要根据现场生产情况选择合适的机器进行加工。于是在传统的作业车间调度问题(Job-shop scheduling problem，JSP)的基础上发展出了柔性作业车间调度问题(Flexible job-shop scheduling problem，FJSP)。目前柔性作业车间调度问题的研究很多，何莺等[1]提出了以工件提前/拖期惩罚代价最小，生产周期最小为目标的多目标优化调度算法，可得到满意的较优解；孙志峻等[2]提出了针对批量生产的柔性作业车间调度方案；Runwei等[3] 研究了遗传算法在作业车间调度问题中的应用；张国辉等[4]设计了一种改进遗传算法用于柔性作业车间调度问题的求解，提高了求解质量。

在这些研究中，考虑了机器的选择问

题，使得问题得到较好的解决。但是选择不同的机器加工，转换机器进行生产时的运输路线也就会不同，即运输时间也不同。而零件加工的运输时间在目前的研究却没有得到较好的考虑。如孙志峻等[2]在约束条件中已规定了工件的运输时间被忽略。事实上在现在的工厂生产中，零件加工运输时间占整个加工时间的比例是很大的，一些大型零件的运输通常还需要行车等起重运输工具，那这个比例则更大。福特汽车公司的统计数据表明，在工厂生产过程中零件的加工时间只占5%，而其他95%的时间都是零件在搬运和储存等待之中[5]。由此可见，运输时间是柔性作业车间调度问题中必须要考虑的一个因素。在调度时确定一条合理的加工路线，尽量减少运输时间，是提高生产效率，获得更大效益的可靠途径。

本文针对FJSP特点，将零件运输时间考虑进调度模型之中，使得调度结果更符合实际情况；并且采用启发式规则与遗传算法相结合的调度算法，使得在求解FJSP时的求解速度和求解质量上都有了较大提高。柔性作业车间调度问题建模

柔性作业车间调度问题的描述如下：n个工件要在m台机器上加工。每个工件包含一道或多道工序，各工序之间有先后约束，每道工序可以选择多台不同加工机器中的一台进行加工，工序的运输时间随加工机器的不同而不同。调度目标是为每道工序选择最合适的机器、确定每台机器上各个工件工序的最佳加工顺序以及开工时间，达到加工时间短、设备利用率高，生产成本就低等调度目标。因此实际上可将柔性作业车间调度问题分为两个子问题：确定各工序的加工顺序和确定各工序的加工机器。

在本文调度模型中，设定最小加工时间作为目标函数：

min:Ht

（1）其中H为目标函数，t为在完成所有加工任务的总时间，单位为秒。其中t可表示为：

tmax{T(M1),T(M2),……，T(Mm)}

（2）上式表示作业的完工时间等于设备中完工时间最晚的那台设备的完工时间，其中T(Mm)表示设备m的最后完工时间，它的计算式如下： T(Mm

Mm

M

m

m)WTMik

TSij,i(j1)

T(Oik)（3）其中用WTMjik表示在冲压机Mm上空闲

时间；TSMm

ij,i(j1)

表示在冲压机Mm上加工的工序的运输时间，一般可以用运输距离除以运输速度，也可视现场情况确定；T(O)M

m

ik表示在冲压机Mm上加工的工序的加工时

间。此外，加工过程还需要满足如下约束条件：

（1）同一工件的后一道工序开工时间不能早于前道工序的完工时间。

（2）每台机器同一时刻只能加工一种工序。

（3）一道工序开始后必须在该台机器上不间断加工直至完成。

（4）不同工件没有加工优先级的区别。改进遗传算法的设计与实现

2.1 启发式规则设计

常用的启发式规则通常只用于解决传统作业车间调度问题，而柔性作业车间调度问题不但要确定工序加工顺序，还要确定机器顺序。考虑到设备利用率和各设备的生产平衡度，本文提出一种基于机器前续完工时间和后续预期加工时间的启发式规则，用于解决柔性作业车间调度中的机器选择问题。具体规则如下：

（1）机器前续完工时间规则：为工序选择加工机器时，首先找到该工序的所有可加工机器，并计算出每台机器已经安排了的工序的完工时间，即前续完工时间。选择前

续完工时间与该工件前一道工序的完工时

间绝对值之差最小的机器，进行该工序的加工。这样选择的好处是可以避免较大的机器

空闲时间，提高了机器利用率；又可以避免

某台机器的工作时间过长，使生产平衡度不

高。

（2）机器后续预期加工时间规则：若有两台或以上的机器前续完工时间并列最早，则对这若干台机器计算后面可能在该机

器上加工的工序的总加工时间，即预期后续加工时间。选择预期后续完工时间最短的机器进行加工。这样可以进一步避免某台机器的工作时间过长，从而提高生产平衡度。

2.2 染色体编码和解码

在柔性作业车间调度问题中，一个生

产计划在调度后的结果中必须包含两个部

分：加工工序及其顺序；加工机器及其顺序。

本文采用文献[6]中的基于工序的编码。例如3个工件，分别有2、3、4道工序，对其进行编码，得到结果如下：

工序编码： 1 2 3 1 2 3 2 3 3机器编码： 1 5 1 2 4 3 2 4

3工序编码中不同代码表示不同的工件，相同代码按从左至右出现的次序分别表示同种工件的先后工序。机器编码中代码表示的是其对应位置工序的机器的编号。

2.3 算法流程

柔性作业车间调度问题比传统作业车间调度问题更加复杂。因此，在算法设计时也要进行相应改进。结合本文的启发式规则，改进遗传算法的具体步骤如下：（1）确定参数。主要包括根据问题复杂程度确定种群规模、交叉率、变异率。（2）初始化。对工序进行编码，先随机生成工序编码，然后按本文的启发式规则生成机器编码，产生第一代种群。（3）适应度函数评价。评价种群中每个染色体的适应度函数值，如果达到收敛条件，则结束运行。否则转步骤（4）。（4）选择操作。采用轮盘赌选择法与精华选择法相结合的方法进行选择操作，选取下一代种群。（5）交叉、变异操作。对选择出来的个体，以交叉率Pc与变异率Pm进行交叉或变异操作，需要注意的是交叉变异只对工序编码进行，然后将完成后的染色体以本文启发式规则进行机器的选择，最终生成新一代种群。

（6）返回步骤（3）。计算实例与结果

根据上述建模思想和算法，本文取某企业冲压车间某天的生产计划（如表3.3）作为实例进行算法仿真。该生产任务列表包括5个冲压件，表中列出了每种冲压件生产的数量，每种冲压件所包含的工序，每道工序的生产时间。

表3.3 生产任务及相关工艺参数表 冲压件 批数量 工序 加工时间（秒）

J2 500

J3 600 J4 500

J5 500

本次作业的生产线共有5台冲压机，成直线式排布，每台冲压机间隔距离相等，设为一个单位距离。每个冲压件的第一道工序只能在第一台或第五台冲压机上进行加工，其余工序可在任一台冲压机上加工。该作业调度问题是典型的柔性作业车间调度问题。

但由于是批量生产，本文第1节中的约束条件“同一工件的后一道工序开工时间不能早于前道工序的完工时间”应该修正为：同一工件的后一道工序开工时间不能早于前一道的第一件工序的完工时间。但考虑到单件工序加工时间相对整批工件工序的加工时间是很小的，为方便计算，将该时间忽略不计，则本问题进一步将此约束条件修改为“同一工件的后一道工序开工时间不能早于前一道的第一件工序的开工时间”，即同一工件的前一道工序开工后，后一道工序即可开工。此外冲压生产时的换模时间需要考虑到加工时间中去。本实例换模时间为30分钟。

按照启发式规则和随机相结合的初始化方法生成50个染色体构成初始种群。同时设定交叉概率Pc=0.6，变异概率Pm=0.01，单位距离运输时间ts=200秒，目标函数：min:H=t；适应度函数：f(vk)=Cmax-H，Cmax为该代种群中完工时间最长的一个染色体。当前种群的最优解遗传50代后仍无提高则

算法终止。

运用上面所设计的遗传算法对这个案例进行仿真求解，最优解的染色体为：

工序码：5 5 5 2 2 3 3 4 4 4 3 1 4 5 5 机器码：1 2 3 5 4 5 4 1 2 3 5 1 4 2 3 将上述调度计划转化为甘特图（图3.7）可以更清楚直观的反映调度结果。

图3.7

调度结果甘特图

由上图可知，本文算法对本次生产任务的调度结果为26700秒，且设备利用率和各设备间的平衡度都较高。如果在建模中不考虑运输时间，通过同样的算法得出的最优染色体是：

工序码：4 4 4 1 4 5 3 3 5 5 3 2 2 5 5 机器码：1 2 3 5 4 5 1 2 4 3 5 1 2 3 4 该染色体解码后得到调度结果为26100秒。但由于实际生产中运输时间是客观存在的，那么在这个调度结果中再加入运输时间，经调整后的实际结果27100秒。这个结果比本文调度结果多了400秒，如图3.8和3.9所示。所以考虑运输时间是十分必要的。

图3.8不含运输时间的调度结果甘特图

T(s)

图3.9含运输时间的调度结果甘特图

在算法的设计上，相对于经典遗传算法，本算法嵌入了启发式规则。程序在环境为AMD Athlon(tm)CPU，主频2.50GHz，内存2GB的运行环境下，取100次运算的平均值，算法运行情况如表3.7：

表3.7算法运行情况表

收敛代数运行时间最优解 本算法1391.86726700 SGA1993.12527900

由以上数据可见，本算法相对于经典遗传算法(SGA)，能够取得更好的解，且运行时间更短。因此本文改进遗传算法能够更好的应用于柔性作业车间调度问题的求解。结论

（1）本文在分析柔性作业车间调度问题的基础上，建立了符合实际情况的调度模型。该模型加入了目前同类研究中未考虑到的影响因素：运输时间，使得该模型具有更高的实际利用价值。

（2）针对经典遗传算法的优缺点进行了分析，提出了嵌入启发式规则的改进遗传算法用于解决柔性作业车间调度问题，并通过仿真实验证明了该算法能够得到更高质量的解，且运算效率更高。

参考文献

[1] 何莺，蔡鸿明.基于需求优先的多目标柔性车

间调度研究.微型电脑应用.2002，7(5): 1-3.[2] 孙志峻，乔冰，潘奎科等.具有柔性加工路径

作业车间批量调度优化研究.机械科学与技术.2002，3(4): 348-350.[3] Runwei Cheng, Mitsuo Gen, Yasuhiro Tsujimura.A Tutorial Survey of Job-shop Scheduling Problems Using Genetic Algorithms PartⅡ: Hybrid Genetic Search Strategies.Computers

and Industrial Engineering.1999, 36(2): 343-364

[4] 张国辉，高亮，李培根等.改进遗传算法求解

柔性作业车间调度问题.机械工程学报.2009，45(7): 145-151.[5] 李学诗.改善工厂物流必须抓住车间生产物

流这个重点.物流技术.2008，27(10): 215-217.[6] M Gen, Y Tsujimura, E Kubota.Solving

Job-Shop Scheduling Problems by Genetic Algorithm.The 16th Int.Conf.on Computer and Industrial Engineering, Vancouver.1994, 2(10): 1577-1582