謝　謝,吳星瑤,李曉麗,孔祥玉

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

2.浙江大學計算機科學與技術(shù)學院,浙江杭州310058;3.吉林省雙遼市職業(yè)高級中學,吉林雙遼136400)

?

帶有不可用區(qū)間、工件可拒絕的單機生產(chǎn)與運輸協(xié)調(diào)調(diào)度問題

謝謝1,吳星瑤2,李曉麗3,孔祥玉1

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

2.浙江大學計算機科學與技術(shù)學院,浙江杭州310058;3.吉林省雙遼市職業(yè)高級中學,吉林雙遼136400)

摘要:從生產(chǎn)實際提煉出一類單機生產(chǎn)與運輸協(xié)調(diào)調(diào)度問題,即當工件在機器加工結(jié)束后由一輛容量受限的車運到配送中心.與經(jīng)典調(diào)度問題不同的是,加工機器帶有不可用區(qū)間,且可以拒絕加工某些工件,但拒絕產(chǎn)生懲罰.目標函數(shù)是最后一批完工工件到達配送中心的時間與拒絕工件的懲罰和.由于該問題是NP-難的,提出了一個多項式時間內(nèi)可解的啟發(fā)式算法,并證明該算法的最壞性能比為6.

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

傳統(tǒng)的生產(chǎn)調(diào)度和運輸調(diào)度是分開研究的,通常都是將生產(chǎn)放在首要位置而運輸放在一個從屬的地位,即先安排生產(chǎn)調(diào)度,然后再相應進行運輸物流調(diào)度.然而在實際生產(chǎn)中,由于運輸工具數(shù)量和能力的限制,而使工序之間物料的傳遞受到了限制,在不考慮運輸情況的生產(chǎn)調(diào)度即使是最優(yōu)調(diào)度也難以有效的執(zhí)行.所以將生產(chǎn)調(diào)度和運輸物流調(diào)度協(xié)調(diào)進行研究,有助于提高運輸工具的利用率,使得生產(chǎn)與運輸之間的時間銜接更加精確,從而有效地降低生產(chǎn)和運輸?shù)奈锪骺傎M用.此外,生產(chǎn)調(diào)度問題在過去的幾十年中,大多都是假設(shè)機器可以連續(xù)運作,同時所有工件都必須接受加工.然而,由于生產(chǎn)過程的突發(fā)等非確定性因素,往往導致機器不能連續(xù)運作.同時生產(chǎn)商考慮到企業(yè)的現(xiàn)有資源往往會將一些工件采用外包的方式而拒絕加工,外包的同時要支付一定的外包費用.因此,本文從生產(chǎn)實際提煉出一類單機生產(chǎn)與運輸協(xié)調(diào)調(diào)度問題,生產(chǎn)階段有一臺加工機器,機器帶有不可用區(qū)間、工件加工可以被拒絕,但拒絕產(chǎn)生懲罰.當工件加工完成后被運輸階段的一臺車運往指定的配送中心,該車輛每次最多可裝載K個工件.目標函數(shù)為最小化最后一批完工工件到達配送中心的時間與拒絕工件懲罰和.

有關(guān)生產(chǎn)與運輸協(xié)調(diào)調(diào)度問題首次由Hall和Potts[1]提出,其中運輸?shù)姆绞娇梢允侵苯拥倪\輸方式或考慮路徑優(yōu)化的運輸方式,同時運輸階段考慮了原材料的供給與產(chǎn)成品的配送.在Hall和Potts的基礎(chǔ)上,Chang和Lee[2]考慮了加工后的工件具有不同的物理大小,所以在運輸?shù)倪^程將考慮裝箱問題,并且假設(shè)運輸?shù)哪康牡氐牡乩砦恢貌煌?針對此類問題他們提出一個啟發(fā)式算法并給出最壞性能分析.He等[3]考慮了單機生產(chǎn)與運輸協(xié)調(diào)調(diào)度問題,且運輸過程僅由一輛車輛完成,目標函數(shù)是最小化工件最大完工時間,即最后一個加工完成的工件到達客戶指定位置且車輛返回加工中心的時間,通過提出一個啟發(fā)式算法求解,并證明該算法的最壞性能為5/3.Wang和Cheng[4]考慮了生產(chǎn)與運輸協(xié)調(diào)調(diào)度問題,在生產(chǎn)環(huán)節(jié)機器帶有不可用區(qū)間,且車輛的最大容量為k個工件,目標函數(shù)是最大完工時間,這里最大完工時間是指最后一批加工完成的工件到達配送中心的時間,首先證明此類問題為NP-難的,然后提出啟發(fā)式算法求解并證明最壞性能分析.

