基于订单完成的柔性流水作业排序

胡代平，吴瑞明，徐博艺

（上海交通大学 安泰经济与管理学院，上海 200052）

柔性流水作业的排序考虑所有工件的各自的完成情况，以完工时间或误工成本[1，3]最小为优化目标来进行的作业排序，学者们已提出了启发式算法[2-3]、人工智能搜索算法等[4-5]用于解决这类排序问题。在实际应用中，很多企业是按订单完成进行加工生产的，需要根据客户订单的情况来合理安排生产。客户的一个订单包括1个或多个工件，订单中所有工件全部完成订单生产才完成，本文基于订单完成来研究柔性流水作业的排序问题，考虑工件的订单属性，以订单为单位来计算各个订单的加权单误工成本，并使总的加权误工成本最小作为优化目标来进行柔性流水作业的排序。

1 柔性流水作业问题

通常的柔性流水作业问题：J个工件，按流水顺序需要经过S道工序，每道工序又具有多个平行处理器，第p道工序总的有Mp个处理器。并且满足如下假定：

（1）1个工件在每道工序只能至多被1台处理器处理。

（2）每台处理器1次只能至多处理1个工件，1个工件1次只能至多在1个处理器被处理。

（3）工件在处理器上处理无间断，工件处理任务不能被分割。

如何安排所有工件在这些处理器上进行处理的问题就是柔性流水作业排序问题，其目标函数可以是最小化完工时间或误工成本等。这类排序问题直接求解是非常困难的，所以学者们提出了多种方法来进行求解[1-5]，找出局部最优或近似全局最优的排序方案。还有学者将一些限制条件考虑在内，例如带有序列依赖[6-7]以及带有成组约束[7-10]的排序问题，其中带有成组约束排序问题是将分组作为排序的约束条件，一组内所有工件的某道工序处理都完成后，才能进行下一工序的处理，黎展滔等[9]和何龙敏等[10]研究了带组约束的两阶段柔性流水作业排序问题。基于这些研究，还不能解决按订单完成来进行作业的排序，通常柔性流水作业排序方法无订单信息，而利用成组约束求解方法也不能将1个订单作为1组来进行作业排序，因为按订单生产不能要求订单的所有工件某个工序都完成后才进入下一个工序。本文在前人成果基础上，研究了基于订单完成的多阶段柔性流水作业排序问题。

2 基于订单完成的柔性流水作业模型

2.1 问题描述

O表示订单，J、S、M分别表示工件、工序和处理机。共有O个订单，Oi表示第i个订单，第i个订单有Ji个工件；Jij表示i个订单的第j个工件，i=1，2，…，O；j=1，2，…，Ji，Ji为第i个订单工件总数。共有S道工序，第p道工序有Mp台处理器。Mpq表示第p道工序的第q台处理机，p=1，2，…，S；q=1，2，…，Mp。同一个订单中的所有工件同时到达系统，订单到达时间为Ri，订单合同交货时间为Di。订单中的工件不是所有的工序都一定需要，可以只需要1个或几个工序。本文还假定基于订单完成的柔性流水作业问题满足以下条件：

（1）1个工件只能同时至多被1台处理器。

（2）1台处理器只能同时至多处理1个工件。

（3）所有工件的操作均按照从头至尾的流水顺序依次被处理。

（4）所有工件均不能被分割中断。

2.2 符号说明与决策变量

模型中符号说明：

Tijpq—第i个订单的第j个工件在第p道工序的第q台处理器上进行处理时所需要的时间长度，即处理时间。

Kijp—第i个订单的第j个工件是否需要第p道工序处理。赋值为1表示需要处理，赋值为0表示不需要处理。当Kijp=0时，对于q=1，2，…，Mp，Tijpq均为0。

Cijp—第i个订单的第j个工件经过第p道工序处理的完成时间。

Cij—第i个订单的第j个工件完成时间。

Ci—第i个订单的完成时间。

Fpq—第p道工序第q台处理器最早可以开始处理的时间，即最早可用时间。

Wi—第i个订单的优先级权重，可以是大于0的正整数，由决策者根据其实际应用情况给定，例如不同客户的重要程度、订单价值大小等。

模型的决策变量：

xijpq—第i个订单的第j个工件在第p道工序的第q台处理器上的开始时间。

Kijpq—第i个订单的第j个工件第p道工序，是否在第q台处理器进行处理，为0-1决策变量，0表示不处理，1表示处理。

