兩個(gè)代理的單機(jī)排序問題研究

馮 琪，孟金濤，鄭玉暉

（1．中原工學(xué)院，鄭州450007；2．鄭州航空工業(yè)管理學(xué)院，鄭州450015）

兩個(gè)代理的單機(jī)排序問題研究

馮 琪1，孟金濤2，鄭玉暉1

（1．中原工學(xué)院，鄭州450007；2．鄭州航空工業(yè)管理學(xué)院，鄭州450015）

研究了兩個(gè)代理的單機(jī)排序問題．其中第一個(gè)代理以完工時(shí)間和為目標(biāo)函數(shù)，第二個(gè)代理以誤工工件個(gè)數(shù)為目標(biāo)函數(shù)．排序問題的目標(biāo)是尋找一種排序，使得在第二個(gè)代理的目標(biāo)函數(shù)不超過給定上界的情況下，第一個(gè)代理的目標(biāo)函數(shù)最?。疚倪€對(duì)這一問題設(shè)計(jì)了一個(gè)擬多項(xiàng)式時(shí)間算法．

排序；兩個(gè)代理；擬多項(xiàng)式時(shí)間算法

廣義而言，排序問題可以理解為“最優(yōu)地分配資源于時(shí)間區(qū)間去完成一定的任務(wù)”．其中，資源可以有不同的種類，例如人力、物力、機(jī)器、能源及工具等資源；任務(wù)也有各種解釋，如從制造系統(tǒng)的機(jī)器加工到計(jì)算機(jī)系統(tǒng)的信息處理等．但是任務(wù)具有相同的特性，它們都有準(zhǔn)備時(shí)間、交工期限、權(quán)重、任務(wù)之間的先后約束以及描述完成任務(wù)與資源分配之間依賴關(guān)系的目標(biāo)函數(shù)．因此，我們可以一般性地將排序問題看成是“最優(yōu)地分配機(jī)器的時(shí)間去加工一些工件”．排序問題產(chǎn)生的背景主要是機(jī)器制造，后來被廣泛應(yīng)用于服務(wù)業(yè)、制造業(yè)、運(yùn)輸業(yè)、管理、計(jì)算機(jī)科學(xué)等領(lǐng)域．

所謂多代理（客戶）排序，是指有多個(gè)代理（客戶），每一個(gè)代理都有各自的工件集和各自的目標(biāo)函數(shù)，并且所有代理的工件競(jìng)爭(zhēng)使用共同的資源．它有廣泛的應(yīng)用，例如在一些共同的航線上，如何安排不同飛機(jī)的飛行，使得飛機(jī)可以最快到達(dá)目的地．該問題首先在文獻(xiàn)［1］和［2］中提出．文獻(xiàn)［3］研究了兩個(gè)代理的排序問題，目標(biāo)是尋找一個(gè)最優(yōu)排序，使所有代理的目標(biāo)函數(shù)和達(dá)到最優(yōu)．第一個(gè)代理的目標(biāo)函數(shù)為工件的完工時(shí)間和（或最大延遲），第二個(gè)代理的目標(biāo)函數(shù)為最大延遲給出了多項(xiàng)式時(shí)間算法．文獻(xiàn)［4］也考慮了兩個(gè)代理的排序問題．第一個(gè)代理的目標(biāo)函數(shù)為加權(quán)完工時(shí)間和，第二個(gè)代理的目標(biāo)函數(shù)為最大加權(quán)完工時(shí)間，目標(biāo)仍然是尋找一個(gè)最優(yōu)排序，使所有代理的目標(biāo)函數(shù)和達(dá)到最優(yōu)，并且證明了這一問題是強(qiáng)NP－困難的．關(guān)于多代理排序問題的近期研究，參見文獻(xiàn)［5－9］．

對(duì)于多個(gè)代理的排序問題，由于多個(gè)代理的工件要在相同的機(jī)器上加工，因此為了使某一目標(biāo)達(dá)到最優(yōu)，決策者要從全局的角度考慮問題，并且兼顧好每一個(gè)代理的利益，使代理各方互相合作、協(xié)調(diào)配合．下面研究的兩個(gè)代理的排序問題，就是要使第一個(gè)代理的目標(biāo)函數(shù)達(dá)到最優(yōu)，但是同時(shí)要保證第二個(gè)代理的利益，使第二個(gè)代理的目標(biāo)不會(huì)很差，即不超過給定的上界．

1 模 型