工件可拒絕的調(diào)度問題首次被Bartal等[5]提出,目標函數(shù)是最小化加工工件的最大時間表長與拒絕工件懲罰和,采用設(shè)計全多項式時間近似方案(FPTAS)求解.后來,Zhang等[6]考慮了工件可拒絕的單機調(diào)度問題,且每個工件帶有不同的釋放時間,目標函數(shù)是最小化加工工件的最大完工時間與拒絕工件懲罰和,采用啟發(fā)式算法求解,并證明該算法的最壞性能為2,為了使得問題可以在多項式時間內(nèi)求得近似解,最后設(shè)計一個全多項式時間近似方案(FPTAS),此方案的運算時間是O(n3/ε).

機器帶有不可用區(qū)間的調(diào)度問題首次由Adiri等[7]提出,分別針對具有確定的不可用區(qū)間和隨機性的不可用區(qū)間兩種情況進行分析,目標函數(shù)是最小化工件的總完工時間和,首先證明此類問題為NP-難的,同時證明應用經(jīng)典的SPT算法求解的最壞性能為2/7.后來,Kacem和Mahjoub[8]考慮了帶有不可用區(qū)間的單機調(diào)度問題,目標函數(shù)是工件的總完工時間和,嘗試設(shè)計一個全多項式時間近似方案(FPTAS)求解,使得問題可以在多項式時間內(nèi)求解.Kacem和Kellerer[9]考慮了帶有不可用區(qū)間的單機調(diào)度問題,且每個工件都有不同的釋放時間,考慮到問題的復雜性,采用啟發(fā)式算法求解,并證明該算法的最壞性能為2.由此看出,大多數(shù)學者針對帶有不可用區(qū)間或工件可拒絕的調(diào)度問題的研究,很少有人將不可用區(qū)間工件可拒絕兩種約束同時考慮.

結(jié)合以上文獻可以看出,大多數(shù)學者僅考慮運輸階段的各種限制,很少考慮生產(chǎn)階段的約束,或者僅考慮生產(chǎn)階段的約束而沒有將運輸一起考慮,如謝等[10].因此,本文考慮一類帶有不可用區(qū)間、工件可拒絕的生產(chǎn)與運輸協(xié)調(diào)調(diào)度問題,針對該問題的復雜性,提出了多項式時間內(nèi)求解問題的啟發(fā)式算法,并進一步證明了該算法的最壞性能比為6.

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

問題描述如下:給定n個工件的集合N={J1,J2,…,Jn}.要求接收加工的工件首先在機器上加工,加工完成后運往配送中心.在工件的生產(chǎn)階段存在兩種約束:①生產(chǎn)商考慮到自己的利益,在安排生產(chǎn)之前可能會拒絕某些工件的加工,但相應需要支付一定懲罰;②機器在加工的過程中由于定期維護帶來一段時間不可用.不失一般性本章涉及的所有參數(shù)都為正整數(shù),各參數(shù)如下:

pj為工件Jj的加工時間;

wj為工件Jj的拒絕懲罰值;

[T1,T2]為機器由于維修、保養(yǎng)帶來的一段作業(yè)時間受限區(qū)間;

Δ=T2-T1為機器受限時間間隔;

σ為工件集N的一個可行排序即工件的加工順序;

Bk為第k次配送批次;

α(Bk)為配送批次Bk的最后一個工件的加工完成時間;

C(Bk)為車輛返回加工中心準備運輸Bk的時間;

q1和q2有n=Kq1+q2,且q1和q2為整數(shù),0≤q2≤K;

φ=[B1,B2,…,Bm],運輸方案q1+1≤m≤n;

(σ,φ)為生產(chǎn)與運輸調(diào)度的可行方案;

C(σ,φ)為(σ,φ)的最后一批工件運送到配送中心且車輛返回加工中心的最大完工時間;

C*(σ,φ)為最優(yōu)方案的最大完工時間;

2　啟發(fā)式算法及最壞性能分析

為了較快的得到較好的近似解,給出如下滿足最優(yōu)解的性質(zhì)以加快解的搜索過程:

①工件加工盡可能早,且加工無空閑;②先加工完的工件先運輸;③當有K個工件加工完時車輛的運輸不能空閑必須立即運往配送中心.

