同时带有安装时间和送出时间的单机排序问题

胡晨晨, 赵玉芳

(沈阳师范大学 数学与系统科学学院, 沈阳 110034)



同时带有安装时间和送出时间的单机排序问题

胡晨晨, 赵玉芳

(沈阳师范大学 数学与系统科学学院, 沈阳 110034)

在实际生产,如钢铁和冶金工业生产过程中,工件在加工之前需要预热或安装必要的夹具和固定装置,在加工之后工件需要进行冷却处理等,也就是工件在进行加工时常常带有安装时间和送出时间。讨论带有学习效应、安装时间和送出时间的单机排序问题。在这一模型中,工件的实际加工时间是与工件的基本加工时间和工件的实际加工位置相关的一般函数。工件的安装时间和送出时间均依赖于已加工完的工件的实际加工时间,即p-s-d形式。目标函数分别为最大完工时间、总完工时间、加权总完工时间、总延误时间、最大延误时间和最大延迟时间,提出了上述问题的最优排序规则。

排序; 单机; 学习效应; 安装时间; 送出时间

0 引 言

在工业生产中,工件到达后不一定可以马上进行加工,常常在加工前需要进行一些准备工作,如安装夹具或固定装置等。处理这些准备工作需要消耗一定的安装时间,因此考虑加工工件具有一定的安装时间是十分必要的,它对工件的最大完工时间、总完工时间等问题产生影响。Koulamas等[9]首次提出了一种安装时间(p-s-d),它依赖于所有已加工完的工件。Kuo等[10]研究了带有学习效应和安装时间的单机排序问题,目标函数分别为最大完工时间和总完工时间,并对上述问题提出了多项式时间算法。Wang[11]研究了带有安装时间,且学习效应与时间相关的单机排序问题。目标函数分别为最大完工时间,总完工时间,加权总完工时间,最大延迟时间。证明了上述问题都是多项式时间可解的。Lee[12]研究了同时带有安装时间,学习效应和退化效应的单机排序问题,其中工件的实际加工时间是与工件的基本加工时间和工件的实际加工位置相关的一般函数。目标函数分别为最大完工时间,总完工时间,加权总完工时间,总延误时间,最大延误时间和最大延迟时间。提出了上述问题的最优排序规则,证明了它们都是多项式时间可解的。Hsu等[13]研究了带有学习效应和安装时间的不同类型机排序问题。目标函数是总完工时间问题。证明了上述问题可以转化成指派问题,是多项式可解的,算法复杂性为o(n(m+2))。

同时,在钢铁工业加工过程中,钢铁由于在加工完成后温度极高,不会马上送出,这就需要一定时间来进行冷却,因此工件的等待时间会对工件的总完工时间产生不利的影响,Koulamas等[14]提出了这样的不利影响被认为是与过去排序相关的(p-s-d)送出时间。为了分析方便,通常假设送出时间与工件的等待时间是成比例的。Rustogi等[15]对加工时间为一般函数的排序问题作了综述。Zhao等[16]研究了带有送出时间的单机排序问题。其中,送出时间是与过去排序相关的,加工时间是与位置相关的一般函数,即pj,r=g(r)pj,目标函数分别为最大完工时间和总完工时间。证明了上述问题是多项式时间可解的。

1 问题描述

假设有n个独立的工件在一台机器上需要被加工,记为J={J1,J2,…,Jn}。对于每个工件Jj,pj表示Jj的基本加工时间;wj表示Jj的权;dj表示Jj的工期;Cj表示Jj的完工时间;Tj=max{0,Cj-dj}为Jj的延误时间。工件的实际加工时间可表示成:

pj[r]=pjg(r),r=1,2,…,n

其中,g(r)表示与位置r相关的非负递减函数。

在[9]中,工件Jj在排序中排在第r个位置的安装时间表示为:

这里b≥0是常数,p[k]表示排在第k个位置的实际加工时间。

