具有复杂缓冲的分段多流水车间调度问题

张志英，代乙君，隋毅

(1.同济大学 机械与能源工程学院，上海200092;2.上海江南长兴造船有限责任公司，上海201913)

流水车间的调度问题在离散制造业中是最常见的一类生产调度模式，这类问题受到了较多的关注，并被证明为NP-hard问题［1］。由于现实生产中存在很多制约条件，使得经典的流水车间调度模型生成的调度变得不可行，需要实用性较好的调度方案。船舶企业在制定生产计划时按照分段的加工顺序依次排产，缺乏对各个车间以及堆场中调度的整体考虑，导致实际生产中“前拖后赶”的情况，造成生产低效率和工期延误。

近年来，许多学者从理论和算法上对典型流水车间调度问题进行了较为深入的研究，HEJAZI R等对以制造期为优化目标的典型流水车间调度问题进行了较为详细的总结［2］。但基于机器间带无限缓冲的假设在实际中往往是无法满足的。有学者研究带有限缓冲或不存在缓冲的流水车间调度问题。张其亮等对带有阻塞限制的混合流水车间调度问题进行优化求解［3］;刘世强等［4］分别对典型流水车间调度问题、带阻塞的流水车间调度问题、无等待的流水车间调度问题和带有限缓冲的流水车间调度问题进行了分析。目前求解流水车间调度问题的优化方法主要有精确计算法、构造法和智能计算法，精确算法主要包括规划法等，但只适用于中小规模的问题，构造法是从局部最优中寻找全局最优的方法，适合局部搜索，其中NEH(Nawaz Enscore and Ham)被公认为是最好的构造法;智能算法例如遗传算法，应用广，但有时计算效率不高［5］。较多学者用智能算法对带阻塞的混合流水车间调度问题进行了研究［6-8］。

具有复杂缓冲的分段多流水车间调度问题与带缓冲的单流水车间调度有一定的相似性，但由于船舶分段加工的特殊性、堆场与流水车间内缓冲的区别，使得该问题更加复杂。船舶分段的返工、堆场中分段重调度以及阻塞是船舶建造经常出现的情况，如果不能合理的协调解决，会降低设备的利用率、延长建造周期。目前对多流水车间的整体调度问题研究的文献较少。考虑缓冲的流水车间调度的研究中，工件在缓冲中大部分是遵从先进先出(first in first out，FIFO)规则［9-11］，但船舶分段在车间之间的堆场中并不受FIFO规则约束，所以多流水车间调度需在缓冲中对工件进行再排序来优化调度。

本文根据船厂的实际生产运作情况，提出了考虑分段生产的多流水车间调度模型，设置3种不同的缓冲类型，考虑缓冲中工件重调度和返工，建立调度模型，并利用某船厂的数据进行实例验证。

1 问题描述和数学模型

1.1 问题描述

区别于传统的机器间有无限缓冲、工件的加工顺序相同，且在缓冲中都遵从FIFO规则的典型流水车间调度问题，该问题包括车间内部的调度问题和相邻车间缓冲中的调度问题。其特殊性有:

1)复杂缓冲:存在3种缓冲类型，分别为无限能力缓冲、无缓冲和有限能力缓冲。

2)缓冲能力不确定:对有限能力缓冲，由于工件的面积各异，而缓冲的面积确定，所以缓冲中能存放的工件数量不确定。

3)缓冲重调度:在车间之间的缓冲中对工件进行再排序。

4)返工:当工件在某一台机器上的阻塞时间超过阻塞时间限制上限时，工件需在当前机器上重新加工，返工次数不限。

该问题可以描述为:H个工件依次经过G个流水车间加工，不同车间内机器数量不同，工件进入车间后从机器1到Mg依次进行加工，机器是串联的，并且机器间不存在缓冲。工件需依次经过所有车间的所有的机器加工后才可离开。

