基于訂單完成的柔性流水作業(yè)排序

胡代平，吳瑞明，徐博藝

（上海交通大學(xué) 安泰經(jīng)濟(jì)與管理學(xué)院，上海 200052）

柔性流水作業(yè)的排序考慮所有工件的各自的完成情況，以完工時(shí)間或誤工成本[1，3]最小為優(yōu)化目標(biāo)來(lái)進(jìn)行的作業(yè)排序，學(xué)者們已提出了啟發(fā)式算法[2-3]、人工智能搜索算法等[4-5]用于解決這類排序問(wèn)題。在實(shí)際應(yīng)用中，很多企業(yè)是按訂單完成進(jìn)行加工生產(chǎn)的，需要根據(jù)客戶訂單的情況來(lái)合理安排生產(chǎn)。客戶的一個(gè)訂單包括1個(gè)或多個(gè)工件，訂單中所有工件全部完成訂單生產(chǎn)才完成，本文基于訂單完成來(lái)研究柔性流水作業(yè)的排序問(wèn)題，考慮工件的訂單屬性，以訂單為單位來(lái)計(jì)算各個(gè)訂單的加權(quán)單誤工成本，并使總的加權(quán)誤工成本最小作為優(yōu)化目標(biāo)來(lái)進(jìn)行柔性流水作業(yè)的排序。

1 柔性流水作業(yè)問(wèn)題

通常的柔性流水作業(yè)問(wèn)題：J個(gè)工件，按流水順序需要經(jīng)過(guò)S道工序，每道工序又具有多個(gè)平行處理器，第p道工序總的有Mp個(gè)處理器。并且滿足如下假定：

（1）1個(gè)工件在每道工序只能至多被1臺(tái)處理器處理。

（2）每臺(tái)處理器1次只能至多處理1個(gè)工件，1個(gè)工件1次只能至多在1個(gè)處理器被處理。

（3）工件在處理器上處理無(wú)間斷，工件處理任務(wù)不能被分割。

如何安排所有工件在這些處理器上進(jìn)行處理的問(wèn)題就是柔性流水作業(yè)排序問(wèn)題，其目標(biāo)函數(shù)可以是最小化完工時(shí)間或誤工成本等。這類排序問(wèn)題直接求解是非常困難的，所以學(xué)者們提出了多種方法來(lái)進(jìn)行求解[1-5]，找出局部最優(yōu)或近似全局最優(yōu)的排序方案。還有學(xué)者將一些限制條件考慮在內(nèi)，例如帶有序列依賴[6-7]以及帶有成組約束[7-10]的排序問(wèn)題，其中帶有成組約束排序問(wèn)題是將分組作為排序的約束條件，一組內(nèi)所有工件的某道工序處理都完成后，才能進(jìn)行下一工序的處理，黎展滔等[9]和何龍敏等[10]研究了帶組約束的兩階段柔性流水作業(yè)排序問(wèn)題。基于這些研究，還不能解決按訂單完成來(lái)進(jìn)行作業(yè)的排序，通常柔性流水作業(yè)排序方法無(wú)訂單信息，而利用成組約束求解方法也不能將1個(gè)訂單作為1組來(lái)進(jìn)行作業(yè)排序，因?yàn)榘从唵紊a(chǎn)不能要求訂單的所有工件某個(gè)工序都完成后才進(jìn)入下一個(gè)工序。本文在前人成果基礎(chǔ)上，研究了基于訂單完成的多階段柔性流水作業(yè)排序問(wèn)題。

2 基于訂單完成的柔性流水作業(yè)模型

2.1 問(wèn)題描述