在[14]中,工件Jj在排序中排在第r个位置的送出时间表示为:

这里γ≥0是常数,p[k]表示排在第k个位置的实际加工时间。Cmax,∑Cj,∑wjCj和∑Tj分别表示最大完工时间,总完工时间,加权总完工时间和总延误时间;Tmax和Lmax分别表示最大延误时间和最大延迟时间。本文研究的问题,用三参数表示法[17]分别表示为

这里disagr(pj,wj)表示工件的加工时间与权逆序,即对任意的工件Ji和Jj,若pi≤pj有wi≥wj;agr(pj,dj)表示工件的加工时间与工期同序,即对任意的工件Ji和Jj,若pi≤pj时有di≤dj。

2 主要性质

假设存在2个排序S=(π1,i,j,π2)和S′=(π1,j,i,π2),这里π1和π2分别表示部分序列,也就是排在工件Ji和Jj前工件的集合为π1,排在工件Ji和Jj后工件的集合为π2。工件Ji和Jj分别表示在S中第r和第r+1位置上的工件,也就是在π′中第r+1和第r位置上的工件。由于Cj(S)=Cj(S′),j=1,…,r-1,故设Cr-1(S)=Cr-1(S′)=t。在排序S中,工件Ji和Jj的完工时间分别为

同理,排序S′中,工件Jj和Ji的完工时间分别为

2.1 最大完工时间问题

为了更好的说明最大完工时间问题,首先给出下列引理。

引理1[15]对于问题1|pj[r]=pjg(r)|Cmax,工件按SPT规则排列得到最优排序。

定理1 对于问题1|pj[r]=pjg(r),spsd,qpsd|Cmax,工件按SPT规则排列得到最优排序。

证明 用反证法。假设存在最优排序S=(π1,i,j,π2),其中2个相邻工件Ji和Jj分别在第r和第r+1个位置上加工,且pi>pj,而S′=(π1,j,i,π2),则由等式(1)～式(4)有

故

Cj(S)-Ci(S′)=(pi-pj)[g(r)-g(r+1)]+(b+γ)(pi-pj)g(r)

由假设pi>pj,且g(r)为与位置r相关的非负递减函数,带入等式(4)中,有

即交换后工件Ji和Jj的完工时间变小了,也就是排在Ji和Jj后工件的开始加工时间变小了,故变换后的最大完工时间变小了。这与假设S是最优排序矛盾。

2.2 加权总完工时间问题

当wj=1时,加权总完工时间问题即为总完工时间问题,它与最大完工时间问题类似。为了更好的说明总完工时间问题,给出下列引理。

引理2[15]对于问题1|pj[r]=pjg(r)|∑Cj,工件按SPT规则排列得到最优排序。

定理2 对于问题1|pj[r]=pjg(r),spsd,qpsd|∑Cj,工件按SPT规则排列得到最优排序。

证明 与定理1类似,假设存在最优排序S,其中2个相邻工件Ji和Jj分别在第r和第r+1个位置上加工,且pi>pj,在其他工件位置不变的情况下,只交换工件Ji和Jj的位置,得到排序S′,比较等式(1)～式(4)有

由假设pi>pj,且g(r)为与位置r相关的非负递减函数,带入等式(6)中,有Ci(S)+Cj(S)>Ci(S′)+Cj(S′)。即交换后工件Ji和Jj的完工时间和变小了;再由(5)可知,Cj(S)>Ci(S′),也就是排在Ji和Jj后工件的开始加工时间变小了,则它们的完工时间不会增加。而排在工件Ji和Jj前工件的完工时间不变,故交换后的总完工时间变小了。这与假设S是最优排序矛盾。

根据以上分析,下面对目标函数为加权总完工时间的问题进行讨论:

定理3 在问题1|pj[r]=pjg(r),spsd,qpsd,disagr(pj,wj)|∑wjCj中,工件按照pj/wj非减的顺序(WSPT规则)排列可得到最优排序;其中disagr(pj,wj)表示工件的加工时间与权是逆序的,即对任意的工件Ji和Jj,若pi≤pj有wi≥wj。

