一种新型逻辑智能推理方法在混流生产线排产优化中的应用

王献红　史国权

1.长春理工大学，长春，130022　　2.长春轨道客车股份有限公司，长春，130062

一种新型逻辑智能推理方法在混流生产线排产优化中的应用

王献红1,2史国权1

1.长春理工大学，长春，1300222.长春轨道客车股份有限公司，长春，130062

针对有多个工作站、同一工作站中有不同效率并行机、各工作站之间有缓冲区、允许工件有等待条件下的混流生产线排产优化问题，提出了一种逻辑智能推理方法与遗传算法相结合的问题求解思路,解决了针对该典型问题求解排序长度时存在的数学建模及计算较为复杂的问题。

并行机；缓冲区；混流生产线；逻辑智能推理方法；遗传算法

0　引言

在混流生产线中，无等待(no-wait)自动化制造系统指工件在一个工作站完成加工后，必须立即搬运到下一个工作站[1]。文献[2]研究了具有任意工作站数目的无等待自动化系统，并为该系统提出了一种多项式的调度算法。并行机是指在加工时间特别长的瓶颈工作站上设置的多个同时加工工件的工作机器。文献[3-6]研究的都是工作站中加工工件无等待问题，文献[7]则研究了有等待的问题，文献[3-7]在研究求解问题时均采用了数学建模求解的方法。文献[1]研究了工作站存在并行机的调度问题，采用的也是数学建模求解的方法。文献[8]研究了工作站中有缓冲区的问题，并将遗传算法与调度规则相结合采用数学建模的方法求解了该问题。上述研究都存在着局限性，即没有在混流生产线条件下将“多工作站”、“同一工作站中有不同效率并行机”、“各工作站之间有缓冲区”、“允许工件有等待”四个因素放在一起展开研究；另外，现有文献对问题的求解方法基本都是采用数学建模的方法，数学建模求解对简单的问题比较容易，而对上述四个因素并存的情况会十分困难。

在生产实际中，很多企业在多工作站混流生产线的各个工作站之间设立缓冲区，其目的是缩短生产中某个或某几个工作站的闲置时间，同时还可以规避因某个工作站出现偶发问题导致的整个生产线停工的问题。企业实际生产中普遍存在某些工作站甚至是全部的工作站中有并行机的现象，甚至并行机的规格型号与效率并不相同，因此研究混流生产线具有多工作站、工作站间有缓冲区、某些工作站内具有不同效率的并行机、允许工件有等待这样的典型排产优化问题具有重要意义。本文在上述背景及各缓冲区规模确定条件下提出一种新型逻辑智能推理方法应用于求解排序长度的排产优化问题，规避建模求解问题的复杂性。

1　问题模型

设有H个工件,某个工件标记为Hi,其中i=1,2,…,I;生产线共有S个工作站，Sj表示第j个工作站,j=1,2,…,J;至少有一个工作站有并行机,用mSj表示工作站Sj所具有的并行机数量，即mSj≥1。各工件必须以相同的顺序依次通过流水生产线的全部工作站；任何两个相邻工作站之间设有一个容量合理的缓冲区,缓冲区的工件按照先进先出的原则依次排队；每个工件在一个工作站中只能被一个设备加工；当工件在某个工作站设备上完成加工，而该工作站的紧后缓冲区中没有空闲的位置存放时，则该工件只能在原设备上等待，直到紧后缓冲区中有空闲的地方或下一个工作站至少有一个空闲的设备为止。本文的排产目标是确定一个排产方案，包括确定投入顺序、每个工件在每个工作站中所使用的加工设备、各工件在每个工作站的开始加工时间及结束时间，使得优化目标值最优。

其他问题约束条件是：①各工作站的同一台设备同一时刻最多只能加工一个工件；②同一个工件在同一时刻只能被一台设备加工；③所有的工件一旦被设备加工则加工不能中断，直至加工完成为止；④每一个工件之间具有相同的加工优先等级；⑤全部工件在0时刻均可以被加工；⑥对于任意一个工作站而言，各工件对应各并行机的效率参数是已知的,即任意一个工件在生产线上的任何一台设备上的加工时间是确定已知的；⑦各缓冲区容量是固定的。

2　评价指标

在这里选取“排序长度”作为优化指标。排序长度又可称为最大流经时间或制造周期，它是生产实际中经常被关注的指标，它是评价排产方案优劣的最根本的指标之一，特别能说明生产线效率的高低。为了问题说明与表述的简单，我们在这里定义任意一个投入顺序最后一个工件最后一道工序完成的时间为OSJ,HI,则优化目标为M=minOSJ,HI。

