帶有退化工件和拒絕的不同類型機排序問題

胡晨晨, 趙玉芳

(沈陽師范大學 數學與系統科學學院, 沈陽 110034)

帶有退化工件和拒絕的不同類型機排序問題

胡晨晨, 趙玉芳

(沈陽師范大學 數學與系統科學學院, 沈陽 110034)

在工業生產過程中,由于一些特殊的原因,工件可以被拒絕加工但要付出相應的費用,即拒絕懲罰。為了節約處理成本,加工時間長的工件或者加工所需的費用高的工件,可以支付一定的費用來進行外加工或購買。將退化和拒絕結合起來考慮,討論帶有退化工件和拒絕的不同類型機排序問題。在這一模型中,工件的實際加工時間是其開始加工時間的線性遞增函數,其中工件的退化率只與機器有關,與工件本身無關。目標函數是極小化接受工件的排序指標與拒絕工件總懲罰之和。排序指標分別為總時間表長和總完工時間。目的是找到拒絕工件集和接受工件集,并安排接受工件的加工順序,使所求問題的目標函數值最小。通過將2個問題的目標函數轉化為指派問題,證明了他們都是多項式可解的。

排序; 不同類型機; 退化工件; 拒絕; 總完工時間

在工業生產過程中,工件的加工時間往往依賴于工件的開始加工時間。Browne等[1]首次提出了退化工件的排序問題。文獻[2-3]研究了加工時間與開始加工時間相關的排序問題。文獻[4-6]研究了與退化相關的排序問題。Kuo等[7]證明了問題Pm/pj=aj+btj∑Cj是多項式時間可解的。Kuo等[8]證明了在給定每臺機器加工的工件數前提下,問題Rm/pij=aij+bitij∑Cj是多項式時間可解的。同時,現實生產過程中存在著工件被拒絕的情況。Bartal等[9]首先提出了工件可以拒絕的排序問題。文獻[10-11]研究了帶有退化工件和拒絕的排序問題。Gerstl等[12]研究了工件的加工時間與位置相關的、帶有拒絕的平行機排序問題。Hsu[13]研究了帶有退化工件和拒絕的不同類型機排序問題。

工業生產過程中,經常有退化效應與拒絕懲罰同時出現的情況。本文研究帶有退化工件和拒絕的不同類型機排序問題,與以往情況不同,工件的實際加工時間與工件開始加工時間相關,即pij=aij+bitij,目標函數分別求總時間表長和拒絕懲罰的費用總和以及總完工時間和拒絕懲罰的費用總和。

1 問題描述

假設n個工件J1,J2,…,Jn安排在m臺不同類型機M1,M2,…,Mm上加工,工件均可在零時刻加工,每臺機器一次至多只能加工一個工件,每個工件在同一時刻只能在一臺機器上加工或者被拒絕加工。

和

2 總時間表長與拒絕懲罰問題

引理2[7]對于問題1/pj=aj+btj/Cmax,如果工件的排序π=(J1,J2,…,Jn),則π的時間表長為

它表示把工件Jj指派在機器Mi上位置r的費用。另外,令xijr為0/1變量,如果工件Jj排在機器Mi上r位置時,xijr=1;否則xijr=0。因此,上述問題可以歸結為指派問題:

3 總完工時間與拒絕懲罰問題

引理5[8]對于問題1/pj=aj+btj∑Cj,如果工件的排序π=(J1,J2,…,Jn),則π的總完工時間為

證明 由于工件零時刻到達,引用引理5,則在機器Mi上的完工時間為

同理,帶入目標函數,則有

定義Cijr的值:

它表示把工件Jj指派在機器Mi上位置r的費用。上述問題可以歸結指派問題:

約束集(6)能保證每個工件只能加工一次,約束集(7)能保證每個位置只能加工一個工件。約束集(8)反應出每個工件都能被接受或拒絕。

同理,指派問題要運行的總數為(n+1)m。根據上面的分析,得出了下面的結論。

下面給出此問題的一個數值例子:

例m=2,n=4,a11=5,a12=4,a13=7,a14=2,a21=3,a22=1,a23=3,a24=8,e1=7,e2=11,e3=6,e4=3,b1=1,b2=2。工件被拒絕的個數可以是0,1,2,3,4。首先考慮拒絕一個工件的情況。此數值例子(n1,n2)有4種情況,分別為(3,0),(2,1),(1,2),(0,3)。對于(2,1)這種情況,表1給出了第j個工件排在第i臺機器上的第r個位置時對應的目標函數的系數,其中[i,r]表示工件排在第i臺機器上的第r個位置。

表1 n1=2,n2=1時對應目標函數的系數

解上述指派問題,得F(2,1)=27。此時機器1上的排序為(J4,J1);機器2上的排序為J2;拒絕工件為J3。

4 結 論

