陈驻民，羊 英

(1.东华大学管理学院上海 200051;2.上海第二工业大学实验实训中心，上海 201209)

笔者研究的是非相关平行机台的混流生产中带有瓶颈的作业排序问题，非相关平行机台的混流生产在现实的生产系统中十分普遍，该现象的产生可能是由于为了扩大生产能力而在某些阶段增加了平行机台，或者由于在某些阶段存在新、旧机器的协同工作而存在非相关平行机台。存在瓶颈现象的混流生产在实际的生产系统也经常出现［1-7］，例如化工、纺织、食品和造纸等企业，这些企业在生产过程中常出现相似产品在非相关平行机上的作业排序问题，同时这些生产系统也通常会存在生产瓶颈。瓶颈的管理在生产排序中是一个非常重要的管理任务，对于带有瓶颈的生产线的排序通常分以下3个步骤来完成［8-9］:①瓶颈的识别;②瓶颈阶段的排序;③非瓶颈阶段的排序。笔者对研究的混流生产问题作如下假设:存在n个工件需要通过J个生产阶段的流水生产线，同时每个阶段均有一个或多个平行机台。

近年来很多研究者开始研究混流生产问题，但是大多数研究者研究的是多阶段的混流生产中存在相同平行机台的排序问题［10］，研究者通常采用模拟退火算法、遗传算法等搜索方法完成该问题的生产排序，但是搜索的效率存在很大的问题，同时对于研究的问题也有很多限制，而对于混流生产中非相关平行机台的问题很少有人去解决。笔者以纺织企业为例，提出了一个基于瓶颈的启发式算法在非相关平行机台生产排序中的应用，该算法的目的是为了最小化上述问题的完工时间，同时该算法的效率及适用场合优于智能搜索算法，可较好地解决混流生产中带瓶颈的生产排序问题。

1 混流生产中基于瓶颈的启发式算法

1.1 符号的定义

所提出的基于瓶颈的启发式算法用于解决非相关平行机台的混流生产作业排序，由于假设每个阶段都存在非相关平行机台，因此在每一个阶段中都使用以下3种机器选取规则:①在可用的机器中选取最早空闲的机器;②当工件分配到可用机器的时候，选取可以最早完工的机器;③当工件分配到该阶段所有机器时(可用或不可用)，选取可以最早完工的机器。

为了描述该方法，对如下的符号进行了定义:

i为工件编号，i=1，2，3，…，n;j为阶段编号，j=1，2，3，…，J;b 为瓶颈阶段编号，b∈［1，2，3，…，J］;s为在阶段 j机器的编号，s=1，2，3，…，mj;mj为阶段j中非相关平行机台的数目为工件i在j阶段的平均处理时间;Pibs为在瓶颈阶段b工件i在机器s上的处理时间;Rj为阶段j的工作负荷;CiJ为工件i在最后阶段J的完成时间;为工件i在瓶颈阶段b之前的总的处理时间;为工件i在瓶颈阶段b之后的总的处理时间。

1.2 问题描述

笔者对需要解决的问题作如下的假设:包含J个阶段，其中又包含一个瓶颈阶段b，在阶段j有mj个非相关平行机台，非相关平行机台mj的数量可能不同;有n个工件需要被处理，每个工件执行相同的加工路径;所有的工件在0时刻都是可用的;每个工件在每个阶段每台机器上的处理时间都是预先知道的，一台机器在一个时刻只能处理一个工件，在两个阶段之间有无限缓冲期，这里不考虑停机或装设成本;工作的负荷作为瓶颈的指示器，阶段j的工作负荷通过计算该阶段所有操作的处理时间总和除以机器的数量得到，用公式，拥有最大Rj值的阶段被定义为瓶颈阶段。

1.3 算法描述

GAREY等人证明了具有3台机器的最小化完工时间流程排序问题是一个NP困难问题，HOOGEVEEN等人证明了具有两阶段的最小化完工时间的问题是NP困难问题，因此，笔者提出的问题一定也是NP困难问题。

笔者基于瓶颈的启发式算法主要思想是瓶颈阶段的计划可能会影响非瓶颈阶段的计划，该启发式算法包含3步:①确认瓶颈阶段;②采用基于瓶颈的方法产生最初的排序次序;③在最初的排序基础上采用基于瓶颈的插入方法产生最后的排序。

算法中的最初计划的排序方法如下:

(1)把集合A置为空集。

(2)把系统分为瓶颈前系统，瓶颈系统以及瓶颈后系统，计算瓶颈前系统和瓶颈后系统的时间和时间。

(6)在集合A中获得最初的工件序列。