3　逻辑智能推理方法

3.1.1推理方法

(1)随机生成一个生产线投入序列，将序列的前S1m个工件同时安排在第一个工作站的设备中；如果第一个工作站中的并行机效率不同，则按工件序列顺序逐个将工件优先安排在效率较高的设备上，即工件序列中排列在前的工件优先选择效率较高的设备。初始加工时间设定为“0”时刻。

(2)在上述基础上对第一个工作站进行安排。如果第一个工作站的某个设备首先完成了工件的加工，则将完成的工件转移到第二个工作站，并将该工件安排在第二个工作站中效率最高的设备上;第一个工作站空闲出的设备被安排加工剩余待投入序列中的当前第一个工件；第一个工作站中第二个加工完成工件空出的设备再被安排加工剩余待投入序列中的当前第一个工件；第一个工作站中第二个完成工件优先被安排在第二个工作站中目前处于空闲状态、且效率处于当前第一高的设备上加工,如果第二个工作站只有一台设备没有并行机或第二个工作站目前没有空闲设备则将该工件放入缓冲区中空闲位置的最前端；依此类推，第一个工作站中所新出现的每一个空闲设备都被安排加工剩余待投入序列中的当前处于第一个的工件。

(3)对第二个工作站或对其后任意工作站Sj进行安排。如果本工作站有空闲设备，则将紧前缓冲区中的排序为最前面的工件安排在效率最高的空闲设备上加工，同时该缓冲区中剩余的待加工工件位置前移；依此类推，直到将本工作站的所有加工设备排满为止。如果紧前缓冲区没有工件则只能等待前一个工作站在未来最近期完工的工件，此时本工作站产生了空闲设备。

(4)如果工作站Sj中有完工的工件，而其紧后缓冲区没有空闲位置且Sj+1工作站中的设备均处于加工中，则Sj工作站中的处于停止加工但又不能将工件卸下的设备处于堵塞状态；如果前面工作站有并行机且同时有2个或多个工件同时完成加工，则遵循以下规则：缓冲区排列在先的工件优先选择下一个工作站的加工设备。

(5)当所有工件通过最后一个工作站完成了全部的加工任务后，最后一个完工的工件的结束时间即为排序长度。

(6)在流水线的一个排产循环完成后，所有的工作站复位，回到第一个排产循环的初始状态。

3.1.2时间记录器的构建

显然按上文的逻辑关系，由于对具体某一个随机产生的投入序列来说，投入序列是确定的，加之设备使用规则也是确定的，且对于任意一个工作站而言，其内部的各并行机的效率排序及任意一个工件在生产线上的任何一台设备上的加工时间是已知的，所以可以推论出，只要按上文的规则开发编制一个合适的程序软件就可以将所有工件的加工过程进行仿真计算，并记录下每个工件在任意一个工作站中的某个设备上的开始时间和结束时间，任意投入序列方案的排序长度可以求出。3.2遗传算法

显然如何在有缓冲区及不同效率并行机混流生产线中确定排产投入顺序的问题同样也是排产优化问题。当多个不同规格的工件依次投入到生产线上进行加工时，需要给各个工件排定一个加工投入的顺序，当然这样的排产顺序方案很多，我们要确定采用哪个排产方案以使某个指标最优。对于任意一个排产方案可以通过上述的逻辑智能推理方法来计算出该方案的排序长度，可以采用遗传算法进行排产方案的全局搜索，对于遗传算法搜索出的全部排产方案进行逻辑智能推理计算比较就可以求出最优的排产方案。需要说明的是，其编码规则推荐使用矢量编码方式，即将各个工件以实数编码，如有I个工件，分别为其标记为1，2，…，I即可，则种群染色体个体即某排产投入顺序的形式可为(3，7，1，4，5，2,9,10,6，8)，此时I=10。此处要注意标记工件身份的编码与排产序列中的第几个工件的序列号的区别，前者代表某个工件，后者代表工件在某个染色体个体中的序列号。推荐的遗传算法参数的选择如下：交换率Pc=0.4，变异率Pm=0.04，初始种群数量为10～30，最大迭代次数为100～300；选择采用轮盘赌法，排序长度作为适应值函数。遗传算法参数的选择确定可以根据问题的实际规模试算调整，本文只提供解决问题的思路。