我們研究的問題模型描述如下：有兩個(gè)代理，分別具有工件集J（1）和J（2），其中個(gè)工件都可以在t＝0時(shí)刻開始在一臺(tái)機(jī)器上加工．和分別表示工件的加工時(shí)間和完工時(shí)間，令表示工件的工期（最遲的交貨時(shí)間）．第一個(gè)代理J（1）以它的工件的完工時(shí)間和為目標(biāo)函數(shù)．對(duì)于代理2的工件），若，則，這時(shí)稱不誤工；若則，這時(shí)稱誤工．第二個(gè)代理以它的誤工工件個(gè)數(shù)為目標(biāo)函數(shù)．我們的目標(biāo)是尋找一種排序，使得在滿足代理2的目標(biāo)函數(shù)不超過給定上界Q（Q＞0）的情況下，代理1的目標(biāo)函數(shù)最?。捎肎raham等人的三參數(shù)法［10］，可以把我們研究的問題表示為．對(duì)這一問題，文獻(xiàn)［9］證明了這是一般意義下NP－困難的．本文對(duì)該問題給出了一個(gè)擬多項(xiàng)式時(shí)間算法．

2 擬多項(xiàng)式時(shí)間算法

定義1 SPT－規(guī)則：將工件J1，J2，…，Jn按pj非減的順序排列的排序規(guī)則稱為最短加工時(shí)間優(yōu)先規(guī)則，簡(jiǎn)稱SPT－規(guī)則．

由文獻(xiàn)［11］可知：

定義2 EDD－規(guī)則：將工件J1，J2，…，Jn按dj非減的順序排列的排序規(guī)則稱為最早工期優(yōu)先規(guī)則，簡(jiǎn)稱EDD－規(guī)則．

由文獻(xiàn)［12］可知：

證明：假如存在一個(gè)最優(yōu)排序π，使得代理1的2個(gè)工件和不按SPT－規(guī)則排列，即，工件排在了工件的前面．將排序π做如下調(diào)整：交換工件和的位置，設(shè)所得排序?yàn)棣小洌瑒t有．此外，在π′中，介于工件和之間的工件的完工時(shí)間減少了，從而排序π′比排序π更好，這與π是最優(yōu)排序相矛盾．因此，對(duì)代理1的所有工件，重復(fù)上述做法，則得到一個(gè)最優(yōu)排序，使得代理1的工件按SPT－規(guī)則排列．

