具有交期約束的非同質顧客并行機競爭調度

王長軍，賈永基

（東華大學 旭日工商管理學院，上海 200051）

具有交期約束的非同質顧客并行機競爭調度

王長軍，賈永基

（東華大學 旭日工商管理學院，上海 200051）

考慮面向具有交期要求的非同質顧客的并行機調度問題，其中，不同顧客具有不同等待敏感程度，且具有各自的交期約束.為此，采用非合作博弈建立描述該問題的模型，并提出一種包含松弛、可行化和交互協調三步的啟發式算法.算例仿真進一步闡述和驗證所提方法的有效性.

并行機調度；非同質顧客；交期；啟發式算法

顧客對于等待是敏感的［1］，等待的情況將直接影響顧客對于服務的評價［2］.為此，按照顧客對于等待的敏感程度，為其提供產品或服務，是企業應當具有的一項重要的能力.但是，不同顧客會因為經營模式、產品或服務對其重要程度等差異，而呈現明顯不同的等待特性.比如，對于采用精益運作模式的顧客而言，最常見的越快越好的規則未必適用他們.在出口與內需共存，實物渠道和電子渠道并重的今天，不同的時間效用已成為顧客訴求差異化的一項重要體現.這自然會給供應鏈帶來影響，也需要提供產品或服務的企業做出相應的調整.

現有運作研究多假定顧客為同質（homogeneity），但也開始有研究者關注不同顧客具有不同時間效用 （time utility，后簡稱“時效”）函數［3］，即非同質顧客的情況.如文獻［4］在供應方為單機的情況下，考慮兩類分別具有不同時效函數的顧客，并證明這樣的問題為非確定性多項式困難（non－deterministic polynomial－hard，NP－hard）.文獻［5］深入研究了非同質顧客給全局最優的實現帶來的影響，即無秩序代價（price of anarchy），給出了不同情況下的明確上下界.文獻［6］在單機環境下，既考慮了顧客的非同質時效函數，又考慮了供應方的目標，最終給出一種求解具有良好全局性能的Nash均衡調度的算法.

但是，在很多情況下顧客對時效的要求可能很復雜，除了能夠反映對于等待敏感程度的時效函數之外，顧客通常還會提出一個最終的交貨時間要求，即交期約束.而這一點是現有針對非同質顧客的運作研究還沒有充分考慮的.

為此，本文在并行機下考慮顧客除具有不同的時效函數外，還具有各自的交期約束的情況.并行機擁有者要在實現自身利益最大化的同時，兼顧顧客的時效函數，并滿足交期約束.首先，對于非同質顧客這一多人多目標問題，建立基于非合作博弈的數學模型，并采用Nash均衡調度概念描述模型的解.繼而，針對并行機的物理約束和顧客的交期約束，利用拉格朗日松弛建立相應的松弛模型，并由此設計出包含松弛、可行化調整和交互協調三步的啟發式算法.最后，通過算例仿真驗證本文提出方法的有效性.

1 問題描述與分析

選擇并行機中的同速并行機作為供應方的生產環境.同速并行機的特點是所有機器具有相同加工功能和相同且恒定的加工速度.考慮一個n個任務和m臺同速并行機調度問題.供應方具有目標函數M.同時，每個任務Ji都具有獨立的時效函數fi（wi）和交期DLi要求，并對應一個獨立的顧客.借鑒文獻［6］在單機下的模型，可得到并行機中如下數學模型.

其中：ri，pi和Ci分別為Ji的到達、加工和完工時間，均為整數；wi是Ji加工前的等待時間，為優化的決策變量，滿足式（3）；H 是規劃時域，H 應足夠大以完成所有任務的加工.

模型中，式（1）和（2）分別是任務時效函數和供應方的經濟性指標，式（4）隱含了不可搶占約束，即任一任務必須連續加工直至完工.式（4）和（5）構成了機器容量約束，即任一機器在同一時刻最多只能加工一個任務.圖1所示為模型中各變量圖示.

圖1 同速并行機變量圖示Fig.1 Illustration of variables in parallel machine

