工件可拒絕的兩個代理排序問題的全多項式時間近似方案

馮 琪, 楊麗華, 狄 帥

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

1 引言

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

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

在本文中，通過對問題的分析，將所研究的問題轉化為一個具有可用區間的工件可拒絕排序問題.有關這方面的研究結果，在國內外文獻中還不多.Zhong 等人[33]研究了機器具有禁用區間的工件可拒絕排序問題.他們考慮了模型的近似性和重要的特殊情形.Li 和Chen[34]研究了一臺機器上具有退化維修活動的工件可拒絕排序問題，目標是確定維修活動的位置和接收工件的序列，使得接收工件的排序費用與拒絕懲罰之和達到最小.Zou 和Yuan[35]也考慮了機器具有維修活動的工件可拒絕排序問題，并對所研究問題給出一系列的結果.

為了敘述方便，引入一些簡單描述排序問題的符號.本文所涉及的相關記號如下：

2 全多項式時間近似方案

首先，給出全多項式時間近似方案的定義.

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

存在一個最優的排序滿足下列性質：

性質1 被接收的A-工件以任意序列連續加工.

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

記

對于本文所討論的問題，在文獻[12]中，已經證明該問題是一般意義下NP-困難的，并且給出了一個動態規劃算法和一個2-近似算法，由于本文算法與這兩個算法關系密切，因此，下面列出這兩個算法.

動態規劃算法[12]

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

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

則定理成立.

3 結論

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