馮 琪，楊麗華

（中原工學(xué)院，鄭州450007）

工業(yè)生產(chǎn)中一個(gè)帶有拒絕費(fèi)用的工件排序問(wèn)題研究

馮 琪，楊麗華

（中原工學(xué)院，鄭州450007）

在工業(yè)生產(chǎn)中，生產(chǎn)決策者為了獲得最大利潤(rùn)，可能接收一個(gè)工件，也可能拒絕一個(gè)工件．為了解決哪些工件應(yīng)該被接收，哪些工件應(yīng)該被拒絕問(wèn)題，本文研究了工業(yè)生產(chǎn)中一個(gè)帶有拒絕費(fèi)用的工件排序問(wèn)題，對(duì)該問(wèn)題設(shè)計(jì)了一個(gè)動(dòng)態(tài)規(guī)劃算法．

排序；拒絕；動(dòng)態(tài)規(guī)劃算法

所謂排序，就是在一定的約束條件下對(duì)工件和機(jī)器按時(shí)間進(jìn)行分配和安排加工次序，使一個(gè)或多個(gè)指標(biāo)達(dá)到最優(yōu)．作為運(yùn)籌學(xué)和管理學(xué)的一個(gè)重要分支，機(jī)器排序理論有著深厚的背景和廣闊的應(yīng)用前景．例如，如果我們把現(xiàn)有的資源（如人力、資金、工具等）當(dāng)成機(jī)器，把所要完成的任務(wù)當(dāng)成工件，那么其他領(lǐng)域的許多問(wèn)題都可以轉(zhuǎn)化成一個(gè)機(jī)器排序問(wèn)題．目前，關(guān)于排序理論的研究成果已經(jīng)應(yīng)用在許多不同的領(lǐng)域，包括計(jì)算機(jī)科學(xué)及工程、供應(yīng)鏈管理、物流運(yùn)輸?shù)阮I(lǐng)域．因此，從廣義上來(lái)說(shuō)，機(jī)器排序可以理解為最優(yōu)地分配有限資源以完成給定的任務(wù)．

在大多數(shù)經(jīng)典的排序文獻(xiàn)中，都是基于以下假設(shè)：所有的工件都必須在機(jī)器上加工，不允許拒絕任何工件．然而，在現(xiàn)實(shí)中這些假設(shè)并非總是成立的．由于資源的有限性，在實(shí)際中生產(chǎn)決策者經(jīng)常會(huì)拒絕一些耗費(fèi)資源且利潤(rùn)較低的工件．如果拒絕一個(gè)工件，有時(shí)候基于信用或其他因素，不得不支付一個(gè)確定的拒絕費(fèi)用．

可拒絕工件的排序問(wèn)題是一種新的排序模型．關(guān)于這方面的研究還比較少．Bartal Y等人首先考慮了帶有拒絕費(fèi)用的排序問(wèn)題，他們的目標(biāo)是把被接收工件的最大完工時(shí)間與所有被拒絕工件總的拒絕費(fèi)用之和最小化．對(duì)于在線情形，他們給出了一個(gè)在線算法，并且證明了這個(gè)在線算法有最好的競(jìng)爭(zhēng)比2．618；對(duì)于離線情形，他們給出了一個(gè)近似比為2－的近似算法和一個(gè)多項(xiàng)式時(shí)間近似方案（這里m是平行機(jī)機(jī)器數(shù)量）［1］．自此以后，帶有拒絕費(fèi)用的工件排序問(wèn)題受到越來(lái)越多的關(guān)注．對(duì)上述的工件在線排序問(wèn)題，在所有的工件加工允許被中斷的情況下，Seiden S給出了一個(gè)競(jìng)爭(zhēng)比約為2．387 4的在線算法［2］．Hoogeveen H等人考慮了允許加工中斷的工件離線排序問(wèn)題，他們證明了這個(gè)問(wèn)題是NP－困難的，并給出了一個(gè)全多項(xiàng)式時(shí)間近似方案［3］．Engles D W等人考慮了工件可拒絕的單機(jī)排序問(wèn)題，目標(biāo)是把被接收工件總的完工時(shí)間與所有被拒絕工件總的拒絕費(fèi)用之和最小化；他們證明了這個(gè)問(wèn)題是NP－困難的，并給出了一個(gè)全多項(xiàng)式時(shí)間近似方案［4］．Epstein L等人考慮了具有單位長(zhǎng)度的工件的單機(jī)在線排序問(wèn)題，目標(biāo)是把被接收工件總的完工時(shí)間與所有被拒絕工件總的拒絕費(fèi)用之和最小化，他們給出了一個(gè)競(jìng)爭(zhēng)比約為1．866的在線算法，并且證明了任何確定的在線算法的競(jìng)爭(zhēng)比至少為1．637 84［5］．Lu L F等人也對(duì)帶有拒絕費(fèi)用的工件排序問(wèn)題做了大量的研究，對(duì)不同的機(jī)器環(huán)境進(jìn)行了分析和探討，并且得出了一系列結(jié)論［6－9］．