O表示訂單，J、S、M分別表示工件、工序和處理機(jī)。共有O個(gè)訂單，Oi表示第i個(gè)訂單，第i個(gè)訂單有Ji個(gè)工件；Jij表示i個(gè)訂單的第j個(gè)工件，i=1，2，…，O；j=1，2，…，Ji，Ji為第i個(gè)訂單工件總數(shù)。共有S道工序，第p道工序有Mp臺(tái)處理器。Mpq表示第p道工序的第q臺(tái)處理機(jī)，p=1，2，…，S；q=1，2，…，Mp。同一個(gè)訂單中的所有工件同時(shí)到達(dá)系統(tǒng)，訂單到達(dá)時(shí)間為Ri，訂單合同交貨時(shí)間為Di。訂單中的工件不是所有的工序都一定需要，可以只需要1個(gè)或幾個(gè)工序。本文還假定基于訂單完成的柔性流水作業(yè)問(wèn)題滿足以下條件：

（1）1個(gè)工件只能同時(shí)至多被1臺(tái)處理器。

（2）1臺(tái)處理器只能同時(shí)至多處理1個(gè)工件。

（3）所有工件的操作均按照從頭至尾的流水順序依次被處理。

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

2.2 符號(hào)說(shuō)明與決策變量

模型中符號(hào)說(shuō)明：

Tijpq—第i個(gè)訂單的第j個(gè)工件在第p道工序的第q臺(tái)處理器上進(jìn)行處理時(shí)所需要的時(shí)間長(zhǎng)度，即處理時(shí)間。

Kijp—第i個(gè)訂單的第j個(gè)工件是否需要第p道工序處理。賦值為1表示需要處理，賦值為0表示不需要處理。當(dāng)Kijp=0時(shí)，對(duì)于q=1，2，…，Mp，Tijpq均為0。

Cijp—第i個(gè)訂單的第j個(gè)工件經(jīng)過(guò)第p道工序處理的完成時(shí)間。

Cij—第i個(gè)訂單的第j個(gè)工件完成時(shí)間。

Ci—第i個(gè)訂單的完成時(shí)間。

Fpq—第p道工序第q臺(tái)處理器最早可以開始處理的時(shí)間，即最早可用時(shí)間。

Wi—第i個(gè)訂單的優(yōu)先級(jí)權(quán)重，可以是大于0的正整數(shù)，由決策者根據(jù)其實(shí)際應(yīng)用情況給定，例如不同客戶的重要程度、訂單價(jià)值大小等。

模型的決策變量：

xijpq—第i個(gè)訂單的第j個(gè)工件在第p道工序的第q臺(tái)處理器上的開始時(shí)間。

Kijpq—第i個(gè)訂單的第j個(gè)工件第p道工序，是否在第q臺(tái)處理器進(jìn)行處理，為0-1決策變量，0表示不處理，1表示處理。

yijpq—第i個(gè)訂單的第j個(gè)工件第p道工序在第q臺(tái)處理器的排序，yijpq=1，2，…，為不小于0的整數(shù)。0表示工件不在該機(jī)器上處理，1表示工件在該處理器上的作業(yè)隊(duì)列中排第1，2表示排第2，以此類推。

Zi—第i個(gè)訂單延誤的時(shí)間長(zhǎng)度，即誤工時(shí)間。

Ei—第i個(gè)訂單提前完工的時(shí)間長(zhǎng)度。

2.3 模型表示

（1）目標(biāo)函數(shù)。當(dāng)訂單完成時(shí)間大于合同交貨時(shí)間時(shí)，才有誤工成本，否則無(wú)誤工成本，只有當(dāng)Ci≥Di時(shí)，目標(biāo)函數(shù)可以寫為）

通過(guò)利用訂單誤工時(shí)間Zi（Zi≥0）將目標(biāo)函數(shù)轉(zhuǎn)換為線性函數(shù)：

（2）約束條件。訂單的完成時(shí)間與誤工時(shí)間、提前完工時(shí)間和合同交貨時(shí)間的關(guān)系：

對(duì)于第i個(gè)訂單的第j個(gè)工件，是否在第p道工序進(jìn)行處理Kijp的值，與表示該工件是否在第p道工序的第q臺(tái)處理器上處理的變量Kijpq滿足如下關(guān)系：