除了任務和供應方指標外，本文還考慮顧客對于任務完成最終期限的要求，描述為即任務Ji必須在DLi之前完成.交期DLi是由顧客i提出的.在供應能力有限時，可能無法滿足所有任務交期要求.因此，約束（6）應是可協商的，本文用DLimax來表示Ji對其交期的最大容忍底線.

由式（1）～（6）構成了一個帶約束的多人多目標優化問題.其中：式（1）和（2）是優化目標；式（3）～（5）是必須滿足的物理約束；式（6）則是一種柔性約束.傳統同速并行機調度研究僅考慮問題（2）～（5）.本文不僅考慮了任務時效（1），也同時考慮了約束（6）.對于如上的多人多目標問題，類似文獻［5－6］，采用非合作博弈進行研究.為此，定義滿足式（6）和式（7）的調度w＊（w＊＝（w＊1，…，w＊n））為模型的解，即Nash均衡調度.

Nash均衡調度w＊是顧客之間競爭現有生產資源的一種均衡結果，在這個解中，除破壞約束或惡化其他顧客的調度結果，否則每個顧客都不能改進自身的調度結果.但是，與博弈理論中個體理性與集體理性常常沖突的情況類似，Nash均衡調度w＊可能具有很差的全局性能［5］.為此，需要在多個Nash均衡調度w＊中選取具有良好全局性能指標（2）的結果.此外，過強的約束（6）可能導致沒有滿足任務交期要求的w＊，這將是后文要重點解決的一個問題.

2 算法設計

本節給出一種基于模型，并由供需各方參與決策的啟發式算法求解上述問題.求解算法分為三階段.

在第一階段，首先將難約束松弛，其中不僅包括物理約束式（4）和（5），也包括交期要求式（6），得到只具有簡單約束（3）的多人多目標優化問題.此時可以將文獻［6］在單機下的算法擴展到同速并行機下，求出一個能較好滿足各方經濟性指標的Nash均衡調度.

第二階段以第一階段的解為基礎，進行以可行化為目的的協調.即通過調整任務加工順序，降低調度中的不可行程度，如果能得到可行的Nash均衡調度，則計算結束.否則，進入第三階段.

第三階段按設定規則與顧客協調，逐步修正部分交期約束，重復上面的步驟，直到出現供需各方接受的調度結果，即可行的Nash均衡結果.但是，如果所有顧客均放松其交貨要求至DLmaxi，仍無法得到可行的解，則說明約束過緊，部分顧客無法成功競爭到機器資源.

2.1 松弛模型的建立和求解

為簡化求解，考慮將難約束式（4）～（6）松弛，分別結合到各個任務的時效函數中，從而形成簡單約束的多人多目標優化問題.其中，對式（4）～（6）采用不同的松弛方式.為將式（6）松弛，將各個Ji的時效函數fi中大于DLi的懲罰值設為一極大數R，如圖2，得到新的時效函數fi′（wi）.這種剛性的懲罰方式，保證了計算結果必定滿足約束式（6）.對式（4）和（5），將其通過拉格朗日乘子πk結合到各個任務的時效函數中.于是，可得松弛后的任務時效函數為

式中：πk可看作是供應方為其每段資源設定的價格，其值不小于0；Pik則是Ji為使用第k時段資源的支付.

圖2 式（6）松弛示意圖Fig.2 Illustration of relaxing formula（6）

對于難約束松弛后的多人多目標模型，類似地，定義滿足式（3）和（10）的調度 w′（w′＝（w′1，…，w′n））為松弛后模型的Nash均衡調度.

此處，可將文獻［6］算法擴展到同速并行機下.基本思路為給定機器資源價格π，任務根據各自時效函數（8）并行地競爭機器資源，而機器則根據任務競爭結果和自身全局目標（2），改變資源價格π，以引導顧客自利行為結果趨向于全局優化.循環迭代，直至各方均不改變自身策略為止，最終產生一個具有良好全局目標（2）的w′.由此，設計如下的松弛模型求解算法.

（3）計算松弛后的全局性能指標Mr＝根據上一步中確定的任務開工順序，采用List scheduling［7］方法可行化，并計算可行化調度的全局目標，作為