對(duì)工業(yè)生產(chǎn)中帶有拒絕費(fèi)用的工件排序問(wèn)題，還有大量的挑戰(zhàn)性的問(wèn)題有待解決．本文研究了這一領(lǐng)域中的一個(gè)排序問(wèn)題，探討了它的計(jì)算復(fù)雜性，并且設(shè)計(jì)了一個(gè)動(dòng)態(tài)規(guī)劃算法．

1 排序問(wèn)題的描述

對(duì)本文所考慮的帶有拒絕費(fèi)用的工件排序問(wèn)題描述如下：

有1臺(tái)機(jī)器，n個(gè)待加工的工件J1，…，Jn．并且每個(gè)工件Jj有一個(gè)加工時(shí)間pj和一個(gè)拒絕費(fèi)用wj．工件Jj或者被拒絕并且支付一個(gè)確定的拒絕費(fèi)用wj，或者被接收并安排在機(jī)器上加工．目標(biāo)是使被接收工件總的完工時(shí)間與所有被拒絕工件總的拒絕費(fèi)用之和達(dá)到最?。?/p>

2 排序問(wèn)題的記號(hào)與概念

我們定義A和R分別為所有被接收工件的集合和所有被拒絕工件的集合．采用Graham P L等人提出的排序問(wèn)題的一般記號(hào)［10］，把這個(gè)問(wèn)題記為

根據(jù)1979年Graham P L等人提出的工件排序問(wèn)題的三參數(shù)表示法［10］，我們使用α｜β｜γ來(lái)表示一個(gè)排序問(wèn)題．在這里，α域表示機(jī)器的數(shù)量、類型和環(huán)境；β域表示工件的特征和約束；γ域表示要優(yōu)化的目標(biāo)．在本文中，α域、β域和γ域中的參數(shù)分別表示如下：

（1）α域：1表示單機(jī)，并且一次只能加工一個(gè)工件．

（2）β域：J1，…，Jn表示n個(gè)需要加工的工件；pj表示工件Jj的加工時(shí)間；wj表示工件Jj的拒絕費(fèi)用；reject表示工件允許被拒絕且每個(gè)被拒絕的工件要支付一個(gè)拒絕費(fèi)用wj．

（3）γ域：Cj表示工件Jj的完工時(shí)間，表示

j被接收工件總的完工時(shí)間；wj表示被拒絕工件Jj的拒絕費(fèi)用，表示被拒絕工作總的拒絕用費(fèi)；表示被接收工件總的完工時(shí)間與被拒絕工件總的拒絕費(fèi)用之和．

3 排序問(wèn)題的求解

針對(duì)所研究的排序問(wèn)題，我們將設(shè)計(jì)一個(gè)動(dòng)態(tài)規(guī)劃算法來(lái)解決．

3．1 動(dòng)態(tài)規(guī)劃算法的思想

（1）動(dòng)態(tài)規(guī)劃方法的關(guān)鍵在于正確地寫(xiě)出基本的遞推關(guān)系式和恰當(dāng)?shù)倪吔鐥l件．要做到這一點(diǎn)，必須先將問(wèn)題的過(guò)程分成幾個(gè)相互聯(lián)系的階段，恰當(dāng)?shù)剡x取狀態(tài)變量和決策變量及定義最優(yōu)值函數(shù)，從而把一個(gè)大問(wèn)題轉(zhuǎn)化成一組同類型的子問(wèn)題，然后逐個(gè)求解．即從邊界條件開(kāi)始，逐段遞推尋優(yōu)．在對(duì)每一個(gè)子問(wèn)題的求解中，均利用了它前面的子問(wèn)題的最優(yōu)化結(jié)果，依次進(jìn)行，對(duì)最后一個(gè)子問(wèn)題求解所得到的最優(yōu)解就是整個(gè)問(wèn)題的最優(yōu)解．

（2）在多階段決策過(guò)程中，動(dòng)態(tài)規(guī)劃方法是既把當(dāng)前一階段和未來(lái)各階段分開(kāi)，又把當(dāng)前效益和未來(lái)效益結(jié)合起來(lái)考慮的一種最優(yōu)化方法．因此，每階段的決策是從全局來(lái)考慮的，與單獨(dú)考慮本階段狀態(tài)得出的決策一般是不同的．

（3）在求整個(gè)問(wèn)題的最優(yōu)策略時(shí)，由于初始狀態(tài)是已知的，而每階段的決策都是該階段狀態(tài)的函數(shù)，故最優(yōu)策略所經(jīng)過(guò)的各階段狀態(tài)便可逐次變換得到，從而確定最優(yōu)路線．

3．2 動(dòng)態(tài)規(guī)劃算法

根據(jù)引理1，對(duì)工件重新標(biāo)號(hào)，使得p1≤…≤pn．下面給出一個(gè)定理，在這個(gè)定理中，工件的最優(yōu)加工次序與引理①中的工件的最優(yōu)加工次序有密切的關(guān)系

定理1：在O（n2）時(shí)間內(nèi)能得到問(wèn)題的最優(yōu)解．

