陳 東，趙傳立

（沈陽師范大學(xué) 數(shù)學(xué)與系統(tǒng)科學(xué)學(xué)院，沈陽 110034）

0 引 言

近年來有關(guān)交貨期的排序問題已廣為關(guān)注，交貨期問題是指：若某個工件在交貨期內(nèi)完工，則不產(chǎn)生懲罰費(fèi)用，如果工件在窗口之前或之后完工則會產(chǎn)生提前或延誤的費(fèi)用。Mosheiov等［1］研究了帶有相同交貨期的單機(jī)排序問題，目標(biāo)函數(shù)為極小化最大完工時間。Mor等［2］提出了帶有維修活動且具有相同大小交貨期的單機(jī)排序問題，目標(biāo)函數(shù)是極小化加權(quán)流時間的總費(fèi)用。Yin等［3］研究了帶有相同交貨期和分批交貨期成本的單機(jī)排序問題，目標(biāo)是通過確定最優(yōu)排序，確定工件的交貨期、交貨期的開始時間和大小，從而極小化總的費(fèi)用和加權(quán)誤工數(shù)等。

工件可拒絕是指：在所有到達(dá)的工件中，某些工件由于外界或自身的原因可能被拒絕加工，但也會產(chǎn)生費(fèi)用，費(fèi)用由拒絕工件集中對應(yīng)工件的單位費(fèi)用求出。Shabtay等［4］研究了帶有位置權(quán)函數(shù)和工件可拒絕的單機(jī)排序問題，目標(biāo)函數(shù)是極小化接受工件集和拒絕工件集產(chǎn)生的總費(fèi)用。Zhang等［5］研究了工件可拒絕的單機(jī)排序問題，目標(biāo)函數(shù)是極小化接受工件集的最大完工時間和被拒絕的工件產(chǎn)生的費(fèi)用。Zhang等［6］研究了帶有釋放時間和工件可拒絕的單機(jī)排序問題，目標(biāo)是極小化總的最大完工時間，極小化拒絕工件產(chǎn)生的總費(fèi)用。Zhang等［7］研究了工件可拒絕的、無界并行批排序問題，目標(biāo)是極小化總的完工時間和總的費(fèi)用等。Cao等［8］研究了帶有拒絕的單機(jī)排序問題，目標(biāo)是極小化拒絕工件的總費(fèi)用、接受工件的最大完工時間。

另外，為了提高機(jī)器的工作效率，縮短工件的加工時間，維修活動已被廣度應(yīng)用。Yang等［9］研究了帶有松弛交貨期、學(xué)習(xí)效應(yīng)和維修活動的單機(jī)排序問題，目標(biāo)是確定最優(yōu)排序、最優(yōu)維修位置、極小化總的費(fèi)用等。Mosheiov等［10］研究了帶有退化維修的單機(jī)排序問題，目標(biāo)是極小化最大完工時間和總的費(fèi)用等。Yang［11］研究了帶有學(xué)習(xí)效應(yīng)和多維修活動的單機(jī)排序問題，目標(biāo)是確定最優(yōu)維修位置和最優(yōu)維修頻率等。Yang等［12］研究了維修活動是位置線性函數(shù)的單機(jī)排序問題，目標(biāo)是通過確定最優(yōu)位置，極小化總的完工時間等。張麗華等［13］研究了一類單機(jī)維護(hù)調(diào)度問題研究。崔苗苗等［14］針對處理機(jī)具有一個不可用區(qū)間情況進(jìn)行了研究。

本文考慮帶有交貨期、維修活動和工件可拒絕的單機(jī)排序問題。我們給出了一些最優(yōu)解的討論，證明了該問題是多項(xiàng)式時間可解的。

1 問題描述

接受工件的總費(fèi)用包括提前、延誤、交貨期的開始時間和交貨期大小產(chǎn)生的費(fèi)用。設(shè)α≥0，β≥0，γ≥0和δ≥0分別表示提前完工時間、延誤完工時間、交貨期的開始時間和交貨期大小的單位費(fèi)用。

因此接受工件集的費(fèi)用可以表示為：

拒絕工件集的費(fèi)用可以表示為：

總的費(fèi)用為：于是，用三參數(shù)法Graham等［15］可以表示如下：

2 先前的結(jié)論

Mosheiov［1］給出的一些性質(zhì)可以應(yīng)用到本文中的接受工件集，設(shè)接受工件集A中有h個工件，對于任意給定的排序A：σ＝（J1，J2，…，Jh），有如下性質(zhì)：

性質(zhì)1 如果C［j］＜，則C［j－1］＜。

性質(zhì)2 如果C［j］＞，則C［j－1］＞。

性質(zhì)3 在最優(yōu)排序σ＊＝（J［1］，J［2］，…，J［n］）中，存在某個k和l，使得

其中，k＊，l＊為性質(zhì)3中k，l的最優(yōu)值。

性質(zhì)5 對于任意給定的排序，若是最優(yōu)排序，一定滿足以下一種：

1）無維修活動；

2）維修活動從t＝0時刻開始；

3）維修活動的開始時間等于排在第i個位置的工件的完工時間，其中i≥l，即：維修活動一定排在某一延誤工件之前。

3 最優(yōu)排序

