帶有不可用區(qū)間、工件可拒絕的單機(jī)調(diào)度問題

謝　謝, 李曉麗, 孔祥玉

(1. 沈陽大學(xué) 裝備制造綜合自動化重點實驗室, 遼寧 沈陽　110044;

2. 雙遼市職業(yè)高級中學(xué), 吉林 雙遼　136400)

?

帶有不可用區(qū)間、工件可拒絕的單機(jī)調(diào)度問題

謝謝1, 李曉麗2, 孔祥玉1

(1. 沈陽大學(xué) 裝備制造綜合自動化重點實驗室, 遼寧 沈陽110044;

2. 雙遼市職業(yè)高級中學(xué), 吉林 雙遼136400)

摘要:從企業(yè)生產(chǎn)經(jīng)常發(fā)生的一些實際問題中提煉出一類帶有不可用區(qū)間、工件可拒絕的單機(jī)調(diào)度問題.目標(biāo)函數(shù)是最小化加工工件的總完工時間與拒絕工件的懲罰和.對于這個已證明為NP難的問題提出一個動態(tài)規(guī)劃算法最優(yōu)求解小規(guī)模問題,為求解大規(guī)模問題,改進(jìn)了已有最壞性能為4的啟發(fā)式算法,并進(jìn)一步證明了該算法的最壞性能為(k為算法的迭代次數(shù)).

關(guān)鍵詞:調(diào)度; 不可用區(qū)間; 拒絕工件; 動態(tài)規(guī)劃; 啟發(fā)式算法

對于大多數(shù)的經(jīng)典調(diào)度模型,一些研究人員通常假設(shè)所有的工件必須接受加工,且加工機(jī)器不可以中斷.然而在實際生產(chǎn)過程中,生產(chǎn)商為了獲得更多的利潤,往往會考慮拒絕一些加工時間較長且懲罰相對較小的工件加工.同時在生產(chǎn)企業(yè)加工過程中由于機(jī)器加工中斷的現(xiàn)象頻頻發(fā)生,迫使機(jī)器在一段時間內(nèi)不能加工任何工件,為了減少機(jī)器停產(chǎn)給企業(yè)帶來的損失,帶有不可用區(qū)間的調(diào)度問題也引起了管理者的關(guān)注.因此,本文同時考慮帶有不可用區(qū)間、工件加工可拒絕的單機(jī)調(diào)度問題,目標(biāo)函數(shù)是最小化加工工件的總完工時間與拒絕工件的懲罰和.

1研究背景

工件可拒絕的調(diào)度問題首次被Bartal等[1]提出,目標(biāo)函數(shù)是最小化加工工件的最大時間表長與拒絕工件懲罰和,考慮了在線與離線兩種情況,分別提出在線算法與全多項式時間近似方案(FPTAS)求解.此類問題被提出后引起了大量研究人員的關(guān)注,針對不同的加工環(huán)境,對工件可拒絕的調(diào)度問題做出了研究.Zhang等[2]考慮了帶有到達(dá)時間與工件可拒絕的單機(jī)調(diào)度問題,目標(biāo)函數(shù)是最小化加工工件的最大完工時間和拒絕工件懲罰和,提出求解該問題的2-因子算法,并給出求解最優(yōu)解的兩個動態(tài)規(guī)劃算法,通過修改動態(tài)規(guī)劃算法得到全多項式時間近似方案(FPTAS),此方案的運算時間是O(n3/ε).Dosa和He[3]考慮了帶有機(jī)器花費且工件可拒絕的調(diào)度問題,且假設(shè)在調(diào)度模型中,一開始沒有一個確定的機(jī)器花費,只有當(dāng)購買新機(jī)器的時候這種花費才可以確定.

2問題參數(shù)及描述

一般情況下此類問題大多是NP難的,只有在特殊情況下才存在多項式時間算法.

3動態(tài)規(guī)劃算法

情況1當(dāng)工件Jj(j=2,…,n)被拒絕時,有式(1)成立:

(1)

情況2當(dāng)工件Jj(j=2, …, n)接受加工時,有以下兩種情況:

(2)

(2) 當(dāng)工件Jj在T2之后完成加工,有式(3)成立:

(3)

綜上所述有下面的動態(tài)規(guī)劃算法:

邊界條件:

(4)

遞推函數(shù):

當(dāng)j=2, …, n時,

(5)

最優(yōu)值:

問題的最優(yōu)值為

