具有機(jī)器準(zhǔn)備時(shí)間的半在線排序問題.pdf

1、鄭碩士學(xué)位授予單位代碼研究生學(xué)號密級學(xué)論文論文題目：具有機(jī)器準(zhǔn)備時(shí)間的半在線排序問題作者姓名：學(xué)科門類：專業(yè)名稱：研究方向：導(dǎo)師姓名、職稱：陳華榮理學(xué)運(yùn)籌學(xué)與控制論圖論與組合最優(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∞r(nóng)epresentsthelargestprocessingtimeofalljobsThemainresu

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