具有交期約束的非同質(zhì)顧客并行機(jī)競爭調(diào)度

王長軍，賈永基

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

具有交期約束的非同質(zhì)顧客并行機(jī)競爭調(diào)度

王長軍，賈永基

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

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

并行機(jī)調(diào)度；非同質(zhì)顧客；交期；啟發(fā)式算法

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

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

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

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

1 問題描述與分析

選擇并行機(jī)中的同速并行機(jī)作為供應(yīng)方的生產(chǎn)環(huán)境.同速并行機(jī)的特點(diǎn)是所有機(jī)器具有相同加工功能和相同且恒定的加工速度.考慮一個(gè)n個(gè)任務(wù)和m臺同速并行機(jī)調(diào)度問題.供應(yīng)方具有目標(biāo)函數(shù)M.同時(shí)，每個(gè)任務(wù)Ji都具有獨(dú)立的時(shí)效函數(shù)fi（wi）和交期DLi要求，并對應(yīng)一個(gè)獨(dú)立的顧客.借鑒文獻(xiàn)［6］在單機(jī)下的模型，可得到并行機(jī)中如下數(shù)學(xué)模型.

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

模型中，式（1）和（2）分別是任務(wù)時(shí)效函數(shù)和供應(yīng)方的經(jīng)濟(jì)性指標(biāo)，式（4）隱含了不可搶占約束，即任一任務(wù)必須連續(xù)加工直至完工.式（4）和（5）構(gòu)成了機(jī)器容量約束，即任一機(jī)器在同一時(shí)刻最多只能加工一個(gè)任務(wù).圖1所示為模型中各變量圖示.

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

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

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

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

2 算法設(shè)計(jì)

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

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

第二階段以第一階段的解為基礎(chǔ)，進(jìn)行以可行化為目的的協(xié)調(diào).即通過調(diào)整任務(wù)加工順序，降低調(diào)度中的不可行程度，如果能得到可行的Nash均衡調(diào)度，則計(jì)算結(jié)束.否則，進(jìn)入第三階段.

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

2.1 松弛模型的建立和求解

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

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

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

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

此處，可將文獻(xiàn)［6］算法擴(kuò)展到同速并行機(jī)下.基本思路為給定機(jī)器資源價(jià)格π，任務(wù)根據(jù)各自時(shí)效函數(shù)（8）并行地競爭機(jī)器資源，而機(jī)器則根據(jù)任務(wù)競爭結(jié)果和自身全局目標(biāo)（2），改變資源價(jià)格π，以引導(dǎo)顧客自利行為結(jié)果趨向于全局優(yōu)化.循環(huán)迭代，直至各方均不改變自身策略為止，最終產(chǎn)生一個(gè)具有良好全局目標(biāo)（2）的w′.由此，設(shè)計(jì)如下的松弛模型求解算法.

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

（5）r＝r＋1，轉(zhuǎn)（1）.

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

2.2 可行化調(diào)整

為在可行化過程中區(qū)分各個(gè)任務(wù)交期的緊迫程度，首先定義顧客任務(wù)的自由度

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

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

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

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

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

（3）記當(dāng)前I（r）中編號最小的任務(wù)為Ji.對于I（r）的可行化調(diào)度，如果 ?Jk∈I（r）滿足Fk≤0，則Ji的開工時(shí)間為 max｛ri，Br｝，S＝S－｛Ji｝，更新Br，轉(zhuǎn)（5）.

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

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

（6）反饋每個(gè)任務(wù)的自由度Fi，計(jì)算結(jié)束.

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

2.3 交互協(xié)調(diào)

該階段是在可行化調(diào)整的計(jì)算結(jié)果，特別是任務(wù)自由度的基礎(chǔ)上，依據(jù)顧客能夠承受超期，供應(yīng)方與顧客的交互協(xié)調(diào)過程.用協(xié)調(diào)因子ki（∈（0，1］）和DLimax兩個(gè)常數(shù)來描述Ji在交互中的協(xié)調(diào)可能程度，它們均由顧客自己給定.

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

如果計(jì)算過程中得到可行的w＊，則整個(gè)計(jì)算終止.否則，當(dāng)最近兩次迭代中均出現(xiàn)所有任務(wù)的εi＝0，且仍有部分任務(wù)的Fi＞0時(shí)，說明已沒有協(xié)商余地，計(jì)算終止.此時(shí)，由于供應(yīng)方能力的限制，已無法滿足所有顧客.

3 仿真實(shí)例

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

其中：Ti為大于di的常數(shù).文獻(xiàn)［6］改進(jìn)Ⅲ型指標(biāo)得Ⅳ型指標(biāo)如式（14）所示.

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

其中：0＜αi2＜1.

顯然，上述8種指標(biāo)均是隨等待時(shí)間單調(diào)非減的.

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

根據(jù)任務(wù)特點(diǎn)確定其優(yōu)先級：具有線性指標(biāo)的J1，J2，J3，J4優(yōu)先級為1，J7雖為指數(shù)型指標(biāo)，注意到它具有固定的上限，所以設(shè)定它的優(yōu)先級也為1；具有2次型指標(biāo)的J5和J6優(yōu)先級為2；J8優(yōu)先級最高，為3.

表1 待加工任務(wù)信息Table 1 Information of tasks

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

表2 第一輪第一階段計(jì)算結(jié)果Table 2 Computing results of the 1st period in the 1st round

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

表4 第二輪兩階段計(jì)算結(jié)果Table 4 Computing results of the 2nd period in the 2nd round

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

4 結(jié) 語

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

［1］陳劍，張楠.針對等待敏感顧客的缺貨補(bǔ)償與庫存策略研究［J］.管理科學(xué)學(xué)報(bào)，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.當(dāng)代物流學(xué)［M］.北京：中國人民大學(xué)出版社，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ī)下獨(dú)立任務(wù)調(diào)度的無秩序代價(jià)分析［J］.管理科學(xué)學(xué)報(bào)，2010，13（5）：44－50，81.

［6］王長軍，王志宏，賈永基.單機(jī)排序模型下自利任務(wù)的無秩序代價(jià)分析與機(jī)制設(shè)計(jì)［J］.東華大學(xué)學(xué)報(bào)：自然科學(xué)版，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－h(huán)omogeneous 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－h(huán)omogeneous 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－h(huán)omogeneous customers；due－date；heuristic algorithm

C 935

A

2012－03－06

國家自然科學(xué)基金資助項(xiàng)目（70772073，60874076，71172174）；中央高?；究蒲袠I(yè)務(wù)費(fèi)專項(xiàng)資金資助項(xiàng)目（11D10826）

王長軍（1976—），男，安徽巢湖人，講師，博士，研究方向?yàn)檎{(diào)度理論與方法.E－mail：cjwang＠dhu.edu.cn

1671－0444（2012）03－0332－06