订单优先权的置换流水线订单排序问题

第 l0期2013年 l0月机械设计 与制造Machinery Design & Manufacture 257订单优先权的置换流水线订单排序问题庞如英，申武超(内蒙古工业大学 机械学院，内蒙古 呼和浩特 010051)摘 要：不同订单对企业来说重要度不同，而传统的置换流水车间调度研究主要解决订单平等下的总完工时间最小问题。应用模糊层次分析法找到订单优先权排序，将每种订单排序与订单优先权排序进行一致程度对比，在此基础上构建了一个考虑订单优先权的置换流水车间生产调度模型，该模型能够求解综合考虑订单重要度和总完工时间的最优订单生产排序。最后运用遗传算法对该模型进行求解，并对结果进行分析，得出优先权系数 W对生产调度的指导意义。

关键词：置换流水车间；订单排序；订单优先权中图分类号：TH16；F406．2 文献标识码：A 文章编号：1001—3997(2013)1o一0257—04Order Priority Permutation Flow-Shop SchedulingPANG Ru-ying，SHEN Wu-chao(School of Mechanical Engineering，Inner Mongolia University ofTechnology，Inner Mongolia Hohhot 010051，China)Abstract：Diferent orders ale diferent important degrees for enterprises．The study on traditional Permutation Flow—shopScheduling Problem (PFSP)is always tO get the order scheduling on minimum makespan based on the principle ofthe orderequality．It colne up with the order scheduling on priority byfuzzy analytic h&r~chy，and contrasted each sort of orderscheduling tO the order scheduling on priority．Then a new PFSP model considering order priority and makespan Was proposed.

The mo del Was solved bygenetic algorithm，and the results were analyzed，and the guiding signifco2~e ofthe coeficient W toproduction scheduling Was obtaine d.

Key W ords：Permutation Flow-Shop；Order Scheduling；Order Priority1引言对于订货型(MTO，Make—To—Order)企业，当收到一批订单的时候，怎样对多品种产品组织生产，并且能够最大程度缩减交货期，满足顾客需求，是很多企业面临的问题。置换流水车间调度问题(Permutation Flow—shop Scheduling Problem，PFSP)是一类经典的加工调度问题，取得了很大的成果，但绝大多数学者的研究集中在求解最小完工时间上 ，研究的重点总是各种启发式算法的改进。

而实际上，企业往往并不是只重视总完工时间。通常他们需要综合考虑多个目标，权衡调度以实现企业整体效益最优化131。目前一些学者开始对多目标车间调度问题进行研究 ，文献嗍运用模糊逻辑和进化算法对车间调度中的总完工时间、机器总负荷以及最大负荷机器的负荷目标进行了研究；文献 建立了包括时间、成本、交货期满意度和设备利用率在内的多 目标优化模型。文献 提出了粒子群算法和局部搜索算法结合的混合算法，基于优先权对多目标的车间调度问题进行了研究。文献f7】击黾出文化基因算法来同时最小化完工时间和总流程时间。文献【捌提出贪婪随机自适应搜索方法以同时最小化两个(完工时间和最大延迟 )或三个(完工时间、最大延迟和总流程时间)目标。

以上文献都是基于订单同等重要的前提下进行的，与企业实际操作情况不符 ，一般企业要根据订单的交货期、金额等排出订单加工优先顺序。因此，试图在考虑订单优先权的基础上，对总完工时间进行适当调整，从而得出一个既考虑订单优先权，又使总完工时间相对最小的订单生产顺序。

2问题描述与依据为了分析方便，假设每个订单只对应一个产品，若一个订单包含多个产品，则可以把这个订单理解为多个订单。对置换流水线问题 ，做如下假设 ：对于 n个订单在 m台不同机器上加工 ，每个工件有m道工序，每道工序都要在不同的机器上加工，每个工件在机器上的加工顺序相同，每台机器一次在某一时刻只能加工一 个工件，每台机器加工的各工件顺序相同。每个工件在每台机器上加工的时间已知。问题的目标是求出订单的加工顺序，使得按照该加工顺序加工各订单既考虑了订单优先权，又使总完工时间相对最小。

