带有退化工件和拒绝的不同类型机排序问题

胡晨晨, 赵玉芳

(沈阳师范大学 数学与系统科学学院, 沈阳 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