求解调度问题的启发式算法7页

1、一种改进的关键工序算法刘智勇 徐昕江苏科技大学经济管理学院，江苏 镇江 212003摘要：针对问题，改进了关键工序法法，该算法同时注重关键工件与关键工序，通过对关键工件与非关键工件在关键工序前后的加工时间计算、比较来获得各工件加工的先后顺序，缩短最长流程时间。并将该启发式算法与关键工序法进行了对比分析，最后利用仿真的方法来验证所提出的方法的可行性。关键词：Flow-shop 关键工件 关键工序 启发式算法 最长流程时间0引言Flow-shop调度问题（flow shop scheduling problem,FSP）是许多实际流水线生产调度问题的简化模型，它无论是在离散制造工业还是在流程工业中

2、都具有广泛的应用，因此其研究具有重要的理论意义和工程价值。n/m/p/Fmax问题是Flow-shop调度问题中的一种特殊情况，即所有工件在各台机器上的加工顺序都相同，也称流水作业排列排序问题或同顺序排序问题。其求解方法有精确方法1（分支定界法、穷举法等）、智能搜索法2,3,4（神经网络法、遗传算法、蚁群算法等）、启发式算法4,5,6,7（Palmer算法、C-D-S法、关键工序法、最小排序系数法等）等等。由于Flow-shop调度问题一般都属于NP难题(nondeterministic polynomial)。精确方法只能求解小规模问题，对于大规模问题几乎被认为是无效算法，智能搜索法在求解上

3、虽比启发式算法更接近最有解，但由于设计针对具体问题的智能搜索法对于许多人来说比较困难，特别是对于实际工程人员更是如此。所以启发式算法仍是用的很多的方法。主要的启发式算法有Palmer算法、关键工序法和最小排序系数法等。其中，关键工序法贯穿着当前先进的管理思想，能够很好的对现实情况进行解释和分析。然而关键工序法所求的可行解很可能与最优解相差甚远，鉴于此，本文对其进行了改进。1 问题描述问题可以描述为：有个工件在台机器上加工，各工件有完全相同的工艺路线，每一台机器上加工工件的先后顺序也完全相同；一个工件不能同时在不同的机器上加工；每台机器同时只能加工一个工件；各工件在加工完后立即送下一道工序；工件

4、在机器上开始加工，必须一直进行到该工序完工，中途不允许停下来插入其它工件；所有工件在0时刻已准备就绪，机器调整时间包括在加工时间内；允许工件在工序之间等待，允许机器在任务未到达时闲置；优化目标是求出这n个任务的一个全排列，使其最长流程时间（也称加工周期）最短，则的计算方法如下：上式中代表工件在机器上的完工时间，代表工件在机器上的加工时间。2改进的关键工序法改进的关键工序法要求抓住关键工序和关键工件，定义关键工序为各道工序上加工各个工件总时间最长的工序；定义关键工件为各个工件在各道工序加工总时间最长的工件。若关键工件都多个，则按照各关键工件首道工序加工时间与尾道工序加工时间的大小分组，首道工序加

5、工时间小于尾道的工件为第一组，首道工序加工时间等于尾道的工件第二组，首道工序加工时间大于尾道的工件为第三组，优先顺序为第一组，第二组，第三组，对于第一组中的各关键工件之间的排序则按关键工序前各道工序总加工时间从小到大排序，对于第三组的各关键工件之间的排序则按关键工序后各道工序总加工时间从大到小排序，第二组的各关键工件的排序时需先比较第一组与第三组内的工件个数，当第一组的工件个数少于或等于第三组时，第二组内工件按第一组规则排，否则按第三组的规则排。对关键工件以外的所有工件同样比较首道工序加工时间与尾道工序加工时间，按小于、等于、大于分为三组，其组内排序规则与关键工件个组内排序规则相同。最后按非关

6、键工件第一组，非关键工件第二组，关键工件第一组，关键工件第二组，关键工件第三组，非关键共建第三组的顺序进行总排序，即可获得满意的。对于关键工序为首道工序的情形，就把次关键工序看成是上述的关键工序，排序步骤不变。用数学语言表示如下：Step1: 对，计算，对，计算，定义为关键工件，定义 为关键工序。Step2:：若（其中表示括号中集合包含元素的个数），则，则计算的值，按该值从小到大排列获得一个排序优先。，则计算的值，按该值从大到小排列获得一个排序优先序列。，则当时，那么按的规则获得中元素的排序；当时，那么按的规则获得中元素的排序；设中元素的排序优先序列为。将Step2:中的各种排序优先序列一起排