总完工时间是从第一个订单第一道工序在第一台机器上开始加工到最后一个订单最后一道工序在最后一台机器上加工完成的时间。文献 通过对 9个工件 10台机器的加工问题进行了研究，得出其他生产排序的总完工时间相对于最小总完工时间的分布图，如图 1所示。由图 1可知，得到一个接近最小总完工时间的排序往往不止一个，图 l中阴影区域中的生产排序在总完工时间来稿日期 ：2012—12—14基金项目：内蒙古自然科学基金(2010MS0721)；内蒙古高等学校科学研究项目(NJZY12064)作者简介：庞如英，(1971一)，女，博士，副教授，主要研究方向：生产调度管理、基础IE258 庞如英等：订单优先权的置换流水线订单排序问题 第10期上差别并不是很大，但可能会因为订单排列位置不同，而使得订单的优先满足方面差别很大；另一方面，企业往往并不是最重视总完工时间，而是要考虑订单的重要程度来安排订单生产顺序。

这便需要对订单生产排序的总完工时间和订单的重要程度两个目标进行综合考虑，找到一个考虑订单的重要程度，总完工时间最小的订单生产排序。

0’00.

婪o.

0.

0·0.

1．0o 1．10 1．2O 1-30 1．4O 1．5O 1．6O相对 makespan(最优 =1)图1总完工时间Makespan实验分布图Fig．1 Empirical Distribution of T0tal Completion Time Makespan3基于优先权的订单排序模型构建3．1总目标函数构建对于两个目标，总完工时间和订单优先权，用两个指标 m和k来表示，m表示某种订单加工排序的总完工时间，k表示该种订单加工排序对应的订单优先权。m值越小表示该订单排序在总完工时间上越有竞争力，k值越小表示该订单排序在订单优先满足方面越有竞争力。当订单排序m值确定后，用k作为判断该订单顺序与最优订单优先顺序的不一致性 ，作为对总完工时间 m值的惩罚。因此，总目标函数 z为：Z=mx(1+k) (1)为了表示订单总完工时间与订单重要程度的对比，增加一个系数 ， 值越大表示保证订单优先权越重要，反之表示总完工时间越重要，于是总目标函数 Z改进为：Z_m×(1+wxk) E[0，1] (2)上式可以看出，当w=O的时候 Z=m，即总目标就是总完工时间最小 ，由此可以看出，经典的求总完工时间最小置换流水线问题只是本模型的一种特殊情况。

3．2订单优先权k的确定图2订单优先权评价指标Fig．2 Evaluation Index of Order Priority一 个订单对企业的重要程度受很多因素的影响，且不同部门，会有不同的观点和看法，销售部门关注顾客的需求和订单的金额，生产部门则注重生产成本等。从整个企业看，将影响因素归为三类，一类是客户方面的，另一类是产品方面的，第三类是订单本身方面的。因此评价订单重要度的指标，如图2所示。

依据图2各指标，运用模糊层次分析法得出每个订单的权重，然后按订单权重从大到小进行排序，即可得到一个基于订单优先权的订单加工排序，称之为订单优先权排序。用矩阵 表示它，如表 I所示。对于任一订单排序，为了表示其与订单优先权排序的非一致性程度，用对应权重差的绝对值之和来比较，因此只要找到该订单排序对应的权重值。将陔订单排序和其对应的权重组成一个两行列的矩阵，设为 y，第一行为订单的序号，第二行为对应权重。于是可求出Y矩阵与 矩阵第二行权重对应相减绝对值之和k 。Jj} 值越大表示该顺序与订单优先权顺序越不一致，即相对重要的订单可能排在相对靠后的位置。

