资源描述：
《排序问题P2prmpCmax在中断-重复模型下的调度》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、第15卷第6期运筹与管理Vol.15,No.62006年12月OPERATIONSRESEARCHANDMANAGEMENTSCIENCEDec.2006排序问题P2
2、prmp
3、Cmax在中断—重复模型下的调度123杨斌鑫,刘小冬,成龙(1.太原科技大学应用科学学院,山西太原030024;2.西安财经学院,陕西西安710061;3.航天时代电子公司第七七一研究所,陕西西安710075)摘要:对于传统的中断—恢复模型下的P2
4、prmp
5、Cmax问题,已有最优调度规则。但中断—恢复模型并不是一般意义下的中断模型。在某些情况下,被中断的
6、任务不能被简单的恢复加工,而是在该任务被重新加工之前必须有一定的延迟时间。延迟可能是该项任务的一部分(或者是全部)需要返工的时间。本文在研究了排序问题P2
7、prmp
8、Cmax在中断—重复模型下的调度,指出对于选择哪一个任务被中断的问题是NP2hard的;而对于如Xj何处理被中断的任务的问题,指出当被中断任务的最初被加工时间由Xj增加为Xj+ΔXj=时,可使得11-αj2n31αjXj两台处理机的时间表长相等,从而达到最优。最优时间表长为:Cmax=2∑pj+2-α。最后给出了在中断—jj=1重复模型下的调度规则。关键词:运筹学;排
9、序;并行机排序;中断中图分类号:0223文章标识码:A文章编号:100723221(2006)0620025203AnAlgorithmforP2
10、prmp
11、CmaxtothePreempt2repeatModel123YANGBin2xin,LIUXiao2dong,CHENGLong(1.InstituteofAppliedScience,TaiyuanUniversityofScienceandTechnology,Taiyuan030024,China;2.Xi’anFinancialInstitute,Xi’an7100
12、61,China;3.ChinalishanMicroElectricalCompany,Xi’an710068,China)Abstract:TherehasbeentheoptionalalgorithmfortheproblemP2
13、prmp
14、Cmax.Butthetraditionalpreempt2resumemodelisnottheusualdelaycondition.Sometimes,thepreemptioncannotbesimplyresumed,insteadtheremustbesomedelaybe
15、foretheworkisreprolessed.Thedelaymaybethetimeforreprocessthatthepaitofthework(orwhole)needs.Inthisthesis,westudytheproblemP2
16、prmp
17、Cmaxtothepreempt2repeatmodel.WepointoutthattheproblemwhichjobshouldbeselectedtopreemptisNP2hard.Andfortheprob2lemofhowtodealwiththeselecte
18、djob,wepointoutthatwhentheoriginalworktimeofthepreemptedjobXjischangedfromXjtoXj+ΔXj=,theprocess2timeofthetwomachineswillbeequal,andtheopti211-αj2n31αjXjmaltimelengthCmax=∑pj+.Atlast,analgorithmforP2
19、prmp
20、Cmaxisgiven.2j=12-αjKeywords:operationsresearch;scheduling;para
21、llelmachinescheduling;preemption0已有结果对于中断—恢复模型下的P2
22、prmp
23、Cmax问题,已有如下研究成果:收稿日期:2006203206基金项目:航空科学基金资助项目(01J53079)作者简介:杨斌鑫(19762),男,山东省牟平县人,讲师,硕士,研究方向运筹学。26运筹与管理2006年第15卷n[1]31引理1Cmax≥C=maxmax{pj},∑pjj2j=1该引理给出其时间表长的一个下界。对于上述下界,算法1给出一个最优排序。[1]算法1:n1Step1计算C=maxmax{pj},∑
24、pj;j2j=1Step2把n个任务任意排在一台处理机上加工,其时间表长等于n个任务加工之和且不超过2C;Step3把上述单机排序时间表分成2部分,第一部分[0,C],第二部分为[C,2C];Step4把第一部分[0,C]的排序作为处理机P1的排序