對(duì)于第i個(gè)訂單的第j個(gè)工件在第p道工序第q臺(tái)處理器上的開始時(shí)間不小于該處理器最早可用時(shí)間，且不小于訂單i的到達(dá)時(shí)間。

1個(gè)工件在第p道工序的開始時(shí)間不小于第p-1道工序的完成時(shí)間。

1個(gè)工件在第p道工序的完成時(shí)間，如果不需要本工序的處理，則為上一道工序完工時(shí)間Cij（p-1），如果需要本道工序的處理，假定在第q臺(tái)處理器上進(jìn)行處理，則本當(dāng)工序的完成時(shí)間為開始時(shí)間加上處理時(shí)間。通用的約束可以寫為如下形式：

第i個(gè)訂單的完成需要該訂單的所有工件都完成各道工序的處理，其完工時(shí)間Ci為該訂單所有工件各自最后一道工序（不一定是系統(tǒng)的最后一道的S道工序，因?yàn)椴皇敲總€(gè)工件都需要所有工序）完工時(shí)間中的最大值，由于每個(gè)工件各自最后一道工序完工時(shí)間大于其前面工序的完工時(shí)間，故訂單完成時(shí)間可以表示為

對(duì)于排在第p道工序的第q臺(tái)處理器作業(yè)隊(duì)列中的所有工件，必定都是互不相同的工件，一個(gè)工件Jij的在該作業(yè)隊(duì)列的開始時(shí)間，不小于隊(duì)列中前一個(gè)要處理工件Jlm的完成時(shí)間（不一定是相等關(guān)系，有可能Jij所在的訂單還未到達(dá)或其前一工序還未完成）。

第i個(gè)訂單的第j個(gè)工件第p道工序，是否在第q臺(tái)處理器進(jìn)行處理的決策變量kijpq，與第i個(gè)訂單的第j個(gè)工件在第p道工序在第q臺(tái)處理器作業(yè)隊(duì)列的排序決策變量yijpq之間的約束關(guān)系：

式中，N為足夠大的正整數(shù)。

模型中所有決策變量、中間變量以及表示符號(hào)都不小于0。

3 基于訂單完成的柔性流水作業(yè)排序算法

在算法描述中，還用到以下符號(hào)：

Cfij—不考慮其他工件時(shí)，第i個(gè)訂單第j個(gè)工件可能的最早完成時(shí)間。

Zfij—不考慮其他工件時(shí)，第i個(gè)訂單第j個(gè)工件可能的最小誤工時(shí)間長(zhǎng)度，Zfij=Cfij-Di，可以小于0。

Qi—第i個(gè)訂單排序指標(biāo)

基于訂單完成的柔性流水作業(yè)排序問(wèn)題比較復(fù)雜，本文提出的排序算法流程圖如圖1所示。

具體算法如下：

（1）數(shù)據(jù)初始化。輸入訂單數(shù)量O，每個(gè)訂單包含的工件數(shù)量，其中，第i個(gè)訂單包括的工件數(shù)量Ji；總的工序道數(shù)S，每道工序處理機(jī)臺(tái)數(shù)，第p道工序有處理機(jī)Mp臺(tái)。第i個(gè)訂單第j個(gè)工件需要哪些道工序，確定出Kijp的值，需要p道工序處理則Kijp=1；否則，Kijp=0此時(shí)對(duì)應(yīng)Kijpq=0；第i個(gè)訂單第j個(gè)工件在第p道工序的第q臺(tái)處理器上處理所需時(shí)間Tijpq；第p道工序的第q臺(tái)處理器最早可用時(shí)間Fpq；訂單優(yōu)先因子Wi，訂單到達(dá)時(shí)間Ri，訂單交貨時(shí)間Di。

圖1 基于訂單完成柔性流水作業(yè)排序算法流程圖