整个加工过程分为2个部分，车间内完工后的工件进入缓冲中，在缓冲中完成重调度的工件依次进入下游车间。车间内工件的加工顺序作为下游缓冲重调度的输入，重调度的结果作为下一车间工件加工顺序的输入，工件的返工又会反过来影响缓冲重调度。多车间调度如图1所示。

图1 多车间调度Fig.1 Multi-shop scheduling

1.2 具有复杂缓冲的分段多流水车间调度模型

1.2.1 假设条件

1)工件在机器上加工时不可中断;

2)工件的移动时间不计;

3)准备时间包含在加工时间中;

4)工件依次经过机器的顺序相同;

5)每台机器每次至多可以加工一个工件，每个工件每次至多被一台机器加工。

1.2.2 数学建模

1)车间内调度。

加工的第一个工件的完工时间和离开时间表示为

式中:G表示车间(g=1，2，…，G)，Mg表示机器(m=1，2，…，M)，πg(h)为车间g内按照 πg排序后的第h个工件为完工时间表示离开时间表示加工时间。

缓冲0中的工件进入车间的时间表示为

车间内工件在机器上的完工时间表示为

工件离开车间和缓冲的时间表示为

式中:表示工件h到达缓冲g的时间。

工件在车间内和缓冲中的阻塞时间表示为

式中:表示阻塞时间。

2)车间之间调度。

工件的返工条件表示为

式中:Z为阻塞时间上限。

工件离开缓冲的时间表示为

式中:表示离开缓冲g的时间。

缓冲的面积限制表示为

式中:bg为缓冲g的面积大小，rπg(h)表示工件的面积。

能力之内和受能力约束工件的最早开始加工时间分别表示为

工件离开缓冲的时间表示为

式中:βhg为0～1变量，1表示工件h发生了重调度，否则为0;Xfh为0～1变量，1表示工件f为工件h的前一个工件，否则为0;Xf＇h为 0 ～1 变量，1 表示工件f＇为工件h在缓冲中重调度后的前一个工件，否则为0。

所有工件的完工时间表示为

3)目标函数。

模型的目标函数表示为

同一个工件同一时刻最多只能在一台机器上加工，一台机器每次至多加工一个工件，此约束表示为

式中:ψπg(h)mz为0～1变量，1表示车间g内的工件在机器m上，否则为0。

工件可能出现阻塞表示为

加工顺序的约束表示为

缓冲中重调度、返工次数为非负值表示为

2 启发式算法

用于求解流水车间调度问题的算法主要有构造型和通用型启发式算法，其中NEH算法被公认为目前构造型启发式算法中的最优算法［12］。遗传算法(genetic algorithm，GA)可根据实际问题灵活的变换编码方式来缩小搜索空间，但对交叉变异算子有较大的依赖性［13］。为了在合理的时间内找到所描述问题的较优解，利用NEH算法在初始序列排序方法和其后的工件插入步骤方面的优势［12］，生成车间1内工件的加工顺序，根据工件的相似度选择进入下游车间的工件，利用GA灵活的编码方法，采用基于工件加工顺序的染色体编码方式，根据问题设计交叉变异算子。结合NEH和GA的优点，构建构造型启发式算法，求解步骤见图2。

图2 启发式算法步骤Fig.2 The procedure of the heuristic algorithm

2.1 基于NEH的迭代插入算法

NEH算法的思路为按工件总加工时间的降序对工件排序，再依次取出工件进行迭代插入操作。但当机器之间的缓冲面积很小或不存在缓冲时，按总加工时间的降序排列会使工件的阻塞时间远大于按升序排列的情况［11］。由于车间内不存在缓冲，用NEH算法产生第一个车间内工件的加工顺序时，按照总加工时间的升序排列。

2.2 染色体编码方式

