工件可拒絕的兩個(gè)代理排序問(wèn)題的全多項(xiàng)式時(shí)間近似方案

馮 琪, 楊麗華, 狄 帥

(1- 中原工學(xué)院理學(xué)院，鄭州 450007; 2- 京東數(shù)字科技，北京 100015)

1 引言

排序(調(diào)度)就是在一定的條件下對(duì)工件(產(chǎn)品)和機(jī)器按時(shí)間進(jìn)行分配和安排加工次序，使一個(gè)或多個(gè)指標(biāo)達(dá)到最優(yōu).機(jī)器制造業(yè)的發(fā)展是排序發(fā)展的主要推動(dòng)力.后來(lái)，隨著社會(huì)的進(jìn)步和經(jīng)濟(jì)的快速發(fā)展，在人們的工作和生活中產(chǎn)生了越來(lái)越多的排序問(wèn)題.例如：如何將原材料放在機(jī)器上加工成人們需要的各種產(chǎn)品，并且用料最省或利潤(rùn)最大？如何將生產(chǎn)出來(lái)的零件以一定的次序快速組裝成產(chǎn)品？在大型工程的興建中，如何對(duì)各類人員進(jìn)行安排，對(duì)各種器材的供應(yīng)進(jìn)行調(diào)度？對(duì)于種類繁多的網(wǎng)購(gòu)物品，快遞公司如何調(diào)度，使得快遞員以最快速度把大量物品送到客戶手中？這些都是排序問(wèn)題.因此，在現(xiàn)代化的生活中，服務(wù)業(yè)、制造業(yè)、運(yùn)輸業(yè)、計(jì)算機(jī)科學(xué)等領(lǐng)域都有它的大量應(yīng)用.排序的好壞直接影響著費(fèi)用的高低和利潤(rùn)的大??！大多數(shù)經(jīng)典排序文獻(xiàn)所考慮的工件僅屬于一個(gè)代理(客戶).而在實(shí)際問(wèn)題中，被加工的工件往往屬于不同的代理.例如，一個(gè)企業(yè)或生產(chǎn)廠家，需要同時(shí)面對(duì)不同的客戶，并且這些客戶要競(jìng)爭(zhēng)著使用共同的資源，假如兩個(gè)客戶的訂單需要在同一時(shí)間、同一臺(tái)機(jī)器或者同一個(gè)流水線上加工，決策者如何調(diào)度才能使利潤(rùn)最大化，并且讓不同的客戶都達(dá)到滿意.因此，為了滿足不同代理的需要，決策者需要在多個(gè)代理的利益之間進(jìn)行權(quán)衡.這就產(chǎn)生了多代理排序.同時(shí)，在多數(shù)排序文獻(xiàn)中，都是基于以下假設(shè)：所有的工件都必須在機(jī)器上加工，不允許拒絕任何工件.然而，在現(xiàn)實(shí)中這些假設(shè)并非總是成立的.由于資源的有限性，生產(chǎn)決策者經(jīng)常會(huì)拒絕一些耗費(fèi)資源且利潤(rùn)較低的工件.如果一個(gè)工件被拒絕，有時(shí)候基于信用或其他因素，商家不得不對(duì)所拒絕的客戶支付一定的賠償，稱這種賠償為拒絕懲罰或拒絕費(fèi)用，這就出現(xiàn)了帶有拒絕費(fèi)用的排序(調(diào)度)問(wèn)題.本文研究的就是這樣的一個(gè)問(wèn)題.

Agnetis 等人[1]首先研究了多代理排序問(wèn)題，在異順序作業(yè)環(huán)境下，他們主要研究了一般擬凸函數(shù)的Pareto 最優(yōu)問(wèn)題.此外，還介紹了所研究問(wèn)題在不同領(lǐng)域的實(shí)際應(yīng)用.后來(lái)，Baker 和Smith[2]對(duì)具有兩個(gè)代理的單機(jī)排序問(wèn)題，考慮了工件的目標(biāo)函數(shù)有最大完工時(shí)間，最大延遲等.Agnetis 等人[3]也考慮兩個(gè)代理排序問(wèn)題，目標(biāo)函數(shù)是工件完工時(shí)間的非減函數(shù)，并且工件不允許中斷搶先.Agnetis 等人[4]把問(wèn)題推廣到兩個(gè)以上代理.Yuan 等人[5]更新了文獻(xiàn)[2]的一些結(jié)果并給出相應(yīng)的最優(yōu)算法.后來(lái)，Cheng 等人[6,7]中也考慮了單機(jī)多代理排序問(wèn)題.Ng 等人[8]研究了兩個(gè)代理的排序問(wèn)題.另外，Leung 等人[9]推廣了文獻(xiàn)[3]的結(jié)果.建立了兩個(gè)代理的排序問(wèn)題與重新排序和約束排序之間的關(guān)系.Nong 等人[10]研究了兩個(gè)代理排序問(wèn)題的近似算法.Feng 等人[11]研究了多個(gè)代理的Pareto 最優(yōu)問(wèn)題.Feng 等人[12]研究了帶有拒絕費(fèi)用的單機(jī)多代理排序問(wèn)題.Feng 等人[13]研究了機(jī)器帶有禁用區(qū)間的多代理排序問(wèn)題.有關(guān)這方面的更多結(jié)果可參見(jiàn)文獻(xiàn)[14].