表 1 矩阵( l≥ 2≥ 3≥??≥ )Tab．1 Matrix X(wI≥ 2≥ 3≥??≥ )为了使订单优先权 k值在[O，1]范围之内，要找到优先权最差的订单排序(订单优 顷序的倒序)，求出其k ，记为K，则k=k／K。k=0是按订单优先权排序情况下得到，k=l是优先权排序的倒序情况下得到。

4模型求解与分析假设有 25个订单，10台机器完成的问题，各订单占用各机器的时间矩阵，如表 2所示。应用模糊层次分析法得到订单优先权排序 的矩阵，如表 3所示。

表 2各订单在各机器上的加工时间矩阵 ATab．2 Processing Time matrix A of Al Orderson Every Machine14 15 16 l7 l8 l9 20 21 22 23 24 25m ， n加坞 M 4 舵卯 ，●
” 如 铝 7 44 铝m卯 ¨ 们 6犍 加O 2 ¨ "卯 勰 ∞如 钙 钙 卯； ； mNo．100ct．2O13 机械设计与制造 259表 3订单优先权排序Tab．3 Order Priority Sequence订单号 23 l7 l3 25 8 14 10 19 1 7 16 9 3优先权 黑订单号 15 5 2 21 12 4 22 6 11 18 20 24优先权 篓 04．。 00。．20由于 个订单的排序有 !种，当 足够大时很难求出最优解，属于NP难问题，因此采用遗传算法来求解模型。遗传算法各参数为：种群个体数为2O，种群数为50，代沟为0．8，变异概率为0．7，种群迁移率为0_2，迭代次数为400。

4．1结果分析当系数 =0时，即不考虑订单优先权，这种情况是典型的求总完工时间最小问题，其寻优过程如图3所示。得到订单的加]：顺J芋为 ：12—1O—4—25—2—18-1 1-20—22～6—23—24—8—9—15—1—7一l9一l6—13—3—5—14—17—21。该排序即为最小完工时间排序，综合得分 z与总完工时间m均为 890；订单优先权 k是波动的，最优值为 0．7009。

当系数w--O．2时，运用本模型对其进行求解，求解过程，如图4所示。求得最优的汀单加工顺序为 ：l2一l一25—23—8—10—14—19—2—17—20-22—9—15一l3—3—16—7—4—6—11-5—18—24～21。该{j#， 即为综合最优排序。综合得分z为 967．48，实际的总完工时间 m为901，对应订单优先权 k为0．36694。

匿譬确腔Ⅱ匿留寻优过程一 综 合得 分◆ 总完T时间? 订举顺序得分． ? 0?l一-l■ ? ．L ^I：盼 l； i? ‘}? 一’ 。 ：迭代次数图3 w=0时求解结果Fig．3 Results When w=O难世鳖妞LI 惫龛罕·I 订单顺序得分—～ 。
、 重 一 ． I一JJ— - 一 ' ●0 50 100 l50 2oo 250 30 350 400迭代次数图4 w=O．2时求解结果Fig．4 Results When w=O．2为了便于分析 ，将 25个订单按订单优先权排序分成 5类，分别用A，E，，，O，U表示非常重要、重要、一般重要 、不重要、非常不重要，如图5所示，并加入总完工时间最小和综合最优的排序。

由图 5可知，总完工时间最小排序的A区，有三个 O区的订单(12、4、2)和一个E区的(10)，而综合最优排序的 Ⅸ，只有一个O区的订单(12)和一个 E区的(1)，说明最小完工时间订单排序中有三个不重要的订单占据了非常重要的位置，而综合最优订单排序中只有一个。同理分析其它四个区，不难得出综合最优订单排序比最小完工时间订单排序合理。而且仅使总完工时间增加了9个单位，即最小完工时间 890的 1．O112％，因此在需要考虑订单的优先权时(如 w-O．2)，增加约 l％的加工时间来换取一个更加合理的订单排序是值得的。证明了本模型在选择最优订单／JHI／I~.

序时是有效的。

