高端制造业批量处理问题的优化方案研究

问题背 研究现状及必要 带有不相容工作族的𝛃→𝛅|𝒘𝒋𝑪𝒋问 问题模 问题下 算法设 数值实 案例生 数值结果与分 总 带有不相容工作族及有限缓冲区限制条件的𝛃→𝛅|𝑪𝒋问 问题模 问题下 GSPT算 数值实 案例生 数值结果及分 总 结 参考文 问题背如半导体制造、火箭厂等。FlowShopJobShop排程。但在实际生产中，我们经常会遇到批处理机器，批1.1中，在半导体生产线上不同的1.1研究现状及必要作业研究的一个重要分支。为了问题描述的简化，下文我们以β→δ|Z代表此问题，其中β代表批处理机而δ代表单机。Z则代表了问题的目标。Ahmadietal.[1]研究了βδ问题并就工作周期（𝐶𝑚𝑎𝑥）FullBatch-dealingSPT算法。同时他还拓展了β→δ问题，为其加入了不相容Ahmadietal.工作的基础上，HoogeveenandVelde[2利用了位置完成时间的概念并以β→δ|𝐶𝑗为目标提出了一种时间复杂度为O(nlog𝑛)的算法并给出了其一个日下界。KimandKim[3]利用信息不变性原则为解决β→δ|∑𝐶𝑗提出了GA为基础的新的方案。Suetal.[4则考虑了第二阶段有限等待时间这一限制就β→δ|𝐶𝑚𝑎𝑥问题提出了一个启发式算法及混合线性整数规划模型。SuandChen[5]则就不等同工作尺寸限制条件下的β→δ|𝐶𝑚𝑎𝑥提出了一种启发式算法和一种分支定界算法。Yaoetal[6]考虑了动态工作到达及不相容工作族、有限等待时间限制条件下的β→δ|𝐶𝑚𝑎𝑥问题。他们都为我们解决这些问题提供了诸多GongandTang[7]Gongetal.[8]在考虑𝐶𝑚𝑎𝑥和总堵塞时间的目标下对β→留在批处理机中。他们提出了几种近似算法。Suetal.[9研究了有限缓冲区限制条件下的β→δ|𝐶𝑚𝑎𝑥问题并给出了一种思路以及一个分支定界程序以进行基准化分析。Fuetal.[10]就不相容工作族及有限缓冲区条件下的β→δ|𝐶了研究，其中𝐶从该问题的研究现状，我们得出β→δ|Z例如带有不相容工作族的β→δ|∑𝑤𝑗𝐶𝑗限制条件的βδ|𝐶𝑗问题，而且这些空白在现实生产中更普遍，更接近实际情Ahmadietal.[1]所述的，β→δ|𝐶𝑗问题是plete所研究的带有不相容工作族的β→δ|∑𝑤𝑗𝐶𝑗问题和带有不相容工作族及有限缓冲区限制条件的βδ|𝐶𝑗问题很显然也是plete问题。接下来我们在第三章讨论带有不相容工作族的βδ|𝑤𝑗𝐶𝑗问题，在第四章讨论带有不相容工作族及有限缓冲区限制条件的β→δ|∑𝐶𝑗问题带有不相容工作族的𝛃→𝛅|𝒘𝒋𝑪𝒋问 pat|∑𝑤𝑗𝐶𝑗问题的满批次性，其每一个工件族中的工件数量都是批量生产机器容量的整数所有的工件尺寸所有的批次在批处理机器上拥有相同的处理优先权在批量处理器与单机上都不被允两个处理器间的缓冲区是无限工件可以以任意顺序在单机上进行处NN=｛1,2, F=｛1,2,nkkBB=｛1,2,Fkkpii Mwii变量xilxil=1il，否则xil=yklykl=1lk的工件，否则ykl=uijuij=1当工件i在工件j之前在单机上进行处理，否则uij=0； 工件i的完成时间Uzsoy11]引理3.1：存在一个β→δ，pat|𝑤𝑗𝐶𝑗调度问题的最有解，除了每个工味着工件总数n∑knk=αbα代表满批次性下的批次数量。因此，基于以BDMI：min∑i∈N s.t.∑𝑙∈Bxil= ∀i∈ ∑i∈Nxil= ∀l∈ ∑𝑘∈Fykl= ∀l∈B, =nk ∀𝑘∈F,𝑙∈B xil≤ ∀𝑖∈F,l∈B,uij+uji= ∀i,j∈N,i<j,Ci−pi≥Cj− ∀i,j∈N,i≠j,Ci−pi≥t∑𝑙∈Blxil ∀i∈N,uij∈{0,1},∀i,j∈N,i≠j,（10）∈{0,1},∀𝑘∈F,l∈B,xil∈ ∀i∈N,l∈B,约束（6）lkk的工件才可开始处理。约束（9）i所在的批次在批量处理器上完成了处（10（11）范围。在此，我们可以设置B=｛1,2,…,α|｝以及M=αt+∑i∈NpiBDMI等式定制满批次数据来进行计算实验。对应的计算结果将在3.4部分 引理3.2：当𝑎1≤⋯≤𝑎n与𝑏1≤⋯≤𝑏n𝑎n𝑏1+⋯+𝑎1𝑏n≤𝑎σ(1)𝑏1+⋯+𝑎σ(n)𝑏n≤𝑎1𝑏1+⋯+其中𝑎σ(1),…,𝑎σ(n)为𝑎1,…,𝑎n即，单机的等待时间可以忽略。据此，我们在提法1中推导第一个下界LB1。推论3.1将权重w按降序排列，将处理时间按升序排列，则LB pat|∑𝑤𝐶的一个下界 j=1j(⌈b⌉t+j 𝑗证明：设（x∗,y∗,u∗,C∗）是问题的一个最优解。对于每个工件j,记其所需完成时间为C∗，令w∗和p∗分别为其权重和处理时间。显然，每个C∗包含三个部分： 批量处理器上的完成时间t∑l∈Bx∗在缓冲区的等待时间 0以及单机 间p∗。因此，为了使目标函数 w∗C∗最小化，我们需要以下不等式 j w∗C∗=

w∗(t x∗+△∗+j

n

≥ w∗(t j

≥ j(⌈⌉t+j)= 个问题就变为了释放时间全部为t的单机时间规划问题。这类问题可以通过WSPT法则，即Smith’srule,来取得最优解。推论3.2：将所有工件按pj/wj进行增序排列，∀j∈N,̂̂≤̂ ̂̂，则LB=̂(t∑ĵ)为β→δ1 2 i=1pat|∑𝑤𝑗𝐶𝑗的一个下证明：记（xyuC∗）是问题的一个最优解，对于每个工件j,记其所需完成时间为C∗，令w∗和p∗∑nw∗C∗ j

n∑

w∗C∗≥j

w∗(t+j

in≥

t+

nw∗∑

≥ ̂jt+ ̂j ̂i tLB1就会更精确。除此之GRWC-WSPT算Uzsoy[11]提出了一种用于求解一个批次处理机器上不兼容工件组的最小时间工序（GRWC）的贪心算法。批次处理器上的GRWC过程、单WSPT规则以及一些其他的有用信息组合起来并设计了的第一个启发式算法，其记作GRWC-WSPT。下表描述了其流程：GRWC-第五步：让单机处于待机状态，直到所有的批次都已释放，之后再按p/w的上界，记为UB。UB可被用于分析所提算法的情况。∑引理3.3：令UB=αt∑nj=1wj+ΓWSPT，则UB为 pat|∑𝑤𝑗𝐶𝑗的∑

̂

情况下，第i批工件中的工件的释放时间可以被视为𝑖𝑡+(𝛼−𝑖)=𝛼𝑡，该公式H0。对H0我们可以找到一个可行解，我们很容易确认其目标值为Obj(H0)=αt∑n wj+ΓWSPT=UB.证明完成。推论3.3：GRWC-WSPT是 pat|∑𝑤𝑗𝐶𝑗问题的α近似算法，其证明：考虑引理三证明中工序H0出现在算法的第五步，我们有Obj(GRWC-WSPT)≤UB，基于第四节LB1LB2，以及引理3给出的UB，不难验证LB1≥t∑n wj以及UB−LB2=αt∑n wj−∑n ̂jt。因此，以下不等

Obj(GRWC−WSPT)≤1+Obj(GRWC−WSPT)− ≤1αt

UB− LB1 ̂=1t

j=1wj

wj=1wj− ≤1

t = LP-WSPTLP-WPST的流程如下：第二步：在第k个工件组中，按c的增序排列工件第六步：重定义cj=cj/wj，重复步骤2-5，返回计划表π2及相依目标值Obj(π2)序在单机上进行处理。返回该规划π3极其函数值Obj(π3)。推论3.4：LP-WSPT是β→δ， 证明：考虑到引理3中H0被整合入算法的第七步，同推论3相似

Obj(LP−WSPT)≤1+Obj(LP−WSPT)−

≤1

UB− ≤的LP-relaxation问题。本节进行了一些计算试验来检验所算法的表现。所有的试验均在64位的Windows7系统上运行硬件配置为InCore3.3GHZ的CPU,RAM4.0GB。算法C++编写VS2010运行BDMI的数学公式求Cplex12.5进行（默认的求解时间上限为3600s）对于每个组合“n-m-b”，设置n=b⌈n⌉,j=1,…,m−1,和 =n−∑m−1n 对于每个工件i，其权重由1-2之间的均匀分布给出，处理时间𝑝𝑗和单机则由1-10的均匀分布给出。批次处理时间t被设置为n p。这样的设计可以有效 i=1G1：n={8,12,16,20},m={2,4},b=G2：n={100,200,300,400},m={2,4,10},b=G3：n={800,1000},m={4,10},b=

≥Gap1：GRWC-WSPT与BDMI结果的平均差Gap1与Gap2的计算方法如下Obj(H)−Obj(BDMI)Gap1(2)= 显然，Gap<0BDMI的表现更好，Gap1(2)>0CplexBDMI的平均最佳目标函数值。Time栏表示求解表中所述的一样的，Lp-relaxation更为精密，由此法可在个人电脑上在一小时内解12个工件的问题。当工件数目增加至20时，没有任何案例可以在一小时内求解，对于所有组合，Gap0的最大值是6.64%。3.1G1BDMI模型求解结3.2展示了两种算法的结果的对比以及G1CplexBDMI结果。每个组合的结10个案例的平均。值得注意的是对于每个例子，我们都计算LB1,LB2Lp-r中的最大值，而LB栏中的值则是10个值的平均值。显然，Gap1Gap2BDMI的解的质量高于我们所提的3.49%。另一方面，GRWC-WSPT1.1256，而LP-WSPT则是比其稍好（除了组合16-2-4。3.2G1表格3.3则给出了两种算法G1情形的情况结果以及相应的差值与比值。值。对n=812的组合来说（12-2-2，Gap1与Gap2的最小0，这6.77%。两个算法比值的最低值均小于1.1097，最大值均为1.1678，这意味着这两表3.3算例G1的最好和对比结表3.4给出了三个算法在G2组中的对。标记同表2相似，在此不做详述。如表中所示，Gap0的最大值为14.09%（组合400-2-10），这意味着Cplex给出的着我们算法相较于Cplex给出的BDMI解质量更高。就ratio方面而言，计算时间也稍长一些，但是相差不会超过362.66s.3.4G2表3.5给出了两种算法在G2组的情况分析。标记同表三相似，不做详述。两者在RATIO上的值均为1.1472.当n>200时，两者的最大值都小于1.0941.200-2-20的所有组合，LP-WSPT的平均比值都要较小。Gap1Gap2的表3.5算例G2的最好和对比结3.6GRWC-WSPT算法在G3组的解。角标含义与前类似。应当注只有GRWC-WSPT能够用于解决这类大规模问题。此外，我们还记算了LB1LB2中的最大值，并取其为每个算例的下界。如表6所示，每个算例的ratio均小于1.1034。尤其值得注意的是，对于800-10-50之外的所有组合，Max-R下的最大ratio均小于1.0726，这说明对于大规模问题该算法仍有着不错的表现。等同批次处理时间。其二则是考虑证明这个问题是否存在一个常数近算法。带有不相容工作族及有限缓冲区限制条件的𝛃→𝛅|𝑪𝒋问在此部分，我们首先给出带有不相容工作族及有限缓冲区限制条件的β→∑所有工作一开始都已做好了进入批处理器处理的准备每个族的工作数目都是批处理机容量的整数所有工作的尺寸相同每批工作的处理时间只取决于其内工作所属的族工作在批处理机上的处理时间比其在单机上的处理时间长批处理机及单机都不具有优先权缓冲区尺寸是批处理机容积的整数工作能够在单机上以任意顺序被处理N:N={1,2FF={1,2𝑛𝑘：kBB={1,2𝑞𝑘：k𝑎𝑘：k𝑀𝑖：一个大的正不失一般性的说，我们假设𝑞1≤𝑞2≤𝑞3≤⋯≤𝑞𝑚；Uzsoy[11]fullbatchproperty，其各工作的完工时间呈单调递增。引理4.1：存在βδ|𝐶𝑗的最优解使得除了最后一批的每一批工作都是满带有不相容工作族及有限缓冲区限制条件的β→δ|𝐶𝑗min∑𝑗∈𝑁𝑗s.t.∑𝑙∈𝐵𝑥𝑖𝑙=1∀i∈N（2∑𝑖∈𝑁𝑥𝑖𝑙=b，∀l∈B，∑𝑘∈𝐹𝑦𝑘𝑙=1，∀l∈ 𝑦=𝑛𝑘，∀k∈F，𝑙∈𝐵𝑘𝑙𝑥𝑖𝑙≤𝑦𝑘𝑙，∀i∈𝐹𝑘，l∈B，𝑟𝑙−𝑡𝑙≥0，∀l∈ 𝑟𝑙+1−𝑡𝑙+1≥𝑟𝑙，∀l∈B，𝑙≠𝑎,∑𝑗∈𝑁,𝑗≠𝑖𝑢𝑗𝑖+1≤𝑏(𝑙−ℎ)+𝑀1(1−𝑧𝑙𝑖)，∀𝑙∈𝐵,𝑙≥ℎ+1，𝑖∈∑𝑗∈𝑁,𝑗≠𝑖𝑢𝑗𝑖+1≥𝑏(𝑙−ℎ)+𝜖+[1−𝑏(𝑙−ℎ)−𝜖]𝑧𝑙𝑖，∀𝑙∈𝐵,𝑙≥ℎ+1，𝑖∈𝑁，（10）𝑟𝑙≥𝐶𝑖−p𝑖−𝑀2(1−𝑧𝑙𝑖)，∀𝑙∈𝐵,𝑙≥ℎ+1，𝑖∈𝑁，𝑡𝑙≥𝑞𝑘𝑦𝑘𝑙，∀k∈F，l∈ 𝑢𝑖𝑗+𝑢𝑗𝑖=1，∀𝑖，𝑗∈𝑁,𝑖< 𝐶𝑖−𝑝𝑖≥𝐶𝑗−𝑀2𝑢𝑖𝑗，∀𝑖，𝑗∈𝑁,𝑖< 𝐶𝑖−𝑝𝑖≥𝑟𝑙−𝑀3(1−𝑥𝑖𝑙)，∀𝑖∈𝑁,𝑙∈ 𝑢𝑖𝑗∈{0,1}，∀𝑖，𝑗∈𝑁,𝑖≠ 𝑦𝑘𝑙∈{0,1}，∀𝑘∈𝐹,𝑙∈ 𝑥𝑖𝑙∈{0,1}，∀𝑖∈𝑁,𝑙∈ 𝑍𝑙𝑖∈{0,1}，∀𝑖∈𝑁,𝑙∈ k族的工作被分配为𝑛𝑘个批次进行处理；限制方程（6）lk族的工作时，kl以设𝑀1=n-b(l-h)、𝜖=0.01；限制方程（11）保证了在某一批次工作释放时缓冲区至少存在一个单位的闲置空间，我们可以设𝑀2=∑𝑘∈𝐹𝑎𝑘𝑞𝑘+∑𝑖∈𝑁𝑝𝑖+ℎ𝑏𝑚𝑎𝑥𝑖∈𝑁𝑝𝑖；限制条件（12）定义了批处理所需时间；限被释放到缓冲区的工作，我们可以设𝑀3=∑𝑘∈𝐹𝑎𝑘𝑞𝑘+∑𝑖∈𝑁𝑝𝑖；限制条件（16）（17（18（19）在这一部分推导出带有不相容工作族及有限缓冲区限制条件的β→δ|∑𝐶𝑗问题的两个下界，这将有利于我们检验算法所得结果的质量。推论4.1：将各批次工作按批处理时间𝑡𝑙升序排列，使得𝑡1𝑡2𝑡3

(1+𝐿𝐵1=∑[𝑎𝑘(𝑎+1−∑𝑎𝑖) ]𝑏𝑞𝑘+∑ 为带有不相容工作族及有限缓冲区限制条件的β→δ|𝐶𝑗证明：记𝐶∗j的最优化完工时间，𝑓𝑗（忽略堵塞时间）j处理机上的 工时间，𝑓∗和𝑝∗分别为工作j在批处理机上的完工时间和单机 间𝑓∗、批处理机上的堵塞时间和缓冲区的等待时间∆∗以及单机上的处理时间𝑝∗。 𝑗=1因此令𝑍∗= 𝐶∗为最优化的总完工时间，我们𝑗=1𝑍∗= 𝑍∗= (𝑓∗+∆∗+𝑝∗)≥ (𝑓∗+𝑝∗)= (𝑎−𝑙𝑗=1 𝑗=1 𝑗=1 1)𝑏𝑡∗+ 𝑗=1 ≥ (𝑎−𝑙+

+

(1+=∑[𝑎𝑘(𝑎+1−∑𝑎𝑖) ]𝑏𝑞𝑘+∑

下面我们从另一个角度来推导另一个下界𝐿𝐵2。考虑所有工作自批处理机SPT规则得到最优解。由此我们有下面题。推论4.2：将各批次工作按独立处理时间𝑝𝑗升序排列，使得2≤⋯≤𝐿𝐵2= [𝑞1+(𝑛−𝑗+1)𝑗为带有不相容工作族及有限缓冲区限制条件的β→δ|𝐶𝑗 ∑ 𝐶∗≥∑

+(𝑛−𝑗+1)𝑝∗]≥

+(𝑛−𝑗+1)𝑝𝑗 𝐿𝐵1和𝐿𝐵2计算的时间复杂度均接近𝑂(𝑛log𝑛)，均能很快地通过计算得到。因此我们可以利用这两个下界来评测我们所算法在处理问题时的表现。GSPT4.1fullbatchpolicySPT规则。得到初步编对各工作族𝐹𝑘按照𝑞𝑘升序排列在各族内部对工作按照𝑝𝑗升序排列，𝑗∈贪婪地（即每一批在可能的情况下都组满构建工作批次，顺序按照计算各批次工作在单机上所需的总处理时间令𝑆𝑙=𝑡𝑙，批处理机按照𝑆𝑙令𝑆𝑙𝑃𝑙𝑡𝑙5）6）得到另一种可能方案𝜋2，计算对应目标值Obj(𝜋2)；记此可能方案为𝜋3，计算对应目标值Obj(𝜋3)；确定参数𝑖∗=𝑎𝑟𝑔𝑚𝑖𝑛𝑖𝑂𝑏𝑗(𝜋𝑖)，i=1，2，3；给出方案𝜋∗该算法的时间复杂度为𝑂(𝑛log𝑛)。接下来我们对此算法进行分析δ|∑𝐶𝑗问题的b-近算法，其中b代表批处理机的容积。证明：令Γ= [𝑎(𝑎+1−∑𝑘−1𝑎)−(1+𝑎𝑘)𝑎𝑘]𝑏𝑞。令每一批次工作 成时间为𝐶𝑗𝑓𝑗𝑝𝑗GSPT (1+ 𝑈𝐵= 𝐶𝑗= [𝑛𝑘(𝑛+1− 𝑛𝑖) ]𝑞𝑘+

=Γ2+ 然后以Γ1乘以b，我们 (𝑏+𝑏Γ1= [𝑎𝑘𝑏(𝑎𝑏+𝑏− 𝑎𝑖𝑏) ]

= [𝑛𝑘(𝑛+𝑏−

(𝑏+𝑛𝑖) ] 𝑛𝑘(𝑏− 𝑛𝑘(𝑏−𝑏Γ1−Γ2=

[𝑛𝑘(𝑏−1)

]𝑞𝑘=2

]𝑞𝑘≥由第四部分所给出的下界𝐿𝐵1的值我们可以得到下列不等

Γ2+

≤ = ≤

≤Γ1+Γ1+

Γ1Γ1+

由此我们证明了我们的结论：GSPT为b-近算法 64win73.3GHzCoreCPU及4.0GB的运行内存。算法以C++语言进行编程并在VisualStudio2010中运行。第的数量；b代表批处理机的容积；h代表缓冲区的容积。针对每个组合我们跑了10个样例，样例的生成参考了[1]和[12]。

=𝑏[𝑛]，j=1,2,…,m-𝑛𝑚=𝑛−∑𝑚−1𝑝𝑖∈𝑈(1,10)，𝑝𝑖为整数；U(a,b)为从[a,b]批处理机处理时间为𝑈(𝑏 𝑝−10,𝑏 𝑝+10)且为整数，这使得对 𝑖=1 𝑖=1近。同时如果有样例不符合假设5，那么这个样例将会被删除。𝐺3n={400,600,800,1000},m={5,10},b={10,20},h={2,3}

>12116个时，得结果和最优值的对比如表4.1所示。MIP代表第三部分中的方程组。差距𝑂𝑏𝑗(𝐺𝑆𝑃𝑇)−

×4.1GSPT算 目标值时 目标 时Obj：由GSPT给出的目标值；；Avg-R：GSPTLB间的平均比值；Max-R：GSPTLB对于每个组合，LB、Obj和Time均为10个样例给出数据的平均值，同时我们对每一个组合的每一个样例计GSPTLB间的比值，Avg-R为每个组10个0.05Avg-R出现在(100,4,5,1)1.197；最大的Max-R出现在(200,4,5,1)的组合中，最大比值为1.295；这些结果说明GSPT在4.2GSPT4.3展示了𝐺3GSPT算法处理的结果。每个问题的处理时间都少于0.6秒，对于大部分样例其Avg-R值均小于11，最大的Avg-R出现在(1000,5,10,2)的组合中，最大比值为1.127；Max-R的值同样十分小，最大的Max-R出现在4.3GSPT们还给出了一种b-近算法并给出了其两个下界以对其运行结果进行。通过数值运算的结果我们相信此算法在大规模工作的处理上具有显著的优越性与结些空白，本文具体讨论了带有不相容工作族的β→δ|𝑤𝑗𝐶𝑗作族及有限缓冲区限制条件的βδ|𝐶𝑗参考文J.H.Ahmadi,R.H.Ahmadi,S.Dasu,andC.S.Tang,“Batchingandschedulingjobsonbatchanddiscreteprocessors,”Operationsresearch,vol.40,no.4,pp.750–763,1992.H.HoogeveenandS.vandeVelde,“Schedulingbypositionalcompletiontimes:ysisofatwo-stageflowshopproblemwithabatchingmachine,”MathematicalProgramming,vol.82,no.1-2,pp.273–289,1998.B.KimandS.Kim,“Applicationofgeneticalgorithmsforschedulingbatch-discreteproductionsystem,”ProductionPlanning&Control,vol.13,no.2,pp.155–165,2002.L.-H.Su,“Ahybridtwo-stageflowshopwithlimitedwaitingtimeconstraints,”Computers&IndustrialEngineering,vol.44,no.3,pp.409–424,2003.F.S.Yao,M.Zhao,andH.Zhang,“Two-stagehybridflowshopschedulingwithdynamicjobarrivals,”Computers&OperationsResearch,vol.39,no.7,pp.1701–1712,2012.H.GongandL.