在本文中，通過(guò)對(duì)問(wèn)題的分析，將所研究的問(wèn)題轉(zhuǎn)化為一個(gè)具有可用區(qū)間的工件可拒絕排序問(wèn)題.有關(guān)這方面的研究結(jié)果，在國(guó)內(nèi)外文獻(xiàn)中還不多.Zhong 等人[33]研究了機(jī)器具有禁用區(qū)間的工件可拒絕排序問(wèn)題.他們考慮了模型的近似性和重要的特殊情形.Li 和Chen[34]研究了一臺(tái)機(jī)器上具有退化維修活動(dòng)的工件可拒絕排序問(wèn)題，目標(biāo)是確定維修活動(dòng)的位置和接收工件的序列，使得接收工件的排序費(fèi)用與拒絕懲罰之和達(dá)到最小.Zou 和Yuan[35]也考慮了機(jī)器具有維修活動(dòng)的工件可拒絕排序問(wèn)題，并對(duì)所研究問(wèn)題給出一系列的結(jié)果.

為了敘述方便，引入一些簡(jiǎn)單描述排序問(wèn)題的符號(hào).本文所涉及的相關(guān)記號(hào)如下：

2 全多項(xiàng)式時(shí)間近似方案

首先，給出全多項(xiàng)式時(shí)間近似方案的定義.

定義1 給定一個(gè)帶有非負(fù)權(quán)重的優(yōu)化問(wèn)題P，如果存在一系列的多項(xiàng)式時(shí)間算法A?，使得對(duì)問(wèn)題P的任意一個(gè)實(shí)例I和每一個(gè)固定的? ＞0, A?都是優(yōu)化問(wèn)題P的一個(gè)(1+?)-因子的近似算法，并且當(dāng)?是一個(gè)常數(shù)時(shí)，算法的運(yùn)行時(shí)間是輸入的一個(gè)多項(xiàng)式，那么稱A?為P的一個(gè)多項(xiàng)式時(shí)間近似方案，簡(jiǎn)記為PTAS(Polynomial Time Approximation Scheme).特別地，當(dāng)算法的運(yùn)行時(shí)間也是關(guān)于1/?的一個(gè)輸入多項(xiàng)式時(shí)，我們稱A?是該問(wèn)題的一個(gè)全多項(xiàng)式時(shí)間近似方案，簡(jiǎn)記為FPTAS.

存在一個(gè)最優(yōu)的排序滿足下列性質(zhì)：

性質(zhì)1 被接收的A-工件以任意序列連續(xù)加工.

性質(zhì)2B-工件按照最早工期優(yōu)先加工規(guī)則(簡(jiǎn)稱EDD 規(guī)則)加工，并且B-工件被劃分成兩部分(如果存在)，每一部分仍然按照EDD 規(guī)則加工.其中一部分連續(xù)地在序列的開始加工(如果存在)，剩余的B-工件則在序列的最后連續(xù)加工.

記

對(duì)于本文所討論的問(wèn)題，在文獻(xiàn)[12]中，已經(jīng)證明該問(wèn)題是一般意義下NP-困難的，并且給出了一個(gè)動(dòng)態(tài)規(guī)劃算法和一個(gè)2-近似算法，由于本文算法與這兩個(gè)算法關(guān)系密切，因此，下面列出這兩個(gè)算法.

動(dòng)態(tài)規(guī)劃算法[12]

如果JA=?，停止.否則，令i:=i+1，轉(zhuǎn)步驟2；

步驟5 在步驟3 得到的排序中選擇具有最小目標(biāo)值的排序.

則定理成立.

3 結(jié)論

本文研究了排序問(wèn)題(1)，但這只是代理B的工件全部被接收且是單機(jī)上的情形，我們希望能得出代理B的工件如果部分被拒絕，或者平行機(jī)情形下的一些結(jié)果，這還有待于進(jìn)一步的研究.