yijpq—第i个订单的第j个工件第p道工序在第q台处理器的排序，yijpq=1，2，…，为不小于0的整数。0表示工件不在该机器上处理，1表示工件在该处理器上的作业队列中排第1，2表示排第2，以此类推。

Zi—第i个订单延误的时间长度，即误工时间。

Ei—第i个订单提前完工的时间长度。

2.3 模型表示

（1）目标函数。当订单完成时间大于合同交货时间时，才有误工成本，否则无误工成本，只有当Ci≥Di时，目标函数可以写为）

通过利用订单误工时间Zi（Zi≥0）将目标函数转换为线性函数：

（2）约束条件。订单的完成时间与误工时间、提前完工时间和合同交货时间的关系：

对于第i个订单的第j个工件，是否在第p道工序进行处理Kijp的值，与表示该工件是否在第p道工序的第q台处理器上处理的变量Kijpq满足如下关系：

对于第i个订单的第j个工件在第p道工序第q台处理器上的开始时间不小于该处理器最早可用时间，且不小于订单i的到达时间。

1个工件在第p道工序的开始时间不小于第p-1道工序的完成时间。

1个工件在第p道工序的完成时间，如果不需要本工序的处理，则为上一道工序完工时间Cij（p-1），如果需要本道工序的处理，假定在第q台处理器上进行处理，则本当工序的完成时间为开始时间加上处理时间。通用的约束可以写为如下形式：

第i个订单的完成需要该订单的所有工件都完成各道工序的处理，其完工时间Ci为该订单所有工件各自最后一道工序（不一定是系统的最后一道的S道工序，因为不是每个工件都需要所有工序）完工时间中的最大值，由于每个工件各自最后一道工序完工时间大于其前面工序的完工时间，故订单完成时间可以表示为

对于排在第p道工序的第q台处理器作业队列中的所有工件，必定都是互不相同的工件，一个工件Jij的在该作业队列的开始时间，不小于队列中前一个要处理工件Jlm的完成时间（不一定是相等关系，有可能Jij所在的订单还未到达或其前一工序还未完成）。

第i个订单的第j个工件第p道工序，是否在第q台处理器进行处理的决策变量kijpq，与第i个订单的第j个工件在第p道工序在第q台处理器作业队列的排序决策变量yijpq之间的约束关系：

式中，N为足够大的正整数。

模型中所有决策变量、中间变量以及表示符号都不小于0。

3 基于订单完成的柔性流水作业排序算法

在算法描述中，还用到以下符号：

Cfij—不考虑其他工件时，第i个订单第j个工件可能的最早完成时间。

Zfij—不考虑其他工件时，第i个订单第j个工件可能的最小误工时间长度，Zfij=Cfij-Di，可以小于0。

Qi—第i个订单排序指标

基于订单完成的柔性流水作业排序问题比较复杂，本文提出的排序算法流程图如图1所示。

具体算法如下：

（1）数据初始化。输入订单数量O，每个订单包含的工件数量，其中，第i个订单包括的工件数量Ji；总的工序道数S，每道工序处理机台数，第p道工序有处理机Mp台。第i个订单第j个工件需要哪些道工序，确定出Kijp的值，需要p道工序处理则Kijp=1；否则，Kijp=0此时对应Kijpq=0；第i个订单第j个工件在第p道工序的第q台处理器上处理所需时间Tijpq；第p道工序的第q台处理器最早可用时间Fpq；订单优先因子Wi，订单到达时间Ri，订单交货时间Di。

图1 基于订单完成柔性流水作业排序算法流程图

（2）订单排序。根据订单的权重、到达时间和交货时间计算各个订单排队指标Qi，按Qi值的大小按升序方式将所有订单进行排序。

（3）订单内部工件排序。对于一个订单的各个工件，根据当前处理器运行状况，不考虑其他工件，按步骤（5）的最早最快加工方式试排入系统，计算其可能的最早最快加工完成时间Cfij，然后计算该工件可能的最小误工时间Zfij。在得到订单内各个工件的Zfij后，根据Zfij的值按递减顺序将工件排序。对所有订单，都按此方法完成其各自所包括的工件的排序。

（4）作业排序。根据步骤（2）、（3）订单和订单内部工件排序情况，从第1个订单中取出第1个工件，按工序顺序和步骤（5）、（6）的最早最快加工方式，将工件排入各个工序相应的处理器作业队列中。再取出第1个订单的第2个工件按此方法排入各个工序的作业队列中，直到第1个订单的工件全部完成，再进行第2个订单工件作业排序，直到所有订单的所有工件全部被排入处理器的作业队列。