采用基于工件加工顺序的染色体编码方式，将工件在各车间内的加工顺序、车间序号、工件的编号直接作为染色体的组成。这种编码方式将工件数作为染色体的空间维度，缩小问题的搜索空间，工件的加工顺序信息包含其中，减少染色体的存储空间。设X=((［1］，［1］，π［1，1］)…(［H］，［G］，π［H，G］))为种群中的一条染色体，基因(［h］，［g］，π［h，g］)表示进入车间g的第h个工件为π［h，g］。

2.3 启发式算法的规则

首先根据2.1中的算法产生第一个车间内工件的加工顺序R1，然后根据启发式算法的步骤产生其他车间内工件的加工顺序R2至RG。可行的加工顺序必须符合以下规则:

规则1:0＜g≤G，0 ＜h≤H，(［h］，［g］，π［h，g］)须在(［h-1］，［g］，π［h-1，g］)离开当前的机器后开始加工。

规则 2:任意一条染色体的基因(［h］，［g］，π［h，g］)须包含h∈(0，H)，g∈(0，G)的所有组合，并且h和g按照从小到大的顺序依次取值。

规则1保证只有当下游的机器空闲时，当前的工件才可能移到下一台机器;规则2保证所有的工件从最后一个车间出来时已经完成了所有的操作。

2.4 初始种群构造算法

初始种群构造步骤如图3所示。图3中，B是缓冲可用面积，r为相关度系数，其计算公式为

式(21)表示车间g+1内机器1上正在加工的工件与目前缓冲g中工件加工时间的差值，值越小表示两工件的相关度越高。

图3 初始种群产生步骤Fig.3 The procedure of generating the initial population

2.5 交叉和变异

由于GA对交叉变异算子有较大的依赖性，本文根据模型设置交叉变异概率计算公式。对交叉操作，在种群中随机选择2条染色体作为父代，然后从左到右依次扫描每项基因，提取工件的排序信息。［g］相同时，按照［h］从小到大的顺序依次将提取的π［h，g］组成序列Rg，即为车间g内工件的加工顺序。接着将提取的父代染色体的加工序列信息进行两点交叉。只有［g］相同的基因可两点交叉，提高求解速度。交叉概率如下

式中:为同一台机器上所有工件加工时间的均值。

变异操作，类似于交叉操作，从父代染色体中提取各车间内工件的加工顺序信息，然后对［g］相同的基因按文献［14］提出的平移插入变异算子的方法进行平移操作，具体见图4，变异概率为

图4 邻域移动操作图Fig.4 The neighborhood moving operation diagram

式(22)表示阻塞时间长的工件在总加工时间长的车间内发生交叉的概率较大;式(23)表示阻塞时间长的工件在总加工时间长的车间内发生变异的概率大，但其远远小于交叉概率。

2.6 选择

选择操作同时考虑建造周期与阻塞时间，并按照目标函数值从小到大的顺序对染色体排序。选择概率公式为

式中:f为适应度值，p为染色体被选中的概率，avg为平均，cur为当前染色体，ext是适应度值比均值小且最邻近均值的染色体，Popsize为种群中染色体数量。

该式表示适应度值小的染色体被选择的概率较大，且远大于适应度值大的。

2.7 适应度函数

本文的目标函数是最小化建造周期和阻塞时间，表示为

式中:λ为(0，1)之间的实数，表示权重。

3 实例验证与数值分析

3.1 实例验证

为验证模型和算法的可行性和正确性，以上海某船厂船舶分段在组立、涂装2个流水作业车间内的计划调度为例，利用Visual C#在Windows7平台上进行编程，在处理器为2.10 GHz，内存为2.00 GB的计算机上实现求解算法。

由于实际造船厂的组立车间和涂装车间没有传统意义上的流水车间的机器含义，因此，为了不失一般性，将组立、涂装车间内的工位和工位上的设备抽象为机器。

图5表示分段在船厂流水车间内的加工流程，分段在多个车间内的调度有以下特征:

1)堆场的能力不定;堆场0足以存放单位周期内的所有分段，可认为此处的堆场能力是无限制的;堆场1面积有限;分段离开堆场2的时间还受下游车间内机器加工情况的限制，设为能力无限型。

2)车间内部为带阻塞的流水车间调度;船体分段重并且占用的作业空间较大，工位之间没有缓冲，加工过程中会出现阻塞［15］。

图5 分段加工流程图Fig.5 Block processing flow chart

堆场1面积为2 300 m2，分段及机器的信息见表1。

图6是用遗传算法随机运行一次得到的车间1内分段的加工顺序，图7则是假设不经过重调度，在涂装车间内仍按原顺序加工时的情况，由于分段5在机器2上的阻塞时间大于4 h，需在机器2上返工。返工造成时间和成本的很大浪费，可通过重调度减少返工发生的次数。该模型与算法同样适用于3个及其以上的流水车间调度，具体见下节。

表1 分段加工信息Table 1 Block process information

图6 组立车间内调度示例Fig.6 An example of scheduling in assembly workshop

图7 涂装车间内调度示例Fig.7 An example of scheduling in painting workshop

3.2 数值分析

假设工件在4个连续的流水车间机器上的加工时间在［3，15］间随机生成，车间内机器数在［3，10］间随机生成，缓冲面积在［1 600，2 500］间随机生成。

数值分析过程对λ取定值0.8。为证明此启发式算法有效，分别用以下方法进行比较分析。

图8、9给出了3种算法计算的建造周期和阻塞时间，建造周期1和阻塞时间1对应构造型启发式算法，建造周期2和阻塞时间2对应GA，建造周期3和阻塞时间3对应粒子群算法。用构造型算法求解时，收敛速度较慢，但其初始解和收敛解的质量优于其他2种算法，说明构造型算法在较小程度上减慢收敛速度的同时可以较大程度上提高解的质量。

图8 建造周期的对比Fig.8 The comparison of makespan

图9 阻塞时间的对比Fig.9 The comparison of blocking time

图10给出了3种算法计算的目标函数值，目标1对应构造型启发式算法，目标2对应不存在重调度时的算法，目标3对应随机产生第一个车间内工件的加工顺序的启发式算法。没有重调度时，初始解较优，但最终收敛解的质量低于构造型;用随机产生第一个车间内工件的加工顺序的方法求解时，初始解较差，但收敛较快。说明使用基于NEH的迭代插入算法产生第一个车间内工件的加工顺序会提高初始解的质量，重调度会提高收敛解的质量，同时本文的选择、交叉和变异公式，较好的克服了遗传算法早熟的缺点，可较快搜索到高质量的解。

图10 不同约束条件下运行结果对比Fig.10 The comparison of results under different constrains

表2是3种算法在不同的规模下多次运行结果的平均值，可以看出该构造型启发式算法在求解规模较大的问题时的性能仍然较优，并且随着规模的增大，利用率在逐步提高。

表2 不同规模下随机运行结果对比Table 2 Comparison of results under different dimensions

图11给出了模型中只有单一类型的缓冲时求得的阻塞时间，阻塞1对应问题中只有无限型缓冲时的结果，阻塞2对应问题中只有能力有限型缓冲时的结果，阻塞3对应问题中只有能力较小型缓冲时的结果。通过比较分析可知，分段的阻塞时间随着堆场面积的减小而较大程度地增加。

由上可知，可通过适当增大缓冲面积和增加单个生产周期内加工的工件数来提高机器的利用率。

图11 缓冲面积不同时阻塞时间Fig.11 The blocking time under different buffer areas

4 结论

通过提炼具有船厂生产特征的模型，对多个生产车间以及车间之间缓冲中的调度进行整体考虑，构造启发式算法，较大程度地缩短分段的建造周期和阻塞时间，从而减少实际生产中工期延误问题的发生。在提高调度计划适用性的同时，给求解带缓冲的多车间调度问题提供了思路。