假如存在一個(gè)最優(yōu)排序π＊，在排序π＊中，代理2的工件的排列次序不滿足定理1．現(xiàn)將排序π＊做如下變動(dòng)：把代理2的所有誤工工件移到最后，設(shè)所得排序?yàn)棣小澹捎诎阉胁徽`工的工件往前移動(dòng)了，顯然，）．由引理2可知，在π″中，將J（2）中所有不誤工的工件按EDD－規(guī)則排列，這不會(huì)增加誤工工件個(gè)數(shù)，因而得到的排序π″比π＊更好，這與π＊是最優(yōu)排序相矛盾，定理1得證．

定義3 有效排序：如果一個(gè)排序滿足定理1，稱這一排序是有效排序．

由定理1，我們只需要考慮有效排序．為此，在SPT－規(guī)則之下，將代理1的工件重新標(biāo)號(hào)，使得；在EDD－規(guī)則之下，將代理2的工件重新標(biāo)號(hào)，使得．

首先，給出下面2個(gè)定義：

定義4f（i，j，t，u）是滿足下列條件的排序的最優(yōu)目標(biāo)函數(shù)值：

（2）當(dāng)前排序的最大完工時(shí)間（makespan）是t；

（3）在當(dāng)前排序中，代理2的誤工工件個(gè)數(shù)是u（u≤Q）．

定義5P（i，j）是代理1的前i個(gè)工件和代理2的前j個(gè)工件（不包括誤工工件）的所有的加工時(shí)間之和．

證明：包含代理1的前i個(gè)工件和包含代理2的前j個(gè)工件的最優(yōu)排序中，最后一個(gè)工件或者是工件，或者是工件．因此，考慮下面的幾種情形：

（1）邊界條件：

如果t＝u＝0，則f（0，0，t，u）＝0；否則，f（0，0，t，u）＝＋∞．

（2）遞推函數(shù)：

（3）最優(yōu)值：

下面分析算法的計(jì)算復(fù)雜性．由于，則至多有個(gè)不同的狀態(tài)變量，并且每次迭代均花費(fèi)一個(gè)常數(shù)時(shí)間．因此，算法的時(shí)間復(fù)雜性為，即可以在）時(shí)間內(nèi)得出問題的最優(yōu)解，定理2證畢．

3 結(jié) 語

本文研究了兩個(gè)代理的排序問題．第一個(gè)代理的目標(biāo)函數(shù)是工件的完工時(shí)間和，第二個(gè)代理的目標(biāo)函數(shù)是誤工工件的個(gè)數(shù)．排序問題的目標(biāo)是尋找一種最優(yōu)排序，在滿足第二個(gè)代理的目標(biāo)函數(shù)不超過給定上界的情況下，第一個(gè)代理的目標(biāo)函數(shù)最?。疚倪€對(duì)該問題給出了一個(gè)擬多項(xiàng)式時(shí)間算法．下一步的研究方向是給出這一問題的全多項(xiàng)式時(shí)間近似方案．

［1］Baker K R，Smith J C．A Multiple－criterion Model for Machine Scheduling［J］．Journal of Scheduling，2003，6：7－16．

［2］Agnetis A，Mirchandani P B，Pacciarelli D，et al．Scheduling Problems with Two Competing Agents［J］．Opeartions Research，2004，52：229－242．

［3］Yuan J J，Shang W P，F(xiàn)eng Q．A Note on the Scheduling with Two Families of Jobs［J］．Journal of Scheduling，2005，8：537－542．

［4］馮琪，原晉江．一個(gè)具有兩類工件的多目標(biāo)排序的NP－困難性［J］．運(yùn)籌學(xué)學(xué)報(bào)，2007，11（4）：121－126．

［5］Cheng T C E，Ng C T，Yuan J J．Multi－agent Scheduling on a Single Machine to Minimize Total Weighted Number of Tardy Jobs［J］．Theoretical Computer Science，2006，362：273－281．

［6］Cheng T C E，Ng C T，Yuan J J．Multi－agent Scheduling on a Single Machine with Max－form Criteria［J］．European Journal of Operational Research，2008，188：603－609．

［7］Ng C T，Cheng T C E，Yuan J J．A Note on the Complexity of the Problem of Two－agent Scheduling on a Single Machine［J］．Journal of Combinatorial Optimization，2006，12：387－394．

［8］Agnetis A，Pacciarelli D，Pacifici A．Multi－agent Single Machine Scheduling［J］．Annals of Operations Research，2007，150：3－15．

［9］Leung J Y T，Pinedo M，Wan G．Competitive Two－agent Scheduling and Its Applications［J］．Operations Research，2010，58：458－469．

［10］Graham P L，Lawler E L，Lenstra J K，et al．Optimization and Approximation in Deterministic Machine Scheduling：A survey［J］．Annals of Discrete Mathematics，1979，5：287－326．

［11］Brucker P．Scheduling Algorithms（Third Edition）［M］．Berlin：Springer－Verlag，2001．

［12］Moore J M．An Job，One Machine Sequencing Algorithm for Minimizing the Number of Late Jobs［J］．Management Science，1968，15：102－109．

Study on a Two－agent Scheduling Problem on a Single Machine

FENG Qi1，MENG Jin－tao2，ZHENG Yu－h(huán)ui1
（1．Zhongyuan University of Technology，Zhengzhou 450007；2．Zhengzhou Institute of Aeronautical Industry Management，Zhengzhou 450015，China）

A two－agent scheduling problem on a single－machine is researched．The first agent has the total completion time as its objective function，and the second agent has the number of tardy jobs as its objective function．The goal of the problem is to seek for a schedule such that the objective function of the first agent is minimized，given that the objective function of the second agent does not exceed the given upper bound．A pseudo－polynomial－time algorithm for the problem is given．

scheduling；two－agent；pseudo－polynomial－time algorithm

O223

A

10．3969／j．issn．1671－6906．2012．01．001

1671－6906（2012）01－0001－03

2012－01－03

國(guó)家自然科學(xué)基金項(xiàng)目（10971201；61070229；10901144）；教育部博士點(diǎn)基金項(xiàng)目（20111401110005）；河南省自然科學(xué)研究計(jì)劃項(xiàng)目（112300410047）；河南省教育廳自然科學(xué)研究計(jì)劃項(xiàng)目（2010A110004）

馮 琪（1975－），女，河南周口人，講師，博士生．