4　仿真算例

为了便于测试，本文只选择3个工件及3个工作站，且每个工作站有2台并行机设备的情况(表1)，工作站间设缓冲区，缓冲区容量均为1。测试模型的简化并不影响测试的意义。

表1　工件与设备的对应加工时间表

遗传算法共搜索到6种排产方案,仿真计算结果如表2～表8所示。

由仿真结果可见,上述问题模型的最优排产序列为1→2→3，1→3→2，3→1→2，3→2→1，此时排序长度为19。

表2　染色体(1，2，3)

注：括号内为开始时间，括号外为结束时间。

表3　染色体(1，3，2)

表4　染色体(2，1，3)

表5　染色体(2，3，1)

表6　染色体(3，1，2)

表7　染色体(3，2，1)

表8　各染色体排序长度

5　结语

本文所推荐的一种逻辑智能推理方法可以求解任意一个混流生产线的排产方案的排序长度值，而该方法与遗传算法的全局搜索特性相结合就可以求解有多个工作站、有缓冲区及不同效率并行机、允许工件等待的混流生产线的排产优化问题，仿真测试结果证明了该方法有效可行。

[1]车阿大，宴鹏宇，杨乃定.复杂无等待自动化制造系统的调度算法研究[J].计算机集成制造系统，2007,13(8)：1-3.

Che Ada,Yan Pengyu,Yang Naiding.Polynomial Algorithm for Cyclic Scheduling of a Complex No-wait Robotic Production System [J]. Computer Inte-grated Manufacturing Systems, 2007,13(8)：1-3.[2]Levner E,Kats V,Levit V E.An Improved Algorithm for Cyclic Scheduling in a Robotic Cell[J].European Journal of Operational Research,1997,97(3):500-508.

[3]Che Ada, Chu Chengbin, Chu Feng. Multicyclic Hoist Scheduling with Constant Processing Times[J].IEEE Transactions on Robotics and Automation,2002,18(1)：69-80.

[4]Liu J Y，Jiang Y. An Efficient Optimal Solution to the Two-hoist No-wait Cyclic Scheduling Problem[J]. Operations Research,2005,53(2):313-327.

[5]Leung J M Y，Levner E. An Efficient Algorithm for Multi-hoist Cyclic Scheduling with Fixed Processing Times[J].Operations Research Letters,2006,34(4):465-472.

[6]Che Ada, Chu Chengbin.Multi-degree Cyclic Scheduling of Two Robots in a No-wait Flowshop[J].IEEE Transactions on Automation Science and Engineering, 2005,2(2):173-183.

[7]赵振宏，肖田元. 机器人制造单元的建模与任务调度策略[J].计算机集成制造系统，2001,7(4)：7-11.

Zhao Zhenhong, XiaoTianyuan. Modeling and Task Scheduling Strategy for Robot Manufacturing Cell[J]. Computer Integrated Manufacturing Systems,2001, 7(4):7-11.

[8]吕文彦，党延忠.基于B-T规则与遗传算法的可重入生产系统调度[J].系统仿真学报，2005,17(4)：993-996.

Lü Wenyan, Dang Yanzhong. Scheduling Re-entrant Lines Based on GA and Integrated Rule[J]. Journal of System Simulation, 2005,17(4):993-996.

(编辑王艳丽)

Applications of a New Logic Intelligent Inference Method in Scheduling Optimization of Mixed Production Lines

Wang Xianhong1,2Shi Guoquan1

1.Changchun University of Science and Technology,Changchun,130022 2.Changchun Railway Vehicles Co.,Ltd.,Changchun,130062

This paper presented the optimization of mixed production line with the features of multi work stations, simultaneous operation of the same work station with different efficiencies,having buffer area among work stations,and allowing waiting for work piece.This paper proposed a solution based on logic intelligent reasoning method and genetic algorithm to tactfully solve digital modeling and complex calculation issues for makespan.

parallel machine; buffer zone; mixed flow shop production line; fuzzy logic inference;genetic algorithm

2013-07-10

吉林省重大科技成果转化项目(09ZDZH008)

TP278DOI：10.3969/j.issn.1004-132X.2015.10.008

王献红，男，1966年生。长春理工大学机电工程学院博士研究生，长春轨道客车股份有限公司高级工程师。主要研究方向为生产管理与物流管理。史国权，男，1965年生。长春理工大学副校长,机电工程学院教授、博士研究生导师。