图 5结果分析对比Fig．5 Analysis and Comparison on Results4．2系数 对生产调度的指导意义为了研究系数埘对总完 时间m和订单优先权 的影响，绘制总完工时间 m，订单优先权 ，综合得分 z随系数 的变化情况，如图6所示。由图6可知，综合得分会随着 “，的增加而增加；总完工时间总体也会随着 的增加而增加，但是在 增加剑一 定值时，总完工时间增加停止或者不明显；订单顺序得分总体随着 的增加而减少，但是同总完工时间一样 ，当 增加到一定值时，其减少会停止或者不明显。因此，表明 在0端(如本例[0，0．6])的调节作用相对明显，当w=0．6时，得到的综合最优解基本上就是最倾向于订单优先权的加工顺序，再大订单优先权排序效果几乎没有改善，反而可能会使总完工时问增大。

亘蓄确睡≈厦鲁各指标随 值变化情况图I?综合得分 l ==异蕈孟譬分
一 ．．_ I．．-订单顺序得分I 一 。

：：：；--
● ● ， ● ● ， - ，
， ●、、’ 一 ● - ● _ ● ● 、 ／／： 。： ：，二 ，
_ _ _ - - _ ● ● l，、～ 、 ：l ～
、
、 ，／1"变化值图6各指标随 值变化情况图Fig．6 Change of All Evaluation Index with I／)通过以上分析可知系数 在本模型中有很重要的作用 ，对生产调度的指导意义为：当决策者倾 向于总完丁时问最小时 ，W取值应该尽量小；当决策者更加倾向于订单优先权这个 口标时，取值应该稍微大些。

0 一末 斟．f_t一叵鲁H撇踊岬求 如婚一厘鲁机械设计与制造No．10Oct：201 35结论综合考虑总完工时间和订单优先权两个目标，建立了综合排序最优模型，该模型不但能够解决传统的置换流水线排序问题(w-0)；而且还可以通过调节w的大小，来解决综合考虑总完工时间和订单优先权的最优订单加工顺序。w越大说明订单优先权比较重要，模型计算出来的结果偏向于和订单优先权排序一致的加工顺序；w越小说明总完工时间比较重要 ，模型计算出来的结果偏向于总完工时间最小的加工顺序。

相对于传统的求解最小完工时间为目标的订单生产排序模型，本模型考虑了更多的因素，并将这些因素综合为订单优先权指标，因而更加符合实际的生产调度管理，对现实的生产管理活动也更具参考意义。

参考文献[1]Laha D，Chakraborty U K．An eficient hybrid heuristic for makespanminimizationinpermutationflowshopscheduling LJJ．InternationalJournalofAdvancedManufacturingTechnology，2009(44)：559-569.

[2]于承敏，郑丽萍，张民．粒子群算法解决置换流水车间调度问题方法综述[J]．机械设计与制造，2012(8)：84．86.

(Yu Cheng—min，Zheng Li-ping，Zhang Min．A survey of the methods forthe particle swalITI optimization algorithm to solve the permutation flowshop scheduling problem [J]．Machinery Design＆Manufacture，2012(8)：84—86．)[3]Behnamian J，Fatemi Ghomi S M T，Zandieh M．A muhi—phase coveringPareto-optimal front method to multi-objective scheduling in a realistichybrid flowshop using a hybrid metaheuristic[J]．Expea Systems withApplications，2009(36)：11057-11069.

[4]Imed K，Slim H，Pierre B．Pareto optimality approach for flexible j0b—shop scheduling problems：hybridization of evolutionary algorithms andfuzzy logic[J]．Mathematics and Computers in Simulation，2002(60)：245—276.

[5]吴秀丽，孙树栋，余建军．多目标柔性作业车间调度优化研究[J]计算机集成制造系统，2006，12(5)：731—736.