由于研究没有考虑机器的可用性约束及分段在堆场中的移动路径等问题，因此，将更多实际约束考虑到多车间调度中需要进一步研究。

［1］WANG L，ZHANG L，ZHENG D Z.An effective hybrid genetic algorithm for flow shop scheduling with limited buffers［J］.Computers and Operations Research，2005，33:2960-2971.

［2］HEJAZI R，SAGHAFIAN S.Flowshop scheduling problems with makespan criterion:a review［J］.International Journal of Production Research，2005，43:2895-2929.

［3］张其亮，陈永生.带有阻塞限制的混合流水车间调度问题的混合粒子群求解算法［J］.信息与控制，2013，42(2):252-257.ZHANG Qiliang， CHEN Yongsheng. Heuristic particle swam optimization algorithm for the hybrid flowshop scheduling with blocking constrain［J］.Information and Control，2013，42(2):252-257.

［4］LIU Shiqiang，ERHAN K.Scheduling a flow shop with combined buffer conditions［J］.Int J Production Economics，2009，117:371-380.

［5］TAILLARD E.Some efficient heuristic methods for the flow shop sequencing problem ［J］.European Journal of Operational Research，1990，47(1):65-74.

［6］WANG X，TANG L.A tabu search heuristic for the hybrid flowshop scheduling with finite intermediate buffers［J］.Computers and Operations Research，2009，36:907-918.

［7］HAO Luo，GEORGE Q，HUANG Yingfeng.Two-stage hybrid batching flowshop scheduling with blocking and machine availability constraints using genetic algorithm［J］.Robotics and Computer Integrated Manufacturing，2009，25:962-971.

［8］GICQUEL C，HEGE L.A discrete time exact solution approach for a complex hybrid flow-shop scheduling problem with limited-wait constraints［J］.Computers ＆ Operations Research，2012，39:629-636.

［9］QIAN Bin，WANG Ling.An effective hybrid DE-based algorithm for multi-objective flow shop scheduling with limited buffers［J］.Computer ＆ Operations Research，2009，36:209-233.

［10］WANG Ling，ZHANG Liang，DA Zhongzheng.An effective hybrid genetic algorithm for flow shop scheduling with limited buffers［J］.Computers ＆ Operations Research，2006，33:2960-2971.

［11］QUAN Kepan，WANG Ling，GAO Liang.An effective hybrid discrete differential evolution algorithm for the flow shop scheduling with intermediate buffers［J］.Information Sciences，2011，181:668-685.

［12］刘心报，郭盈，程浩.一种基于NEH算法的有效求解半flowshop问题的迭代插入算法［J］.仪器仪表学报，2009，30(6):261-265.LIU Xinbao，GUO Ying，CHENG Hao.An effective iterated insertion heuristic based on NEH for the semi-flowshop problem［J］.Chinese Journal of Scientific Instrument，2009，30(6):261-265.

［13］晏鹏宇，杨乃定，车阿大.自动制造单元最小完工时间调度问题的混合启发式算法［J］.计算机集成制造系统，2010，16(4):847-854.YAN Pengyu，YANG Naiding，CHE Ada.Hybrid heuristic algorithm for the scheduling problem in robotic cell with makespan criterion［J］.Computer Integrated Manufacturing Systems，2010，16(14):847-854.

［14］MURATAT T，ISHIBUCHI H，TANAKA H.Genetic algorithms for flow shop scheduling problem［J］.Computers ＆Industrial Engineering，1996，30(4):1061-1071.

［15］张志英，李殿勤.船舶平面分段的非完全混合流水线调度［J］.计算机集成制造系统，2012，18(11):2435-2445.ZHANG Zhiying，LI Dianqin.Research on non-completely hybrid flow line scheduling of panel block in ship building［J］.Computer Integrated Manufacturing System，2012，18(11):2435-2445.