陳 東，趙傳立

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

0 引 言

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

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

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

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

1 問題描述

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

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

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

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

2 先前的結(jié)論

Mosheiov［1］給出的一些性質(zhì)可以應(yīng)用到本文中的接受工件集，設(shè)接受工件集A中有h個(gè)工件，對(duì)于任意給定的排序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］）中，存在某個(gè)k和l，使得

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

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

1）無維修活動(dòng)；

2）維修活動(dòng)從t＝0時(shí)刻開始；

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

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］），此時(shí)總的費(fèi)用為：

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

2）維修活動(dòng)在t＝0時(shí)刻開始

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

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

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

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

定理1 若維修活動(dòng)從t＝0時(shí)刻開始，問題

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

證明 對(duì)于任意給定的h，若維修活動(dòng)從t＝0時(shí)刻開始，問題

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

3）維修活動(dòng)的開始時(shí)間等于工件J［i］的完工時(shí)間

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

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

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

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

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

4 結(jié) 語

本文討論了帶有交貨期、維修活動(dòng)和工件可拒絕的單機(jī)排序問題。將所有工件分為2個(gè)集合：分別是接受工件集和拒絕工件集。為了減少工件的加工時(shí)間，對(duì)機(jī)器進(jìn)行一次擁有固定時(shí)間的維修活動(dòng)。目標(biāo)函數(shù)是確定被接受工件的最優(yōu)排序，極小化接受工件和拒絕工件的總費(fèi)用。證明了這個(gè)問題在多項(xiàng)式時(shí)間內(nèi)可以求解。對(duì)于工件可拒絕問題的其他類型目標(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)總完工時(shí)間問題［J］.沈陽師范大學(xué)學(xué)報(bào)：自然科學(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.