(Wu Xiu—li，Sun Shu—dong，Yu Jian-jun．Research on multi—objectiveoptimization for flexible job shop scheduling[Jj．Computer IntegTatedManufacturingSystems，2006，12(5)：731—736．)[6]Moslehi G，Mahnam M．A pareto approach to multi-objective flexiblejob—shop scheduling problem using particle swami optimization and localsearch[J]．International Journal of Production Economics，201 1(129)：14—22.

[7]Chiang Tsung—che，Cheng Hsueh-chien，Fu Li-chen．NNMA：Anefective memetic algorithm for solving multi—objective permutation flowshop scheduling problems [Jj_Expea Systems with Applications，2011．38(5)：5986—5999.

[8]Aroyo J C，De Souza Pereira A A．A GRASP heuristic for the multi—objective permutation flowshop scheduling problem [J]．InternationalJournal ofAdvancedManufacturingTechnology，2011，55(5-8)：741-753.

[9]Tailard E．Some eficient heuristic methods for the flow shop sequencingproblem[J]．European Journal of Operational Research，1990(47)：65-74.

(上接第 256页)5结束语基于物联网的振动监测系统适用于机组环境较为恶劣的工业场所，例如风力发电机 。系统的 Wif无线网络的传输为实时监测的操作人员提供了很多方便，提高了设备故障诊断的可靠性和设备管理的自动化水平，为设备的安全稳定运行提供了依据和保障 。

参考文献[1]陈磊，韩捷，孙俊杰．基于嵌人式技术的机械故障诊断巡检系统研制[J]．仪表技术与传感器，2007(10)：27—29.

(Chen Lei，Han Jie，Sun Jun-jie．Inspection mechanical fault diagnosissystem research based on embedded technology[J]．Instrument TechniqueandSensor，2o07(10)：27—29．)[2]许飞云，胡建中，贾民平嵌入式旋转机械状态监控与故障诊断系统研究[J]-东南大学学报，2004，34(6)：761．765.

(Xu Fei—yun，Hu Jian-zhong，Jia Min—ping．The embedded rotatingmachinery condition monitoring and fault diagnosis system research[J].

Journal ofSoutheast University，2004(6)：761—765．)[3]陈磊，韩捷，孙俊杰．基于嵌入式技术的设备状态监测与故障诊断系统设计[c]．2008年全国振动工程及应用学术会议暨第十一届全国设备故障诊断学术会议，2008(Chen Lei，Han Jie。Sun Jun-jie．Equipment condition monitoring andfault diagnosis system design based on embedded technology [C]．The2008 National Conference on Vibration Engineering and Application ofand the 1 lth National Equipment Fault Diagnosis Colloquium，2008．)[4]薛伟，董辛曼．面向物联网的设备状态监测系统关键技术研究[D]．郑州：郑州大学 ，2012(5)：19—21.

(Xue Wei，Dong Xin-min．Key equipment condition monitoring systemtechnology research for the Internet of things[D]．Zhengzhou：ZhengzhouUniversity，2012(5)：19—21．)[5]杨亮．13．56MHzRFID阅读器的硬件设计与实现[J]．科技广场 ，2007：2l7-219.

(Yang Liang．13．56 MHz RFID reader hardware design and realization[J]．ScienceandTechnologyPlaza，2007：217—219．)[6]邹思轶．Linux嵌入式设计与应用[M]．北京：清华大学出版社，2002.

(Zou Si-yi．Linux embedded design and application[M]．Beijing：TsinghuaUniversity Press，2002．)f7]袁冬梅 ，罗辑，唐毅锋．数控机床振动监测系统设计[J]．2007(4)：221—224.

(Yuan Dong-mei，Luo Ji，Tang Yi—feng．Numerical control machine toolvibrationm0nitoring sy8temdesign[J]．20o7(4)：221—224．)f8]张晓莉，刘晓波．水轮发电机组振动监测软件系统的开发[J]．机械设计与制造，2010(1)：222—224.

(Zhang Xiao-li，Liu Xiao-bo．Hydroelectric generating set vibrationmonitoring software system development[J]．Machinery Design and Manu—facture．2010(1)：22 一224．)