具有機器準備時間的半在線排序問題.pdf

1、鄭碩士學位授予單位代碼研究生學號密級學論文論文題目：具有機器準備時間的半在線排序問題作者姓名：學科門類：專業(yè)名稱：研究方向：導師姓名、職稱：陳華榮理學運籌學與控制論圖論與組合最優(yōu)化原晉江教授二零零七年四月AbstractSchedulingisanimportmantproblemincombinatorialoptimizationinwhichweassign80metaskstotimeandresouce8undersomeco

2、nstraints，suchthatoneormulticriteriaattaintotheoptimumRecentlyonlineandsemi—onlineschedulingaretwobranchesdevelopedfasterOnlineschedulingmeansthatalljobinformationisunknownbefortheirreleasetime，andonceajobisscheduleditca

3、nnotbechangedOfflineschedulingmeansthatalljobinformationisknowninadvanceInpractice，problemsarenotonlyreallyonlineoroffline，butsomehowinbetweenSuchacaseisdefinedassemionlineschedulingThismeansthatpartialinformationaboutjo

4、bsisavailableinadvanceAlgorithmsforasemionlineschedulingarecalledsemi—onlineAlgorithmsUniformandparallelmachineschedulingisanimportantschedulingproblemGenerallytheproblemcanbediscrebedasfollows：ThereareasetJ=^，以，，^)ofind

5、ependentjobs，whereJihasproessingtime只Thejobsmustbescheduledonm(m1)paralleanduniformmachinesWearegivenasetofmachinesM=尬，％，，地，and彤isthespeedofmachineij，J=1，2，，mEachjobhasthesameproportionrelationofprocessingtimeondifferent

6、machinesInclassiclschedulingproblems，weoftenassumemachinesprocessjobsattimezeroButinpracticesituationsareoftennotSO，suchaseachmachinehasanavailabletimeMachinesCanstarttoprocessjobsaftertheavailabletimeWesaysuchproblemasm

7、achinewithavailabletimeInthispaper，weconsidersemi—onlineschedulingproblemsabouttwomachineswithavailabletimeWeassumesumrepresentsthetotalprocessingtimeofalljobs，andPm∞representsthelargestprocessingtimeofalljobsThemainresu

8、ltsinthispaperareasfollows：(1)FortheschedulingmodelQ2，rAsumlCrminwegiveasemionlinealgorithmwithcompetitiveratioatleast麗a1(2)FortheschedulingmodelP2，rj[sum，PHmlc『mn，wegiveasemionlinealgorithmwithcompetitiveratioi4anditist