1、鄭碩士學(xué)位授予單位代碼研究生學(xué)號(hào)密級(jí)學(xué)論文論文題目：具有機(jī)器準(zhǔn)備時(shí)間的半在線排序問(wèn)題作者姓名：學(xué)科門(mén)類(lèi)：專(zhuān)業(yè)名稱(chēng)：研究方向：導(dǎo)師姓名、職稱(chēng)：陳華榮理學(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