本文研究了退化工件帶有拒絕的不同類型機排序問題,工件的加工時間是其開始加工時間的線性遞增函數。目標函數是極小化接受工件的排序指標與拒絕工件總懲罰之和。排序指標分別為總時間表長和總完工時間。通過將2個問題的目標函數轉化為指派問題,證明了它們都是多項式可解的。

[ 1 ]BROWNES,YECHIALIU.Schedulingdeterioratingjobsonasingleprocessor[J].OperRes, 1990,38(3):495-498.

[ 2 ]MOSHEIOVG.Schedulingjobsundersimplelineardeterioration[J].ComputOperRes, 1994,21(6):653-659.

[ 3 ]WANGJibo,WANGMingzheng.Minimizingmakespaninthree-machineflowshopswithdeterioratingjobs[J].ComputOperRes, 2013,40(2):547-557.

[ 4 ]王吉波,劉璐,許揚韜,等. 具有惡化工件的不同工期指派問題研究[J]. 沈陽航空航天大學學報, 2013,30(5):83-87.

[ 5 ]WANGJibo,HSUCJ,YANGDL.Single-machineschedulingwitheffectsofexponentiallearningandgeneraldeterioration[J].ApplMathModel, 2013,37(4):2293-2299.

[ 6 ]沈曉飛,趙玉芳,王曉丹. 帶有退化效應和不可用區間的并行批排序問題[J].沈陽師范大學學報:自然科學版, 2014,32(1):49-53.

[ 7 ]KUOWH,YANGDL.Parallel-machineschedulingwithtimedependentprocessingtimes[J].TheorComputSci, 2008,393(1):204-210.

[ 8 ]KUOWH,HSUCJ,YANGDL.Anoteonunrelatedparallelmachineschedulingwithtime-dependentprocessingtimes[J].JOperResSoc, 2008,60(3):431-434.

[ 9 ]BARTALY,LEONARDIS,SPACCAMELAAM,etal.Multiprocessorschedulingwithrejection[J].SIAMJDiscMath, 2000,13(1):64-78.

[10]CHENGYushao,SUNShijie.Schedulinglineardeterioratingjobswithrejectiononasinglemachine[J].EurJOperRes, 2009,194(1):18-27.

[11]LIShisheng,YUANJinjiang.Parallel-machineschedulingwithdeterioratingjobsandrejection[J].TheorComputSci, 2010,411(40):3642-3650.

[12]GERSTLE,MOSHEIOVG.Schedulingonparallelidenticalmachineswithjob-rejectionandposition-dependentprocessingtimes[J].InfProcessLett, 2012,112(19):743-747.

[13]HSUCJ,CHANGCW.Unrelatedparallel-machineschedulingwithdeterioratingjobsandrejection[J].ApplMechMater, 2013,263:655-659.

[14]GRAHAMRL,LAWLEREL,LENSTRAJK,etal.Optimizationandapproximationindeterministicsequencingandscheduling:asurvey[J].AnnDiscMath, 1979,5(1):287-326.

[15]HSUCJ,CHENGTCE,YANGDL.Unrelatedparallel-machineschedulingwithrate-modifyingactivitiestominimizethetotalcompletiontime[J].InfSci, 2011,181(20):4799-4803.

Unrelatedparallelmachineschedulingwithdeterioratingjobsandrejection

HUChenchen,ZHAOYufang

(School of Mathematics and Systems Science, Shenyang Normal University, Shenyang 110034, China)

In the industrial production process, due to some special reasons, the jobs can be rejected but have to pay the appropriate fees that is rejection penalty. In order to save processing costs, the jobs which have a long processing time and high costs can pay fees to process outside or purchase. This paper considers the unrelated parallel machine scheduling with deteriorating jobs and rejection which combine the concepts of deterioration and rejection. In this model, a job’s actual processing time is an increasing simple linear function of its starting time. The deterioration rate of the job is only related with the machine and regardless of the job itself. The objective is to minimize the sum of the scheduling criterion of the accepted jobs and the total penalty of the rejected jobs. The scheduling criterions are the total load and the total completion time respectively. The purpose is to find the set of rejected jobs, and the non-rejected jobs, and arrange the non-rejected jobs sequence to minimize the objective costs. The objective function of two problems can be transformed into assignment problem, thus proved that the two problems are solvable in polynomial time.

scheduling; unrelated parallel machine; deteriorating jobs; rejection; total completion time

2014-03-06。

遼寧省教育廳科學技術研究項目(L2014433)。

胡晨晨(1989-),女,遼寧錦州人,沈陽師范大學碩士研究生;

: 趙玉芳(1966-),女,遼寧遼陽人,沈陽師范大學副教授,博士,碩士研究生導師。

1673-5862(2014)04-0461-05

O223

: A

10.3969/ j.issn.1673-5862.2014.04.002