证明 假设pi≤pj,由定理1可知Cj(S)≤Ci(S′),欲证S优于S′,则只需证明wiCi(S)+wjCj(S)≤wiCi(S′)+wjCj(S′)即可。由等式(1)～式(4),有

因为pi≤pj,而工件的加工时间与权逆序,则wi≥wj,即wipj≥wjpi。又因为g(r)为与位置r相关的非负递减函数,带入等式(7)中,有wiCi(S)+wjCj(S)≤wiCi(S′)+wjCj(S′)。

下面讨论目标函数与工期有关的问题, 主要考虑总延误时间问题,最大延误时间问题和最大延迟时间问题。

2.3 总延误时间问题

定理4 在问题1|pj[r]=pjg(r),spsd,qpsd,agr(pj,dj)|∑Tj中,工件按照dj非减顺序(EDD规则)排列可得到最优排序;其中agr(pj,dj)表示工件的加工时间与工期是同序的,即对任意的工件Ji和Jj,若pi≤pj时有di≤dj。

证明 假设pi≤pj,则有di≤dj。对于排序S=(π1,i,j,π2)和S′=(π1,j,i,π2),由于排序π1中的加工顺序相同,则总延误是相等的。由定理1可知,最大完工时间按SPT规则排序最优,因此S中部分序列π2的总延误不会大于S′中部分序列π2的总延误。为了证明序列S的总延误小于或等于序列S′的总延误,只需证Ti(S)+Tj(S)≤Ti(S′)+Tj(S′)。

为了分别比较序列S和S′中工件Ji、Jj的总延误,考虑2种情况。

和

假设Ti(S)≠0且Tj(S)≠0,由定理1,di≤dj和pi≤pj有

假设Ti(S)≠0且Tj(S)≠0,由定理1,di≤dj和pi≤pj有

因此,Ti(S)+Tj(S)≤Ti(S′)+Tj(S′)。

根据上述问题的讨论,对于最大延误问题,有如下结论:

推论 在问题1|pj[r]=pjg(r),spsd,qpsd,agr(pj,dj)|Tmax中,工件按照dj非减顺序(EDD规则)排列可得到最优排序。

证明 与定理4的证明类似,省略。

2.4 最大延迟时间问题

定理5 在问题1|pj[r]=pjg(r),spsd,qpsd,agr(pj,dj)|Lmax中,工件按照dj非减顺序(EDD规则)排列可得到最优排序。

在排序S和S′中分别有:

Li(S)=Ci(S)-di,Lj(S)=Cj(S)-dj,Li(S′)=Ci(S′)-di,Lj(S′)=Cj(S′)-dj。

2.5 数值例子

解p[1]1表示第1个位置工件的实际加工时间,p[1]表示第1个位置工件的基本加工时间,则

3 结 论

在本文中,研究了带有学习效应、安装时间和送出时间的单机排序问题。工件的实际加工时间是与工件的基本加工时间和工件的实际加工位置相关的一般函数。工件的安装时间和送出时间均依赖于已加工完的工件的实际加工时间的简单函数。目标函数为最大完工时间,总完工时间,加权总完工时间,总延误时间,最大延误时间和最大延迟时间。证明了上述问题都是多项式时间可解的。对于带有学习效应、安装时间和送出时间问题的其他目标函数,如总误工工件数,公共工期指派等问题,也正在研究中。同时,可将安装时间和送出时间加入到退化效应的函数中,也可将模型推广到多机的问题,有待进一步研究。

[ 1 ]BISKUPD.Single-machineschedulingwithlearningconsiderations[J].EurJOperRes, 1999,115(1):173-178.

[ 2 ]MOSHEIOVG.Schedulingproblemswithalearningeffect[J].EurJOperRes, 2001,132(3):687-693.

