【word】 一类超前有奖延误受罚的排序问题

【word】 一类超前有奖延误受罚的排序问题 一类超前有奖延误受罚的排序问题 2010年11月 第25卷第6期 成阳师范学院 JournalofXianyangNormalUniversity NOV.2O1O VO1.25No.6 【基础数学与应用数学研究】 一 类超前有奖延误受罚的排序问题 王海峰,苑丽华 f曲阜师范大学运筹与管理学院.山东Et照276826) 摘要:讨论了带有学习效应的排序问题,目标函数为超前有奖延误受罚的几个问题.对所 有工件加工时间不相同和相同的情形,分别给出了算法,并了算法的最优性. 关键词:学习效应;超前有奖延误受罚:最优排序 中图分类号:0223文献标识码:A文章编号:1672—2914(2010)06—0001—04 ASchedulingProblemwithEarlinessAwardandTardinessPenalty WANGHai—feng,YUANLi—hua (CollegeofOperationsandManagement,QufuNormalUniversity,Rizhao,Shandong276826,China) Abs缸 act:Inthispaper,theschedulingproblemwithlearningeffectisconsidered.Theobjective functionistominimizethetotalearlinessawardandtardinesspenalty.Severaloptimalalgorithmsare providedfortheprocessingtimesofthejobsarenon—identicalandidentical,r espectively. Keywords:learningeffect;earlinessawardandtardinesspenalty;optimalscheduling 分批排序问题是半导体生产过程的最后阶段提 炼出来的一类重要问题【lj,对于工件时到达,目标函 数为总完工时间这种情形,Bruckert给出了一时间复 杂性为O(凡肛))的动态规划算法.对目标函数为加权 总完工时间.而且属于每一批工件的个数没有限制 而工件有不同到达时间的情形,Deng和Zhang[31证 明了是NP一完备的.并给出了到达时间个数和加工 时间个数是常数的动态规划算法.而对目标函数为 加权总完工时间的问题,已经推出它是NP.完备的, 苗翠霞等[4]在工件有相同的加工时间的情况给出了 最优算法. 在经典排序中,工件的加工时间是一个常数,而 在一些实际排序问题中由于工厂和工人反复加工同 样的工件.他们学会了如何更有效地操作,这意味着 工件在加工顺序中排在后面的加工时间反而缩短. 这类问题被称之为具有学习效应的排序问题.为很 好地示这种学习效应,Biskup[51提出一种学习效应 模型:p,.J,r=l,2,…,n.其中血?0,a为常数, 是学习效应因子,为加工时间,为实际加工 时间.r为加工位置.在该模型中,工件的实际加工时 间只受位置的影响.Kuo提出了一种新的学习效 r.1 应模型:p(1+p[】+p…(1+P,其中 –l 口0,a为常数,是学习效应因子,为工件在位置r 的实际加工时间,P为标准加工时间,PN,k=l,2,…, 卜1为安排在位置k上的工件的标准加工时间,在该 模型中,工件的实际加工时间受排序中前r一1个 工件标准加工时间之和的影响,该模型在许多现实 环境中非常实用. 在工件具有学习效应的条件下,考虑目标函数为 超前有奖延误受罚的排序问题,这里的排序问题可表 示为1ILEI(Ot,Ci为工件的完工时间,和 i=l E分别为延误和超前工件的时间,其中Ti=max{0,Ci— d},Ei=max{O,d—Ci},;>0是罚因子,>O是奖因子.在 工件的加工时间不一和加工时间都相等的情况下给 出最优算法. 所研究的问题用三参数法表示如下: Ir一1l 1lp(1+?p[kl?(%J, 收稿日期:2010—05—23 基金项目:国家自然科学基金项目(10671108). 作者简介:王海峰(1983一),女,山东青岛市人,曲阜师范大学运筹与管 理学院硕士研究生. ? 2?成阳师范学院第25卷 其中口O.为学习效应因子. 1加工时间都不相同的情形 当工件的加工时间不相等时,给出了最优算法. 引理1对于问题 Ir-lI lIp(1+?pJcl嘣,按s序来排序可得I–1l 到最优解. 证明见 中,工件五在第r个位置上加工,工件J;在第r+1个 位置上加工,这种交换不影响工件和之前工件 的完工时间. 在仃中.有 卜2 CA~r)--p【l回(1+?p[1一印(1+?pq=1 r-I l+p, 一 C~Or)=p【1]+p闭(1+?…印『r_1】(1+?砌q1 卜lr-l l+PI(1+p.. =1曩=l 在仃中.有 卜2 (仃)--p【—翻(1+?p【u)口_卜…印I卜11(1+?pq=1 p(1+?p口=1 , (々r)【l】印踊(1+p【l…印[卜l】(1+P11.1 卜1r一】 111.’ pk(1+p竹(1+十p).. q:1q=I 因此有 1+?p.(1+?p啪.卜(1+?p一q=1q=1q1 r-Ir一1 咖(1+?p.(1+?p【qi+p).】=?叩(1+ ?+p(1+?pM(1+?】+p))+q=1q=1q=1 r一1卜l +?p】印)aIW~(1+?p..q=1q=l 因为p,埘>I(>p), 所以 ,一】,一】 (1+?p】+p)(1+?pM).,q1q=1 (1+?(1+?p刚.一_P(1+(1+p】”一q=】=l r_l l+?p】+p>-0.q=l 因此有 ?(一?)>0.. 所以7r优于7r,这与7r是最优排序矛盾.所以 WSPT序是该问题的最优排序. 1对于问题 l卜lI 1fp(1+?P[k,d<min{pj,:l,2,…,n}f—Jk= 1I1 ,如果P和一致,则按p如不减的顺序排序得 最优解. 证明:如果d<min,i=1,2,…,,l},则所有的工件 完成 工.因此有 ?(椰):?(ce1)-e1)=?c广?.(=(cc广卢.i=1i=1i=1i:1 因为最后一项为常数,故由引理3可知,上述结论 成立. 定理3对于问题 1卜1fip(1+?【i,oLi=l1P(12一,凡)i?(OL—Ip(1+2l一【(=1,,…, 凡)I2.,(—l:1l’1 E),如果PJ和OL一致,则按Pi不减的顺序排序 可得最优解. 证明:如果(1,2,…,n),则相应的目标函 数变为 ?(:?(一目:?.(c广:i=1i=li:1 ?Ci一?.i=li:l 因为最后一项为常数.故由引理3可知,上述结论 成立. 2加工时间都相同的情形 当工件的加工时间都相等时,给出了最优算法. 定理4对于问题 fr—lf 1(1+?Ptk,d<mi:1,2,…,n}l?(一Ik=1I1 ),如果Pi,则按不增的顺序排序可得最优解. 证明:如果d<min,i=1,2,…,n},则所有的工 件都超期,因此有 ?():?(e一:?otiCi一?.i=1=1i=1=l 因为最后一项为常数,故由引理3可知,上述结论 成立. 定理5对于问题 l卜1I 1Ip(1+?P[kYp,d>c—I?(ol),如果p,l=1Il1 则按不增的顺序排序可得最优解. 证明:如果>,则所有的工件都提前完工. 因此有 ?(OL压)=?(G一:?G一?.(压)=(G一=G一f.i=1L=1i=1i=1 因为最后一项为常数.故由引理3可知,上述结论 成立. 定理6对于问题 1lp(1+p,F(=1,2,…,n)l(OLi]BE),l1I, l:1I一 如果p,则按OL不增的顺序排序可得最优解. 证明:如果OL(1,2,…,n),则相应的目标函 数变为 ?(—):?(一E):?(Ci一:i=1=1l=1 ?Ci一?.i:ll=1 因为最后一项为常数,故由引理3可知,上述结论 成立. 定理7对于问题 l卜1l 1lP(1+?P(1,2,…,n)I?(T,-B,E2o~,T,-B,E),如JP(1+2p,=(=1,,…,n)l(),如 I:II’1 果p-p,则按不增的顺序排序可得最优解. 证明:假设是问题 fIJ 1lp(1+?p(12一,n)l?(韶)的Ik= 1I1 最优排序,但不是按屈不增的顺序进行排列.不妨设 存在两个相邻工作,,工件在之前加工,但 >,设工件的开工时间为,,工件在第r个位置 上加工,工件在第r+1个位置上加工.设为工件 之前的目标函数值,B为工件之后的目标函数 值.在中,将工件和位置互换,得到排序, 设A为工件之前的目标函数值,日为工件之后 的目标函数值.又因为所有工件的标准加工时间都 相等,故有A=A,B=B.设)和)分别表示序列 和O-的目标函数值.则下面通过几种情况来证明 其正确性. 1)当d比t小时,则可由定理4知其成立. 2)在序(7-中,d在工件的跨度内,在序中,d 在工件的跨度内时,则有 r一】,一1 flo-)=A+o~斗p(1+?P++p(1+?P【=1=1 r一1 印+?p+B,=l r一1r-1 Ao”)=A+(1+?P+O+?P= 1=1 r—J p(1+?plk~~-d)+B.=1 又因为 ,i=1,2,…,, 所以有 咸阳师范学院第25卷 cr))=(一(1+?p0=l 由定理6知,变换后目标函数值不变. 3)在序中,d正好处在工件被加工完成时,在 序中,d正好处在工件被加工完成时.则有 r-I卜1 /?:A—cq(t-p(1+?p陋】)(1印?p柏,–1=1 卜l卜1 一 ol+?p(1+?ptQ:--d)+B,–l=l 又因为 p=l,2,…,,,.=(=1,2,…,凡), 所以 (0r)=0. 因此在这种情况下变化后目标函数值不变. 4)在序or中,d正好处在工件的跨度内,在序 or中,d正好处在工件五的跨度内,则有 );A(d—t-p(1+?p?+O斗(1+?p= 1=l r_1 (1+p?p+B, )=A—7日}(d一,-pj(1~p.+竹(1+?p+:1=1 ,一1 +?pcf)柏.=1 又因为 p(i:1,2,…,n),o/=ce(i=l,2,…,n), 所以 卜1 Ao-)-Ao-)=)(cf—t-p(1+?pV)->o.k=1 所以变换后目标函数值变优,与最优排序矛盾,故or 为最优排序. 5)在序中,d正好处在工件被加工完成时,在 序or中,d正好处在工件被加工完成时.由定理5 知其成立 3小结 本文考虑了具有学习效应和共同交货期的单机 排序问题,目标函数为超前有奖延误受罚总和.目标 是找出最优排序,使得目标函数值达到最小.因为 该问题的一般情形是NP—hard,所以这里给出了一 些特殊情况下的多项式可解的特例,并给出了算法 和相应的证明过程. 参考文献: 【114国春,张峰,罗守成,等.现代排序论【M】.上海:上海科 学普及出版社,2003. [2]BmckerP,GladkyA,HoogevreenH,eta1.Vandevelescheduling abatchingmachine[J].JournalofScheduling,1998(1):31— 54. 【3]DengXT,ZhangYZ.Minimi~ngme~rlresponsetimein batchprocessing[J].Algorithmic,2004(4):513-528. 【4】苗翠霞,张玉忠.极小化加权总完工时间的分批排序1”-3题【J]. 运筹学,2005(2):82—86. 【5]BiskupD.Single—machineschedulingwithlearning consideration[J】_EuropeanJournalofOperationalResearch, 1999(115):l73—178. [6]KuoWH,YangDL.Minimizingthemakespanina single—machineschedulingproblemwithatime-based learningeffect[J】.InformationProcessingLetters,2006(97) 64-67. 【7]KuoWH,YangDL.Minimizingthetotalcompletiontimein asingle-machineschedulingproblemwithatime-dependent learningeffect[J].EuropeanJournalofOperationalResearch, 2006(174):l184一l190.