算例如下:工件個數(shù)n=4,不可用區(qū)間為[T1=2,T2=3],各工件在機(jī)器上的加工時間與懲罰值見表1,目標(biāo)函數(shù)是最小化接受工件的總完工時間與拒絕工件懲罰和.

表1　各工件的加工時間和懲罰值

表2　重新標(biāo)號后各工件的加工時間和懲罰值

按照工件個數(shù)劃分為四個階段,k=1,2,3,4.

(1) 第一次迭代即當(dāng)k=1時.首先考慮工件J1是接受加工還是拒絕加工,因為p1=1

(6)

所以工件J1接受加工.

考慮工件J2是接受加工還是拒絕加工,因為p2=2=T1=2,若接受加工則在T1前完工.有式(7)成立:

(7)

所以工件J2接受加工.

考慮工件J3是接受加工還是拒絕加工,因為p3=2=T1=2,工件J3在T2后完工,有式(8)成立:

(8)

所以工件J3拒絕加工.

考慮工件J4是接受加工還是拒絕加工,因為p4=3>T1=2,若J4接受加工將在T2前完工.有式(9)成立:

(9)

所以工件J4拒絕加工.

(2) 第二次迭代即當(dāng)k=2時.在前一階段工件J1接受加工的情況下,考慮剩余三個工件是接受加工還是拒絕加工.有式(10)成立:

(10)

由此可得工件J2拒絕加工,工件J3拒絕加工,工件J4接受加工.

根據(jù)以上分析過程,依次考慮當(dāng)工件J2接受加工與工件J3拒絕加工,以及工件J4拒絕加工時其余工件的加工情況,當(dāng)J2接受加工時,其余工件的加工情況為:工件J1拒絕加工目標(biāo)值為4,工件J3拒絕加工目標(biāo)值為3,工件J4拒絕加工目標(biāo)值為4;當(dāng)工件J3拒絕加工時,其余工件的加工情況為:工件J1接受加工且目標(biāo)值是2,工件J2接受加工目標(biāo)值為3,工件J4拒絕加工且目標(biāo)值為2;當(dāng)J4拒絕加工時,其余工件的加工情況為:工件J1接受加工且目標(biāo)值為3,工件J2接受加工其目標(biāo)值為4,工件J3拒絕加工其目標(biāo)值為3.

(3) 第三次迭代即當(dāng)k=3時.在第一階段接受工件J1且第二階段拒絕工件J2時,考慮工件J3與工件J4的加工情況,有式(11)成立:

(11)

所以拒絕工件J3目標(biāo)值為9,接受工件J4目標(biāo)值為7.

依據(jù)上述分析過程,當(dāng)?shù)谝浑A段接受工件J1且第二階段拒絕工件J3時,在第三階段應(yīng)拒絕工件J2其目標(biāo)值為5,拒絕工件J4其目標(biāo)值為4;當(dāng)?shù)诙A段拒絕工件J4,在第三階段應(yīng)拒絕工件J2其目標(biāo)值為6,拒絕工件J3其目標(biāo)值為4.

對第三階段的分析求解的主要過程如上所示,具體結(jié)果見圖1.

(4) 第四次迭代即當(dāng)k=4時.當(dāng)?shù)谝浑A段接受工件J1,第二階段拒絕工件J2,第三階段拒絕工件J3,第四階段需考慮是否加工J4,有式(12)成立:

(12)

所以拒絕工件J4加工.

圖1　數(shù)值算例的動態(tài)規(guī)劃解

4啟發(fā)式算法及其性能分析

第1步將所有的工件都按照SPT算法排序.

第2步給出一個正整數(shù)k,對所有的k,做k次交換,即交換A中的a個工件與B中的b個工件的位置得到新的工件加工順序.

引理1滿足

其中φ*(P)為問題P的最優(yōu)目標(biāo)值.

(13)

(14)

且算法H的運行時間為O(n2k+1).

5結(jié)論

本文考慮了一類帶有不可用區(qū)間、工件可拒絕的單機(jī)調(diào)度問題.基于此問題是NP難的,當(dāng)問題規(guī)模較小時采用動態(tài)規(guī)劃算法求解,當(dāng)問題規(guī)模較大時考慮問題的復(fù)雜性,提出一個啟發(fā)式算法求解問題,最后給出最壞性能分析.對此類問題的研究不僅為今后調(diào)度問題研究提供理論依據(jù),同時適應(yīng)生產(chǎn)企業(yè)的實際情況具有較高的應(yīng)用價值.未來將以本文研究為理論基礎(chǔ),進(jìn)一步考慮帶有不可用區(qū)間、拒絕工件的單機(jī)生產(chǎn)與運輸聯(lián)合調(diào)度問題.

