胡代平，吳瑞明，徐博藝

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

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

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

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

（1）1個工件在每道工序只能至多被1臺處理器處理。

（2）每臺處理器1次只能至多處理1個工件，1個工件1次只能至多在1個處理器被處理。

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

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

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

2.1 問題描述

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

（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個工件經(jīng)過第p道工序處理的完成時間。

Cij—第i個訂單的第j個工件完成時間。

Ci—第i個訂單的完成時間。

Fpq—第p道工序第q臺處理器最早可以開始處理的時間，即最早可用時間。

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

模型的決策變量：

xijpq—第i個訂單的第j個工件在第p道工序的第q臺處理器上的開始時間。

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

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

Zi—第i個訂單延誤的時間長度，即誤工時間。

Ei—第i個訂單提前完工的時間長度。

2.3 模型表示

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

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

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

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

對于第i個訂單的第j個工件在第p道工序第q臺處理器上的開始時間不小于該處理器最早可用時間，且不小于訂單i的到達時間。

1個工件在第p道工序的開始時間不小于第p-1道工序的完成時間。

1個工件在第p道工序的完成時間，如果不需要本工序的處理，則為上一道工序完工時間Cij（p-1），如果需要本道工序的處理，假定在第q臺處理器上進行處理，則本當工序的完成時間為開始時間加上處理時間。通用的約束可以寫為如下形式：

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

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

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

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

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

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

在算法描述中，還用到以下符號：

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

Zfij—不考慮其他工件時，第i個訂單第j個工件可能的最小誤工時間長度，Zfij=Cfij-Di，可以小于0。

Qi—第i個訂單排序指標

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

具體算法如下：

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

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

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

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

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

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

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

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

4 應(yīng)用實例

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

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

表1 訂單信息

處理器最早開始時間如表2所示。

表2 處理器最早開始時間

訂單中各個工件在不同處理器上的處理時間如表3所示。

表3 工件的處理時間

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

表4 可能的最早完成時間、最小誤工時間及訂單排序指標

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

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

需要說明是：

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

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

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

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

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

5 結(jié)語

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