（2）訂單排序。根據(jù)訂單的權(quán)重、到達(dá)時(shí)間和交貨時(shí)間計(jì)算各個(gè)訂單排隊(duì)指標(biāo)Qi，按Qi值的大小按升序方式將所有訂單進(jìn)行排序。

（3）訂單內(nèi)部工件排序。對(duì)于一個(gè)訂單的各個(gè)工件，根據(jù)當(dāng)前處理器運(yùn)行狀況，不考慮其他工件，按步驟（5）的最早最快加工方式試排入系統(tǒng)，計(jì)算其可能的最早最快加工完成時(shí)間Cfij，然后計(jì)算該工件可能的最小誤工時(shí)間Zfij。在得到訂單內(nèi)各個(gè)工件的Zfij后，根據(jù)Zfij的值按遞減順序?qū)⒐ぜ判颉?duì)所有訂單，都按此方法完成其各自所包括的工件的排序。

（4）作業(yè)排序。根據(jù)步驟（2）、（3）訂單和訂單內(nèi)部工件排序情況，從第1個(gè)訂單中取出第1個(gè)工件，按工序順序和步驟（5）、（6）的最早最快加工方式，將工件排入各個(gè)工序相應(yīng)的處理器作業(yè)隊(duì)列中。再取出第1個(gè)訂單的第2個(gè)工件按此方法排入各個(gè)工序的作業(yè)隊(duì)列中，直到第1個(gè)訂單的工件全部完成，再進(jìn)行第2個(gè)訂單工件作業(yè)排序，直到所有訂單的所有工件全部被排入處理器的作業(yè)隊(duì)列。

（5）最早最快加工排序方式。1個(gè)工件的第p道工序有多臺(tái)處理器可選時(shí)，對(duì)于第q臺(tái)處理器，按式（5）～（7）及式（10）確定本工件最早開始時(shí)間及最早完成時(shí)間，選擇排入具有最小完成時(shí)間的處理器隊(duì)列。

計(jì)算工件開始時(shí)間、完成時(shí)間和選擇處理器隊(duì)列時(shí)會(huì)遇到3種情況：①隊(duì)列無(wú)工件，直接排入；②隊(duì)列有工件，但某個(gè)工件開始時(shí)間比較晚，其前有空閑時(shí)間可以完成該工件的處理（開始空閑時(shí)間點(diǎn)不大于該工件的開始時(shí)間，空閑時(shí)間段結(jié)束時(shí)間不小于該工件的完成時(shí)間），則將該工件排入空閑時(shí)間內(nèi)完成；③隊(duì)列有工件，隊(duì)列中最后一個(gè)工件完成前不存在可以完成本工件處理的空閑時(shí)間，則把該工件排在隊(duì)列的最后面。

（6）同訂單處理器隊(duì)列優(yōu)化。新排入處理器隊(duì)列的工件，滿足步驟（5）中③的情況，而且隊(duì)列最后的1個(gè)或多個(gè)工件與該工件屬于同一訂單，則需要進(jìn)行同訂單處理隊(duì)列優(yōu)化。將該訂單插入同訂單的各個(gè)工件前面的位置。在插入某一位置后，并按步驟（5）將該工件的余下工序以及被影響的工件的本工序和余下工序都重新排好，計(jì)算該工件和所有被影響的工件的完成時(shí)間Cij和誤工時(shí)間Zij，并計(jì)算它們完成時(shí)間總和與誤工時(shí)間總和。比較該工件在該處理器隊(duì)列排在最后以及插入在不同位置時(shí)所涉及的工件誤工時(shí)間總和與完成時(shí)間總和，選取誤工時(shí)間總和最小的位置，如果誤工時(shí)間總和為0，則選取完成時(shí)間總和最小的位置，在選取的位置排定該工件，同時(shí)確定該工件余下工序的排序位置及被影響的其他工件在本工序及余下工序的排序位置。

4 應(yīng)用實(shí)例