[ 3 ]WANGJibo,MaLi,WangLiyan,etal.Twosinglemachineschedulingproblemswithalearningeffect[J].JDalianUniversityTechnol, 2008,48(6):932-936.

[ 4 ]KUOWH,YANGDL.Minimizingthetotalcompletiontimeinasingle-machineschedulingproblemwithatime-dependentlearningeffect[J].EurJOperRes, 2006,174(2):1184-1190.

[ 5 ]CHENGMB,TADIKAMALLAPR,SHANGJ,etal.Singlemachineschedulingproblemswithexponentiallytime-dependentlearningeffects[J].JManufSyst, 2015,34:60-65.

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

[ 7 ]YINYunqiang,XUDehua,SUNKaibiao,etal.Someschedulingproblemswithgeneralposition-dependentandtime-dependentlearningeffects[J].InfSci, 2009,179(14):2416-2425.

[ 8 ]YANGDL,CHENGTCE,KUOWH.Schedulingwithagenerallearningeffect[J].IntJAdvManufTechnol, 2013,67(1/2/3/4):217-229.

[ 9 ]KOULAMASC,KYPARISISGJ.Single-machineschedulingproblemswithpast-sequence-dependentsetuptimes[J].EurJOperRes, 2008,187(3):1045-1049.

[10]KUOWH,YANGDL.Singlemachineschedulingwithpast-sequence-dependentsetuptimesandlearningeffects[J].InfProcessLett, 2007,102(1):22-26.

[11]WANGJibo.Single-machineschedulingwithpast-sequence-dependentsetuptimesandtime-dependentlearningeffect[J].ComputIndEng, 2008,55(3):584-591.

[12]LEEWC.Single-machineschedulingwithpast-sequence-dependentsetuptimesandgeneraleffectsofdeteriorationandlearning[J].OptimizationLett, 2014,8(1):135-144.

[13]HsuCJ,KuoWH,YangDL.Unrelatedparallelmachineschedulingwithpast-sequence-dependentsetuptimeandlearningeffects[J].ApplMathModel, 2011,35(3):1492-1496.

[14]KOULAMASC,KYPARISISGJ.Single-machineschedulingproblemswithpast-sequence-dependentdeliverytimes[J].IntJProducEcon, 2010,126(2):264-266.

[15]RUSTOGIK,STRUSEVICHVA.Simplematchingvslinearassignmentinschedulingmodelswithpositionaleffects:Acriticalreview[J].EurJOperRes, 2012,222(3):393-407.

[16]ZHAOChuanli,TANGHengyong.Singlemachineschedulingproblemswithgeneralposition-dependentprocessingtimesandpast-sequence-dependentdeliverytimes[J].JApplMathComput, 2014,45(1/2):259-274.

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

Single machine scheduling problems with setup time and delivery time

HUChenchen,ZHAOYufang

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

This paper studies the single machine scheduling problems with learning effect, setup time and delivery time. In this model, the actual processing time of a job is a general function of the normal processing time of the job and its scheduled position. The setup time and delivery time depend on a general function of the processing times of the jobs already processed and its scheduled position, i.e., the setup time and delivery time are past-sequence-dependent(p-s-d).The objectives are to minimize the makespan, the total completion time, the total weighted completion time, the total tardiness, the maximum tardiness, and the maximum lateness. We provide the optimal schedules for some single-machine problems and results show that they are solvable in polynomial time respectively.

scheduling; single machine; learning effect; setup times; delivery times

2014-11-18。

辽宁省教育厅科学研究一般项目(L2014433)。

胡晨晨(1989-),女,辽宁锦州人,沈阳师范大学硕士研究生; 通信作者: 赵玉芳(1966-),女,辽宁辽阳人,沈阳师范大学副教授,博士,硕士研究生导师。

1673-5862(2015)03-0351-07

O223

A

10.3969/ j.issn.1673-5862.2015.03.008