（5）最早最快加工排序方式。1个工件的第p道工序有多台处理器可选时，对于第q台处理器，按式（5）～（7）及式（10）确定本工件最早开始时间及最早完成时间，选择排入具有最小完成时间的处理器队列。

计算工件开始时间、完成时间和选择处理器队列时会遇到3种情况：①队列无工件，直接排入；②队列有工件，但某个工件开始时间比较晚，其前有空闲时间可以完成该工件的处理（开始空闲时间点不大于该工件的开始时间，空闲时间段结束时间不小于该工件的完成时间），则将该工件排入空闲时间内完成；③队列有工件，队列中最后一个工件完成前不存在可以完成本工件处理的空闲时间，则把该工件排在队列的最后面。

（6）同订单处理器队列优化。新排入处理器队列的工件，满足步骤（5）中③的情况，而且队列最后的1个或多个工件与该工件属于同一订单，则需要进行同订单处理队列优化。将该订单插入同订单的各个工件前面的位置。在插入某一位置后，并按步骤（5）将该工件的余下工序以及被影响的工件的本工序和余下工序都重新排好，计算该工件和所有被影响的工件的完成时间Cij和误工时间Zij，并计算它们完成时间总和与误工时间总和。比较该工件在该处理器队列排在最后以及插入在不同位置时所涉及的工件误工时间总和与完成时间总和，选取误工时间总和最小的位置，如果误工时间总和为0，则选取完成时间总和最小的位置，在选取的位置排定该工件，同时确定该工件余下工序的排序位置及被影响的其他工件在本工序及余下工序的排序位置。

4 应用实例

在本实例中，作业处理包括3道工序，第1道工序有3台处理器，第2道工序有2台处理器，第3道工序有3台处理器。同一道工序中的多台处理器的性能也有所不同，其处理速度都是前者大于后者。

共有3个订单，第1个订单有3个工件，第2个订单有2个工件，第3个订单有3个工件。订单到达时间、交货时间以及权重系数如表1所示。

表1 订单信息

处理器最早开始时间如表2所示。

表2 处理器最早开始时间

订单中各个工件在不同处理器上的处理时间如表3所示。

表3 工件的处理时间

计算各个订单的排序指标Qi，再计算每个订单内所有工件的Cfij和Zfij，计算结果如表4所示。

表4 可能的最早完成时间、最小误工时间及订单排序指标

订单及其所包括的工件排序结果为：

按算法进行作业排序，确定出yijpq的值，最终作业排序结果如表5所示。

需要说明是：

（1）在工件J22排入M31（J13，J21）作业队列时，排在J13和J21中间的空闲时间，J13的完成时间C1331=8，而J21的开始时间x2131=11，J22的上一工序的完成时间C2211=6，因此将J22排入M31作业队列的空闲时间（8～11）内，开始时间x2231=8，完成时间C2231=x2231+T2231=9，J21的完成时间C2131=13保持不变。

表5 作业排序结果

（2）在进行工件J31的第2道工序作业排序时，可以排入M22（J12）作业队列，形成M22（J12，J31），也可以排入M21（J11，J21，J32）作业队列再进行同订单处理器作业队列排序优化，优化时J31插入到J32前面，得到作业队列M21（J11，J21，J31），J32在第2道工序的处理被重新调整而排入M22（J12，J32），J32的第3道工序仍排在M31作业队列最后不变，这样得到的J31、J32的误工时间总和为1，比J31排入M22，J32排入M21的误工时间总和2要小1个单位。因此，最终选取J31排入M21（J11，J21，J31），J32排入M22（J12，J32）。

经过作业排序，得到订单实际完成时间Ci、误工时间Zi及加权误工成本Wi Zi的值，如表6所示。3个订单中O1、O2都能按合同如期交货，O3完成时间为18，误工时间为1，加权误工成本为2。

表6 订单完成实际、误工时间即加权误工成本

5 结语

普通柔性流水作业排序中只考虑各自工件的完成情况，没有考虑工件之间的相互关系。很多生产企业实际上采用按订单进行加工生产，因此，按订单完成进行柔性流水作业排序研究更具有实际意义。本文在前人成果的基础上，研究基于订单完成的柔性流水作业排序的算法，以订单为单位，使得订单的加权误工成本最小来优化排序，并通过实例应用验证该了算法的有效性。