（5）r＝r＋1，轉（1）.

注意到，與約束（6）的剛性松弛方式不同，容量約束的松弛采用柔性懲罰，故所得解w′滿足式（6），但未必滿足式（5）.下節需將w′可行化，以得到原模型的w＊.

2.2 可行化調整

為在可行化過程中區分各個任務交期的緊迫程度，首先定義顧客任務的自由度

Fi≤0表明Ji的完工時間沒有違反約束（6），具有｜Fi｜的自由度；而當Fi＞0時，則說明其至少需要提前Fi個時間單位完工才能滿足約束.實際生產環境中，供應方可根據任務的時效函數情況對任務設定相應的優先級.對于具有高優先級的任務，應盡量保證其完工時間在交期要求之前.

如前所述，w′未必滿足式（5）.如果簡單地使用List Scheduling［7］方法將 w′可行化，使其不違反式（5），得出的結果可能違反約束（6）.為此，設計一種深度搜索算法，其指導思想是根據先約束后指標，先物理約束后任務要求的順序對w′進行改造.目的是在保證滿足物理約束前提下，減少違反約束（6）的任務數目，經濟性指標則被放到最次的位置.從而形成一個滿足全部物理約束和部分交貨要求的Nash均衡調度w＊，并由此判定問題可行性，給出供交互協調的定量信息.這種處理方式的本質是在保證可行的前提下最大限度保留了對優化的要求.

算法采用滾動的方式，不斷地根據任務優先級和自由度局部地調整其加工順序，包括確定局部子問題、調度子問題、執行子問題的部分解.其中，局部子問題的選擇采用文獻［8］中的沖突窗口方式，即選擇w′中最靠前的任意兩個之間相互重疊的任務（后任務的開工時間大于前任務的完工時間）集合作為當前子問題，其優點在于準確地考慮了當前可能加工的任務.子問題調度則主要根據任務自由度和優先級對第一階段結果進行調整.每次迭代只確定一個任務.具體算法如下所述.

（1）定義S為w′中所有任務集合，迭代次數r＝0，r次迭代時機器最早空閑時間為Br，B0＝0.按任務在調度w′中的開工順序給所有任務編號；開工時間相同的，則按其當前的優先級由大到小順序編號；若開工時間與優先級均相同，則按其加工時間由小到大順序編號.

（2）按時間軸由小到大的順序，在S中尋找第一個局部子問題任務集合I（r）.顯然有任意Jt，Jt＋1∈I（r）滿足rt＋wt≤rt＋1＋wt＋1＜rt＋wt＋pt.按List scheduling將I（r）中任務可行化.

（3）記當前I（r）中編號最小的任務為Ji.對于I（r）的可行化調度，如果 ?Jk∈I（r）滿足Fk≤0，則Ji的開工時間為 max｛ri，Br｝，S＝S－｛Ji｝，更新Br，轉（5）.

（4）在集合I（r）的所有不滿足約束（6）的任務中，記優先級別最高的為Jj，如果優先級別最高的有多個，則Jj為其中編號最小的.若Jj的優先級小于Ji，且Jj先加工，余者按List scheduling加工使得I（r）中違反約束（6）的任務個數減少，則Jj的開工時間為max｛rj，Br｝.或者Jj的優先級大于Ji，則Jj的開工時間為 max｛rj，Br｝，更新Br，S＝S－｛Jj｝.

（5）r＝r＋1，對于 ?Jk∈S，如果rk＋wk＜Br，則令wk＝Br－rk.如果S不為空，則轉（2）.

（6）反饋每個任務的自由度Fi，計算結束.

步驟（2）是尋找子問題，步驟（3）和（4）求解子問題，算法體現了前文所述的思路，即首要滿足物理約束，然后再考慮如何減少違反約束式（6）的任務，而經濟性指標被放到了最后.改造后所得結果必定滿足物理約束.由算法過程可知，它符合Nash均衡調度w＊定義中的式（7）.所以，如果該結果也滿足任務要求，則該結果就是可行的w＊，整個計算結束.否則，則需通過與顧客的交互，在一定程度上放松部分DLi值，以增加調度可行的可能性.