在本實(shí)例中，作業(yè)處理包括3道工序，第1道工序有3臺(tái)處理器，第2道工序有2臺(tái)處理器，第3道工序有3臺(tái)處理器。同一道工序中的多臺(tái)處理器的性能也有所不同，其處理速度都是前者大于后者。

共有3個(gè)訂單，第1個(gè)訂單有3個(gè)工件，第2個(gè)訂單有2個(gè)工件，第3個(gè)訂單有3個(gè)工件。訂單到達(dá)時(shí)間、交貨時(shí)間以及權(quán)重系數(shù)如表1所示。

表1 訂單信息

處理器最早開始時(shí)間如表2所示。

表2 處理器最早開始時(shí)間

訂單中各個(gè)工件在不同處理器上的處理時(shí)間如表3所示。

表3 工件的處理時(shí)間

計(jì)算各個(gè)訂單的排序指標(biāo)Qi，再計(jì)算每個(gè)訂單內(nèi)所有工件的Cfij和Zfij，計(jì)算結(jié)果如表4所示。

表4 可能的最早完成時(shí)間、最小誤工時(shí)間及訂單排序指標(biāo)

訂單及其所包括的工件排序結(jié)果為：

按算法進(jìn)行作業(yè)排序，確定出yijpq的值，最終作業(yè)排序結(jié)果如表5所示。

需要說(shuō)明是：

（1）在工件J22排入M31（J13，J21）作業(yè)隊(duì)列時(shí)，排在J13和J21中間的空閑時(shí)間，J13的完成時(shí)間C1331=8，而J21的開始時(shí)間x2131=11，J22的上一工序的完成時(shí)間C2211=6，因此將J22排入M31作業(yè)隊(duì)列的空閑時(shí)間（8～11）內(nèi)，開始時(shí)間x2231=8，完成時(shí)間C2231=x2231+T2231=9，J21的完成時(shí)間C2131=13保持不變。

表5 作業(yè)排序結(jié)果

（2）在進(jìn)行工件J31的第2道工序作業(yè)排序時(shí)，可以排入M22（J12）作業(yè)隊(duì)列，形成M22（J12，J31），也可以排入M21（J11，J21，J32）作業(yè)隊(duì)列再進(jìn)行同訂單處理器作業(yè)隊(duì)列排序優(yōu)化，優(yōu)化時(shí)J31插入到J32前面，得到作業(yè)隊(duì)列M21（J11，J21，J31），J32在第2道工序的處理被重新調(diào)整而排入M22（J12，J32），J32的第3道工序仍排在M31作業(yè)隊(duì)列最后不變，這樣得到的J31、J32的誤工時(shí)間總和為1，比J31排入M22，J32排入M21的誤工時(shí)間總和2要小1個(gè)單位。因此，最終選取J31排入M21（J11，J21，J31），J32排入M22（J12，J32）。

經(jīng)過(guò)作業(yè)排序，得到訂單實(shí)際完成時(shí)間Ci、誤工時(shí)間Zi及加權(quán)誤工成本W(wǎng)i Zi的值，如表6所示。3個(gè)訂單中O1、O2都能按合同如期交貨，O3完成時(shí)間為18，誤工時(shí)間為1，加權(quán)誤工成本為2。

表6 訂單完成實(shí)際、誤工時(shí)間即加權(quán)誤工成本

5 結(jié)語(yǔ)

普通柔性流水作業(yè)排序中只考慮各自工件的完成情況，沒(méi)有考慮工件之間的相互關(guān)系。很多生產(chǎn)企業(yè)實(shí)際上采用按訂單進(jìn)行加工生產(chǎn)，因此，按訂單完成進(jìn)行柔性流水作業(yè)排序研究更具有實(shí)際意義。本文在前人成果的基礎(chǔ)上，研究基于訂單完成的柔性流水作業(yè)排序的算法，以訂單為單位，使得訂單的加權(quán)誤工成本最小來(lái)優(yōu)化排序，并通過(guò)實(shí)例應(yīng)用驗(yàn)證該了算法的有效性。