(2) 對于一個最優(yōu)調(diào)度方案,滿批運輸方案一定最優(yōu),即q1+1=m且|B1|=q2,|B2|=…=|Bq+1|=K.

(3) 對于已經(jīng)分批的工件,早加工完成的配送批先運輸.

根據(jù)以上性質(zhì),啟發(fā)式算法H的具體步驟如下:

第1步按照SPT規(guī)則即按pj不減的順序?qū)ぜM行加工,并將其可行排序記為σ1.

第5步按照性質(zhì)5、6對第一步與第二步的工件確定運輸方案,將分別產(chǎn)生兩個運輸方案φ1,φ2.

由于第1步運算的時間為O(nlogn),且為該算法的主要步驟,因此,該算法的運算時間為O(nlogn).

又因為wj≤pj,所以有

因此,所提出的啟發(fā)式算法的最壞性能比為6.

3　結(jié)　　論

參考文獻:

[1]HallNG,PottsCN.SupplyChainScheduling:BatchingandDelivery[J].OperationResearch, 2003,51(4):566-583.

[2]ChangYC,LeeCY.MachineSchedulingwithJobDeliveryCoordination[J].EuropeanJournalOperationResearch, 2004,158(2):470-487.

[3]HeYong,ZhongWeiya,GuHuikun.ImprovedAlgorithmsforTwoSingleMachineSchedulingProblems[J].TheoreticalComputerScience, 2006,363(3):257-265.

[4]WangXL,ChengTCE.MachineSchedulingwithanAvailabilityConstraintandJobDeliveryCoordination[J].NavalResearchLogistics, 2007,54(1):11-20.

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

[6]ZhangLQ,LuLF,YuanJJ.SingleMachineSchedulingwithReleaseDatesandRejection[J].EuropeanJournalofOperationResearch, 2009,198(3):975-978.

[7]AdiriI,BrunoJ,FrostigE,etal.SingleMachineFlow-TimeSchedulingwithaSingleBreakdown[J].ActaInformatica, 1989,26(7):679-696.

[8]KacemI,MahjoubAR.FullyPolynomialTimeApproximationSchemefortheWeightedFlow-TimeMinimizationonaSingleMachinewithaFixedNon-AvailabilityInterval[J].ComputersandIndustrialEngineering, 2009,56(4):1708-1712.

[9]KacemI,KellererH.FastApproximationAlgorithmstoMinimizeaSpecialWeightedFlow-TimeCriteriononaSingleMachinewithaNon-AvailabilityIntervalandReleaseDates[J].JournalofScheduling, 2011,14(3):257-265.

[10]謝謝,李曉麗,孔祥玉. 帶有不可用區(qū)間、工件可拒絕的單機調(diào)度問題[J]. 沈陽大學學報:自然科學版, 2015,27(1):34-39.

【責任編輯:胡天慧】

(XieXie,LiXiaoli,KongXiangyu.SingleMachineSchedulingProblemwithUnavailabilityIntervalandRejection[J].JournalofShenyangUniversity:NaturalScienceEdition, 2015,27(1):34-39.)

ProductionandTransportationCoordinatedSingleMachineSchedulingProblemswithUnavailabilityIntervalandRejection

Xie Xie1,WuXingyao2,LiXiaoli3,KongXiangyu1

(1.KeyLaboratoryofManufacturingIndustrialandIntegratedAutomation,ShenyangUniversity,Shenyang110044,China; 2.CollegeofComputerScienceandTechnology,ZhejiangUniversity,Hangzhou310058,China; 2.ShuangliaoVocationalHighSchoolofJilinProvince,Shuangliao136400,China)

Abstract:A production and transportation coordinated single machine scheduling problem is abstracted from practical production, which is, the workpieces can be transported to the distribution center by a capacity constrained vehicle after machining. Different from the classical scheduling problem, the processing machine has unavailable interval and rejection, and can refuse to produce punishment. The objective function is the sum of the arrival time of last delivery batch to the distribution center and penalties of the rejected jobs. For the problem is NP-hard, a polynomial time solvable heuristic algorithm is proposed, and further demonstrate the worst case bound 6. It is proved that the algorithm’s worst-case performance ratio is 6.

Key words:scheduling; unavailable interval; rejection job; heuristic algorithm

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

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

收稿日期:2014-12-23

文章編號:2095-5456(2015)03-0222-04

中圖分類號:TP30

文獻標志碼:A