參考文獻(xiàn):

[ 1 ]BartalY,LeonardiS,SpaccamelaAM,etal.Multi-ProcessorSchedulingwithRejection[J].SIAMJournalonDiscreteMathematics, 2000,13(1):64-78.

[ 2 ] Zhang Liqi, Lu Lingfa, Yuan Jinjiang. Single Machine Scheduling with Release dates and Rejection[J]. European Journal of Operational Research, 2009,198(3):975-978.

[ 3 ] Dósa G, He Y. Scheduling with Machine Cost and Rejection[J]. Journal of Combinatorial Optimization, 2006,12(4):337-350.

[ 4 ] Adiri I, Bruno J, Frostig E, et al. Single Machine Flow-Time Scheduling with a Single Breakdown[J]. Acta Informatica, 1989,26(7):679-696.

[ 5 ] He Yong, Zhong Weiya, Gu Huikun. Improved Algorithms for Two Single Machine Scheduling Problems[J]. Theoretical Computer Science, 2006,363(3):257-265.

[ 6 ] Kacem I, Chu Chengbin. Worst-Case Analysis of the WSPT and MWSPT Rules for Single Machine Scheduling with One Planned Setup Period[J]. European Journal of Operational Research, 2008,187(3):1080-1089.

[ 7 ] Kacem I, Mahjoub A R. Fully Polynomial Time Approximation Scheme for the Weighted Flow-Time Minimization on a Single Machine with a Fixed Non-Availability Interval[J]. Computers & Industrial Engineering, 2009,56(4):1708-1712.

[ 8 ] Kacem I, Kellerer H. Fast Approximation Algorithms to Minimize a Special Weighted Flow-Time Criterion on a Single Machine with a Non-Availability Interval and Release Dates[J]. Journal of Scheduling, 2011,14(3):257-265.

[ 9 ] 張敏嬌,羅成新. 帶有拒絕工件和機(jī)器維修區(qū)間的單機(jī)排序問題[J]. 重慶師范大學(xué)學(xué)報:自然科學(xué)版, 2012,29(6):5-19.

(Zhang Minjiao, Luo Chengxin. Single Machine Scheduling Problem with Job Rejection and Machine Unavailability Interval[J]. Journal of Chongqing Normal University: Natural Science Edition, 2012,29(6):5-19.)

[10] 謝謝,孔祥玉,鄭勇躍. 二機(jī)流水作業(yè)帶不可用區(qū)間、工件可拒絕的調(diào)度問題[J]. 沈陽大學(xué)校報:自然科學(xué)版, 2014,26(6):479-484.

(Xie Xie, Kong Xiangyu, Zheng Yongyue. Two-Machine Flow-Shop Scheduling Problem with Unavailable Interval and Rejection[J]. Journal of Shenyang University: Natural Science, 2014,26(6):479-484.)

[11] Lee C Y, Liman S D. Single Machine Flow-Time Scheduling with Scheduled Maintenance[J]. Acta Informatica, 1992,29(4):375-382.

【責(zé)任編輯: 李艷】

Single Machine Scheduling Problem with Unavailability Interval and Rejection

XieXie1,LiXiaoli2,KongXiangyu1

(1. Key Laboratory of Manufacturing Industrial and Integrated Automation, Shenyang University, Shenyang 110044, China; 2. Shuangliao Vocational High School, Shuangliao 136400, China)

Abstract:A single machine scheduling problem with unavailable interval and rejection is abstracted from practical problems happened in production enterprise, considers. The objective is to minimize the sum of the flow-time of the accepted jobs and penalties of rejected jobs. For the demonstrated NP-hard problem, a dynamic programming algorithm is proposed for solving small scale problem optimally and a numerical example is given. Further a heuristic algorithm is proposed and a proposed heuristic algorithm is improved with the worst-case ratio is 4. The worst case of the algorithm is demonstrated as(wherekis the number of the iterations).

Key words:scheduling; unavailability interval; rejection job; dynamic programming; heuristic algorithm

收稿日期:2014-11-08

中圖分類號:TP30

文獻(xiàn)標(biāo)志碼:A

作者簡介:謝謝(1981-),女,遼寧沈陽人,沈陽大學(xué)副教授,博士.

基金項目:國家自然科學(xué)基金資助項目(71201104); 遼寧省高等學(xué)校杰出青年學(xué)者成長計劃(LJQ2014133).

文章編號:2095-5456(2015)01-0034-06