情況1 假設(shè)所有的工件都被接受，即h＝n，A＝（J［1］，J［2］，…，J［n］），此種情況已被文獻(xiàn)［1］提到。

情況2 假設(shè)部分工件被接受，即1≤h＜n，A＝（J［1］，J［2］，…，J［h］），此時總的費(fèi)用為：

現(xiàn)在，考慮維修活動的后2種情況：

2）維修活動在t＝0時刻開始

工件J［j］的實(shí)際加工時間為θ［j］p［j］，j＝1，2，…，h。

表示在排序σ中排在第j個位置上的工件的位置權(quán)。

可以將式子（4）化為如下指派問題：

得到式（3）的最優(yōu)解。

定理1 若維修活動從t＝0時刻開始，問題

可以化為指派問題（6），在O（n4）時間內(nèi)可解。

證明 對于任意給定的h，若維修活動從t＝0時刻開始，問題

在O（n3）時間內(nèi)可解，因?yàn)?≤h＜n，所以該問題可以化為指派問題（6），在O（n4）時間內(nèi)可解。證畢。

3）維修活動的開始時間等于工件J［i］的完工時間

其中，w［j］可應(yīng)用式（5）求出。

可以將式（7）化為如下指派問題：

對于任意給定的h和i，以上指派問題在O（n3）時間內(nèi)可解。由于i，h＝1，2，…，n，多次運(yùn)用以上指派算法，求得的最小值便是最優(yōu)值。

可以化為指派問題（8），在O（n5）時間內(nèi)可解。

證明 對于任意給定的h和i，維修活動的開始時間等于工件J［i］的完工時間，其中l(wèi)≤i≤h，問題1

4 結(jié) 語

本文討論了帶有交貨期、維修活動和工件可拒絕的單機(jī)排序問題。將所有工件分為2個集合：分別是接受工件集和拒絕工件集。為了減少工件的加工時間，對機(jī)器進(jìn)行一次擁有固定時間的維修活動。目標(biāo)函數(shù)是確定被接受工件的最優(yōu)排序，極小化接受工件和拒絕工件的總費(fèi)用。證明了這個問題在多項(xiàng)式時間內(nèi)可以求解。對于工件可拒絕問題的其他類型目標(biāo)函數(shù)，以及其他類型的交貨期問題，還有待進(jìn)一步討論。

［1］MOSHEIOV G，SARIG A.Scheduling with a common due－window：Polynomially solvable cases［J］.Inform Sciences，2010，180（8）：1492－1505.

［2］MOR B，MOSHEIOV G.Scheduling a maintenance activity and due－window assignment based on common flow allowance［J］.Int J Prod Econ，2012，135（1）：220－230.

［3］YIN Yunqiang，CHENG T C E，WANG Jiayin，et al.Single machine common due window assignment and scheduling to minimize the total cost［J］.Discrete Optim，2013，10（1）：42－53.

［4］SHABTAY D，GASPAR N，YEDIDSION L.A bicriteria approach to scheduling a single machine with job rejection and positional penalties［J］.J Comb Opt，2012，23（4）：395－424.

［5］LU Lingfa，ZHANG Liqi，NG C T.Optimal algorithms for single machine scheduling with rejection to minimize the makespan［J］.Int J Prod Econ，2011，130（2）：153－158.

［6］ZHANG Liqi，LU Lingfa，YUAN Jinjiang.Single machine scheduling with release dates and rejection［J］.Eur J Oper Res，2009，198（3）：975－978.

［7］ZHANG Liqi，LU Lingfa，NG C T.The unbounded parallel－batch scheduling with rejection［J］.J Oper Res Soc，2012，63（3）：293－298.

［8］CAO Zhigang，ZHANG Yuzhong.Scheduling with rejection and non－identical job arrivals［J］.J Syst Sci Complex，2007，20（4）：529－535.

［9］YANG Suhjenq，HSU Choujung，YANG Darli.Single－machine scheduling and slack due－date assignment with aging effect and deteriorating maintenance［J］.Optim Lett，2012，6（8）：1862－1873.

［10］MOSHEIOV G，SIDNEY J B.Scheduling a deteriorating maintenance activity on a single machine［J］.J Oper Res Soc，2010，61（5）：882－887.

［11］YANG Suhjenq.Single－machine scheduling problems simultaneously with deterioration and learning effects under deteriorating multi－maintenance activities consideration［J］.Comput Ind Eng，2012，62（1）：271－275.

［12］YANG Suhjenq，YANG Darli.Minimizing the makespan on single－machine scheduling with aging effect and variable maintenance activities［J］.Int J Manag Sci，2010，38（6）：528－533.

［13］張麗華，涂菶生.一類單機(jī)維護(hù)調(diào)度問題研究［J］.系統(tǒng)工程，2004，11（22）：102－105.

［14］崔苗苗，趙玉芳，王松麗.機(jī)器具有可用性限制的加權(quán)總完工時間問題［J］.沈陽師范大學(xué)學(xué)報：自然科學(xué)版，2012，30（2）：157－163.

［15］GRAHAM R L，LAWLER E L，LENSTRA J K，et al.Optimization and approximation in deterministic sequencing and scheduling：a survey［J］.Ann Discrete Math，1979，5：287－326.