两台可拒绝同型机半在线排序问题

《两台可拒绝同型机半在线排序问题》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、2009年3月运筹学学报第13卷第1期March，20090RTRANSACTIONSV0l_13No．1SemiOn-LineSchedulingonTwoIdenticalMachineswithRejectionMinXiaoKongXiangqingAbstractThispaperinvestigatesasemion．1ineschedulingproblemontwoidenticalmachineswithrejection．Whenajobarrives，wecalleitherrejectit，in

2、whichcasewepayitspenalty,oracceptitinwhichcaseitcontributesitsprocessingtimetothemakespanoftheconstructedschedule．TheobjectiveiStominimizethesumofthemakespanofthescheduleofallacceptediobsandthepenaltiesofallrejected1obs．NOpreemptionisallowed．Inadditiontwoparalle

3、lsystemsareavailable．Twoschemescouldbechoosenandwecanselectthebettersolutionfinally．ThisiSthefirstsemion．1ineversiononiden．ticalprocessorswithrejection．、vepresentanapproximationalgorithmwithcompetitiveratio3／2andalowerboundof≈1．366iSproposed．KeywordsOperationsre

4、search，scheduling，rejection，semion—line，approximational-gorithm，competitiveratio．SubjectClassification(GB／W13745。921110．74两台可拒绝同型机半在线排序问题闵啸孔祥庆摘要本文讨论一个两台可拒绝同型机半在线排序问题．当工件到达时，可以被拒绝，但要付出一定的罚值，也可以被接收加工，消耗一定的加工时间．其目标是要使所有加工工件生成的makespan和被拒绝工件的总罚值之和最小．加工不允许中断．进一步，机器带有

5、两个并行处理子系统，可以提供两种排序方案，最后选取较好的一种．这是第一个在可拒绝同型机排序模型中使用半在线信息，我们设计出一个近似算法，其竞争比为3／2，另外又给出一个≈1．366的下界．关键词运筹学，排序，可拒绝，半在线，近似算法，竞争比学科分类号(GB／T13745．92)110．741IntroductionInthispaper，weconsiderasemion—lineidenticalmachineschedulingwithrejection．Anidenticalprocessors(machines

6、)systemdenotedbyM={M1，M2．，)andasequenceofindependentjobsJ={t，l，’．．．，，aregiven．Themachinesareavailableattimezeroandnopreemptionisallowed．EachjobhasapositiveprocessingtimedenotedbytjandapenaltycalledPd．Whenajobarrives，itcanbeeitherrejectedwithpayingacertainpenalty

7、Pjorbeacceptedandassignedtosomemachine．inwhichcaseltcontributesitsprocessing收稿日期t2005年9月2日．1．DepartmentofMathematicsandInformationScience，Jiaxingcollege，314001，China；嘉兴学院数学与信息科学学院，浙江嘉兴，314001．MinXiao，KongXiangqing13卷timetothemakespanoftheconstructedschedule．Theo

8、bjectiveistominimizethesumofthemakespanofthescheduleofallacceptedjobsandthepenaltiesofallr~ectedjobs．Aschedulingproblemiscalledon—lineifitrequirestoschedulejobsirrevo