2.3 交互協調

該階段是在可行化調整的計算結果，特別是任務自由度的基礎上，依據顧客能夠承受超期，供應方與顧客的交互協調過程.用協調因子ki（∈（0，1］）和DLimax兩個常數來描述Ji在交互中的協調可能程度，它們均由顧客自己給定.

對于第二階段的調度結果，如果Ji的自由度Fi大于0，其DLi能夠增加的值記為εi，

如果計算過程中得到可行的w＊，則整個計算終止.否則，當最近兩次迭代中均出現所有任務的εi＝0，且仍有部分任務的Fi＞0時，說明已沒有協商余地，計算終止.此時，由于供應方能力的限制，已無法滿足所有顧客.

3 仿真實例

考慮兩同速并行機調度問題，供應方目標為最小化完工時間之和.顧客具有如圖3所示的常用時效函數，其中：Ⅰ和Ⅱ型分別對應完工時間和延遲時間，文獻［9］定義Ⅲ型時效函數如式（13）所示.

其中：Ti為大于di的常數.文獻［6］改進Ⅲ型指標得Ⅳ型指標如式（14）所示.

Ⅳ型指標與Pinedo型［10］指標類似.圖3（e）和3（f）給出了兩種二次型指標Ⅴ型和Ⅵ型，分別是完工時間平方［11］和延期時間平方［12］.此外，還考慮Ⅶ型［13］和Ⅷ 型［14］兩種指數型指標如式（15）和 （16）所示.

其中：0＜αi2＜1.

顯然，上述8種指標均是隨等待時間單調非減的.

本文僅考慮待加工任務信息公開，即完全信息的情況.具體信息如表1，其中：f1（w1）＝C1；f2（w2）＝max｛0，C2－d2｝，d2＝8；f3（w3）具有Ⅲ型指標，d3＝15，T3＝20，ω3＝1；f4（w4）為Ⅳ型，其中：d4＝15，T4＝22，ω41＝1，ω42＝0.5；f5（w5）＝C25；當C6小于d6（＝25）時，f6（w6）為0，否則為（C6－d6）2；f7（w7）和f8（w8）為Ⅶ和Ⅷ型指標，其中：α71＝5，α72＝0.5，α8＝1，d8＝25.

根據任務特點確定其優先級：具有線性指標的J1，J2，J3，J4優先級為1，J7雖為指數型指標，注意到它具有固定的上限，所以設定它的優先級也為1；具有2次型指標的J5和J6優先級為2；J8優先級最高，為3.

表1 待加工任務信息Table 1 Information of tasks

運用本文算法，對上述問題采用Visual Studio 2010編程，在主頻為2.53GHz的電腦上進行運算.第一輪計算中，第一階段的w′計算結果如表2所示，顯然，該結果滿足式（6），但不滿足式（5）.經第二階段計算，得到調度如表3所示，此調度結果很好地平衡了供需之間的成本，通過放棄部分全局目標，獲得了較好的顧客加工成本，但是，該結果不能滿足J3和J7的交貨約束式（6）.為此，對J3和J7進行交互協調，如J3和J7的協調因子k3＝0.5，k7＝0.6，DLmax3＝35，DLmax7＝25，修正后的DL3和DL7分別為30和25.將J3和J7的優先級別分別加1，然后進入第二輪計算，兩階段計算結果如表4所示.此結果可行，計算結束.

表2 第一輪第一階段計算結果Table 2 Computing results of the 1st period in the 1st round

表3 第一輪第二階段計算結果Table 3 Computing results of the 2nd period in the 1st round

表4 第二輪兩階段計算結果Table 4 Computing results of the 2nd period in the 2nd round

觀察表3和4中的∑Ci和∑fi值，在不斷調整以滿足顧客交貨要求的過程中，對于經濟性指標的要求逐漸被弱化.這一現象是必然的，與前文所述一致.

4 結 語