(7)停止程序。

算法中在最初排序的基础上采用基于瓶颈的插入方法产生最终的排序方法如下:

(1)选择最初序列中的第一个工件，让它成为当前序列。

(2)在最初序列中选择下一个工件，把它插入到当前序列的前、后位置和每两个连续工件的中间位置。

(3)计算在第(2)步中产生的部分序列的完工时间，然后在瓶颈阶段调整工件的进入序列，同时在第一阶段也要同时调整其序列。

(4)选择最小的完工时间的部分序列，让该部分序列成为当前序列。

(5)当目前部分计划包含所有工件时，停止程序，否则转到第(2)步。

2 实例验证

笔者以某纺织企业为例，表1中给出了原棉在经过染色、纺纱和织布3个阶段的处理时间。

表1 原棉的单位处理时间

利用基于瓶颈的启发式算法进行计算。

(1)计算表1中每个阶段的工作负荷，它们是 R1=52.55，R2=120.00，R3=66.25，经过计算确定阶段2是其瓶颈。

(2)采用基于瓶颈的方法产生最初的排序次序。最后产生的最初最优序列为1-3-2。

(3)在最初的排序基础上采用基于瓶颈的插入方法产生最后的排序。

计算部分序列3-1的完工时间，如表2所示，其完工时间的值为170。

表2 序列3-1的完工时间值

计算部分序列1-3的完工时间，如表3所示，其完工时间的值为200。

表3 序列1-3的完工时间值

确定其最优部分排列为3-1。

计算部分序列2-3-1的完工时间，如表4所示，其完工时间的值为235。

表4 序列2-3-1的完工时间值

计算部分序列3-2-1的完工时间，如表5所示，其完工时间的值为250。

表5 序列3-2-1的完工时间值

计算部分序列3-1-2的完工时间，如表6所示，其完工时间的值为220。

表6 序列3-1-2的完工时间值

最后得到最优序列为3-1-2。表2～表6中的4个字段的含义分别为:第1个字段为原棉编号，第2个字段为工序编号，第3个字段为原棉加工开始时间，第4个字段为原棉加工结束时间。

3 结论

笔者以纺织企业为例采用基于瓶颈的启发式算法较好地解决了基于瓶颈的非相关平行机台的混合流程型企业的排序问题，同时该方法也可以较好地推广到基于瓶颈的工件生产排序问题中。关于非相关平行机台的排序问题研究目前还鲜见报道，对于该问题的研究基本局限于采用模拟退火算法、遗传算法等搜索算法，而搜索算法的效率问题却成为了实际应用的瓶颈。笔者提出的算法能大大提高排序效率，测试采用C++编制的程序，在6.88 s内可以解决100个工件的排序问题，该算法有较好的应用前景。

［1］WITTROCK R J.An adaptable scheduling algorithm for flexible flow lines［J］.Operations Research，1988(36):445-453.

［2］GUINET A G P，SOLOMON M.Scheduling hybrid flow shops to minimize maximum tardiness or maximum completion time［J］.International Journal of Production Research，1996(34):1643-1654.

［3］LEON V J，RAMAMOORTHY B.An adaptable problem space-based search method for flexible flow line scheduling［J］.IIE Transactions，1997(29):115 –125.

［4］AGNETIS A，PACIFICI A，ROSSI F，et al.Scheduling of flexible flow shop in an automobile assembly plant［J］.European Journal of Operational Research，1997，97(2):348-362.

［5］JIN Z H，OHNO K，ITO T，et al.Scheduling hybrid flow shops in printed circuit board assembly lines［J］.Production and Operations Management，2002(12):216-230.

［6］SAWIK T.An exact approach for batch scheduling in flexible flow lines with limited intermediate buffers［J］.Mathematical and Computer Modeling，2002(36):461-471.

［7］ALISANTOSO D，KHOO L P，JIANG P Y.An immune algorithm approach to the scheduling of a flexible PCB flow shop［J］.International Journal of Advanced Manufacturing Technology，2003(22):819-827.

［8］ADLER L，FRAIMAN N，KOBACKER E，et al.BPSS:a scheduling support system for the packaging industry［J］.Operations Research，1993(41):641 –648.

［9］PATERNINA-ARBOLEDA C D，MONTOYA-TORRES J R，ACERO-DOMINGUEZ M J，et al.Scheduling jobs on a k-stage flexible flow-shop［J］.Annals of Operations Research，2008(164):29-40.

［10］LINN R，ZHANG W.Hybrid flow shop scheduling:a survey［J］.Computer and Industrial Engineering，1999(37):57-61.