7、序，得到。Step3:：若，则，则计算的值，按该值从小到大排列获得一个排序优先。，则计算的值，按该值从大到小排列获得一个排序优先序列。，则当时，那么按Step3中的规则获得中元素的排序；当时，那么按Step3中的规则获得中元素的排序；设中元素的排序优先序列为。Step4:：将上述结果进行总排序优先级：。经过上述四步，获得的结果就是满意解。3算法示例设有8个零件A、B、C、D、E、F、G、H在8台机器M1、M2、M3、M4、M5、M6、M7、M8上同顺序加工，其工艺过程及工时定额见表1，试求出最长流程时间Fmax.表1 工艺过程及工时 零件工序ABCDEFGH各工件加工总时间M138691287

8、44M213224756746M3716109607459M415781011148982M5647125115555M666821083245M72107215102351M8871010156451各工件总加工时间6060585856554541现利用改进的关键工序法求解:计算每个工件的总加工时间以及每个工序总加工时间，见表，可知关键工件有两个A、B，关键工序有一个M4。针对A工件，首道工序加工时间大于尾道工序加工时间，B工件，首道工序加工时间小于尾道工序加工时间，自然A排B的前面，即AB。对剩余工件，按首道工序加工时间大于、等于、小于尾道工序加工时间分成三类，可得首道工序加工时间大于尾道

9、工序加工时间的工件有C、D、F；首道工序加工时间等于尾道工序加工时间的工件E；首道工序加工时间小于尾道工序加工时间的工件有G、H。 对C、D、E、F按关键工序前的各道工序时间相加（M1+M2+M3），得到TC=6+2+10=18，TD=9+4+9=22， TF=2+5+0=4，则C、D、F的排序按T值从小到大为FCD； 对G、H按按关键工序后的各道工序时间相加（M5+M6+M7），得到TG=5+3+2+6=16，TH=5+2+3+4=14，则G、H的排序按T值从大到小为GH。按首道工序加工时间大于尾道工序加工时间的工件，首道工序加工时间等于尾道工序加工时间的工件，关键工件，首道工序加工时间小于

10、尾道工序加工时间的工件的顺序进行全排，获得FCDEABGH。 表2 总流程时间计算结果 零件工序FCDEABGHM12(2)6(8)9(17)1(18)3(21)8(29)8(37)7(44)M25(7)2(10)4(21)7(28)13(41)2(43)6(49)7(56)M30(7)10(20)9(30)6(36)7(48)16(64)7(71)4(75)M414(21)8(29)10(40)11(51)15(66)7(73)8(81)9(90)M511(32)7(39)12(52)5(57)6(72)4(77)5(86)5(95)M68(40)8(48)2(54)10(67)6(78)6

11、(84)3(89)2(97)M710(50)7(57)2(59)15(82)2(84)10(94)2(96)3(100)M85(55)10(67)10(77)1(83)8(92)7(101)6(107)4(111)注：（ ）内表示流程时间计算情况表3 与关键工序法求解结果比较算法排序最大流程时间Fmax改进后算法FCDEABGHFmax=111关键工序法FCDAEBGHFmax=1234算法测试与比较通过MATLAB程序对问题进行100次仿真，将关键工序法和文中提出的改进方法进行了对比。结果如图1所示：图1 不同规模Flow-shop求解结果比较a) m=50,n=50b) m=100,n=1

12、00c) m=150,n=150d) m=200, n=200可见，本文所提出的改进方法普遍优于原本的关键工序方法。当所要求解的Flow-shop问题规模较小时,如图1中 a）所示，改进方法不略于关键工序法。但两条曲线几乎重合，优势比较小。这说明在规模较小的Flow-shop问题中，关键工序法依然十分有效。然而，当问题规模较大时，如图1中b）所示，本文中的改进方法明显优于关键工序法。这说明关键工序法在大规模问题中，相对于最优解将产生明显偏差，并且这种偏差是随着问题规模的扩大而增大的。而本文所提出的改进算法，恰恰弥补了关键工序法在大规模Flow-shop问题中表现较差这一问题。5参考文献1 Li

13、u Lili Tang Guochun. A Branch and Bound Approach and Heuristic Algorithms for Scheduling a Batching MachineJ.2004,8(3):39-44.2REEVES C R. A genetic algorithm for flowshop sequencingJ.Computer and Operations Research,1995,22(1):5-23.3RAJENDRAN C,ZIEGLER H. Ant-colony algorithms for permutation flowshop scheduling to minimize makespan/total flowtime jobsJ. European Journal of Operational Research,2004,155(2):426-4384 叶春明 生产计划与控制M，北京：高等教育出版社，2005：391-400。5WOO H S, YIM D S. A heuristic algorithm for mean flowtime objective in flowshop shcdulingJ. Com