顧客時效和交期要求客觀存在且有差異，不應被同質化.本文在同速并行機下針對具有交期約束的非同質顧客，展開調度建模與算法研究.研究從競爭調度的角度，采用非合作博弈建立了問題的模型，并設計了一種三階段的求解算法.首先模擬顧客對資源的競爭過程，給出一個考慮各方面優化指標和交貨要求的初始調度.然后，進行可行化調整.由于可能存在約束過緊導致無可行解的情況，為此，最后通過一種簡單有效的交互方式來予以協調解決.通過算例仿真驗證所提方法的有效性.研究結果為這類問題的解決提供了輔助決策依據.本文假設顧客信息為已知，即完全信息，而不完全信息的情況則有待今后的進一步研究.

［1］陳劍，張楠.針對等待敏感顧客的缺貨補償與庫存策略研究［J］.管理科學學報，2008，11（3）：53－62.

［2］MAISTER D H.The psychology of waiting lines［M］//CZEPIEL J A，SOLOMON M R，SURPRENANT C F.The service encounter：Managing employee/customer interaction in service businesses. Lexington： Lexington Books，1985：113－123.

［3］MURPHY P R J，WOOD D F.當代物流學［M］.北京：中國人民大學出版社，2009.

［4］KENNETH R B，SMITH J C.A multiple－criterion model for machine scheduling［J］.Journal of Scheduling，2003，6（1）：7－16.

［5］王長軍，賈永基，徐琪，等.并行機下獨立任務調度的無秩序代價分析［J］.管理科學學報，2010，13（5）：44－50，81.

［6］王長軍，王志宏，賈永基.單機排序模型下自利任務的無秩序代價分析與機制設計［J］.東華大學學報：自然科學版，2010，36（6）：680－685，702.

［7］LUH P B，HOITOMT D J， MAX E，et al.Schedule generation and reconfiguration for parallel machines［J］.IEEE Transactions on Robotics and Automation，1990，6（6）：687－696.

［8］WANG C J，XI Y G.A rolling optimization algorithm based on collision window for single machine scheduling problem［J］.Journal of Systems Engineering and Electronics，2005，16（4）：816－822.

［9］KETHLEYA R B，BAHARAM A.Single machine scheduling to minimize total weighted late work：A comparison of scheduling rules and search algorithms［J］.Computers ＆Industrial Engineering，2002，43（3）：509－528.

［10］PINEDO M.Scheduling：Theory，algorithms and systems［M］.New Jersey：Prentice Hall，1995.

［11］CHENG T E，LIU Z H.Parallel machine scheduling to minimize the sum of quadratic completion times［J］.IIE Transactions，2004，36（1）：11－17.

［12］SUN X Q，NOBLE J S， KLEIN C M.Single－machine scheduling with sequence dependent setup to minimize total weighted squared tardiness［J］.IIE Transactions，1999，31（2）：113－124.

［13］ROTHKOPF M H.Scheduling independent tasks on parallel processors［J］.Management Science，1966，12：437－447.

［14］CHEN B，POTTS C N，WOEGINGER G J.A review of machine scheduling： Complexity， algorithms and approximation［M］//DU D Z，PARDALOS P M.Handbook of combinatorial optimization. Dordrecht： Kluwer Academic Publishers，1998：21－169.

Competitive Scheduling in Parallel Machine for Non－homogeneous Customers with Due－Date Constraints

WANG Chang－jun，JIA Yong－ji
（Glorious Sun School of Business and Management，Donghua University，Shanghai 200051，China）

A parallel machine scheduling problem with non－homogeneous customers is considered，in which different customers have heterogeneous waiting－sensitive characteristics and independent due－date constraints.Based on the practical problem，a noncooperative game is used to describe such issues and a heuristic algorithm including relaxation，feasibility and interactive coordination is designed.The effectiveness of the proposed method is further illustrated and validated via a computational experiment.

parallel machine scheduling；non－homogeneous customers；due－date；heuristic algorithm

C 935

A

2012－03－06

國家自然科學基金資助項目（70772073，60874076，71172174）；中央高校基本科研業務費專項資金資助項目（11D10826）

王長軍（1976—），男，安徽巢湖人，講師，博士，研究方向為調度理論與方法.E－mail：cjwang＠dhu.edu.cn

1671－0444（2012）03－0332－06