對(duì)定理1證明如下：

設(shè)f（j，m）是所考慮工件為Jj，…，Jn且被拒絕工件的個(gè)數(shù)為m時(shí)所對(duì)應(yīng)的最優(yōu)目標(biāo)函數(shù)值．

現(xiàn)在，考慮工件為Jj，…，Jn且被拒絕工件的個(gè)數(shù)為m時(shí)的一個(gè)最優(yōu)排序．在這個(gè)排序中，僅僅有下面兩種可能的情形：

情形1：工件Jj被拒絕并且支付一個(gè)確定的拒絕費(fèi)用wj．

由于工件Jj被拒絕，則對(duì)于工件集Jj－1，…，Jn，所有被拒絕工件的個(gè)數(shù)為m－1，工件Jj對(duì)目標(biāo)函數(shù)的貢獻(xiàn)是wj，因此，有f（j，m）＝f（j－1，m－1）＋wj．

情形2：工件Jj被接收并安排在機(jī)器上加工．

由于工件Jj被接收，則對(duì)于工件集Jj－1，…，Jn，所有被拒絕工件的個(gè)數(shù)為m，工件Jj對(duì)目標(biāo)函數(shù)的貢獻(xiàn)是pj，因此，有f（j，m）＝f（j－1，m）＋pj．

綜合上述兩種情形，給出下面的動(dòng)態(tài)規(guī)劃算法DP．這種算法為：

（1）邊界條件：

f（1，0）＝pj，f（1，1）＝wj；且在m≠0，1時(shí)，f（1，m）＝∞．

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

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

min｛f（n，m），1≤m≤n｝

由于1≤j≤n，且1≤m≤n，至多有O（n2）個(gè)不同的狀態(tài)變量．并且每次迭代均花費(fèi)一個(gè)常數(shù)時(shí)間．因此，動(dòng)態(tài)規(guī)劃算法DP的時(shí)間復(fù)雜性為O（n2），即可以在O（n2）時(shí)間內(nèi)得出問(wèn)題的最優(yōu)解．

4 結(jié) 語(yǔ)

本文研究了工業(yè)生產(chǎn)中一個(gè)帶有拒絕費(fèi)用的排序問(wèn)題，對(duì)該問(wèn)題設(shè)計(jì)了一個(gè)動(dòng)態(tài)規(guī)劃算法，探討了它的計(jì)算復(fù)雜性．這對(duì)于幫助決策者在加工產(chǎn)品時(shí)取舍工件提供了理論依據(jù)．

［1］Bartal Y，Leonardi S，Spaccamela A M，eta l．Multiprocessor Scheduling with Rejection［J］．SIAM Journal on Discrete Mathematics，2000，13：64－78．

［2］Seiden S．Preemptive Multiprocessor Scheduling with Rejection［J］．Theoretical Computer Science，2001，262：437－458．

［3］Hoogeveen H，Skutella M，Woeginger G J．Preemptive Scheduling with Rejection［J］．Mathematics Programming，2003，94：361－374．

［4］Engels D W，Karger D R，Kolliopoulos S G，eta l．Techniques for Scheduling with Rejection［J］．Journal of Algorithms，2003，49：175－191．

［5］Epstein L，Noga J，Woeginger G J．On－line Scheduling of Unit Time Jobs with Rejection：Minimizing the Total Completion Time［J］．Operations Research Letters，2002，30：415－420．

［6］Lu L F，Zhang L Q，Yuan J J．The Unbounded Parallel Batch Machine Scheduling with Release Dates and Rejection to Minimize Makespan［J］．Theoretical Computer Science，2008，396：283－289．

［7］Lu L F，Cheng T C E，Yuan J J，eta l．Bounded Single－machine Parallel－batch Scheduling with Release Dates and Rejection［J］．Computers and Operation Research，2009，36：2748－2751．

［8］Zhang L Q，Lu L F，Yuan J J．Single Machine Scheduling with Release Dates and Rejection［J］．European Journal of Operational Research，2009，198：975－978．

［9］Zhang L Q，Lu L F，Yuan J J．Single－machine Scheduling under the Job Rejection Constraint［J］．Theoretical Computer Science，2010，411：1877－1882．

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

［11］Baker K R．Introduction to Sequencing and Scheduling［M］．New York：John Wiley ＆Sons，1979．

Study on the Scheudling Problem with Rejiction Cost in Industrial Production

FENG Qi，YANG Li－h(huán)ua
（Zhongyuan University of Technology，Zhengzhou 450007，China）

In industrial production，decision－makers either accept a job or reject a job to obtain the maximum profit．In order to solve the problem which jobs should be accepted and which jobs should be rejected，a scheduling problem with rejection cost in industrial production in this paper is researched．A dynamic programming algorithm for the problem is designed．

scheduling；rejection；dynamic programming algoriathm

O223

A

10．3969／j．issn．1671－6906．2011．05．001

1671－6906（2011）05－0001－03

2011－09－15

國(guó)家自然科學(xué)基金項(xiàng)目（10971201；61070229）

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