工件帶有優(yōu)先約束的平行機(jī)在線排序問題.pdf

1、:10459:7力夕文學(xué)論大位州學(xué)鄭士碩論文題目:作者姓名:學(xué)科門類:專業(yè)名稱:研究方向:導(dǎo)師姓名、職稱:工件帶有優(yōu)先約束的平行機(jī)在線排序問題吳豐金理學(xué)運(yùn)籌學(xué)與控制論圖論與組合最優(yōu)化l占亞匡勺〕砂戈壽七文少刁又曰1口匕廿久J又二零零八年五月AbstraetScheduling15to舫signsometaskstotimeresoureesundersomeeonstraints，suehthatoneormultieriteria就t

2、aintotheoPtimum.Reeentl又on一lineseheduling15aflourishingschedulingmodel.Onlineschedulingmeansthatailjobinfmationsareunknownbefetheirreleasetimes.Jobseannotbeseheduledbefethcyarrived，andjobsdonothavetobescheduledimmediatel

3、yuPonarrival.Oneetheyarescheduledthaseheduleeannotbechanged.InthisPaPer，weeonsideranon一lineschedulingmodel:on一lineschedulingProblem，往thwithconstraintsonidenticalParallelProeesss.Thereare幾jobs，Jl，J2，…，Jn，eonstraints.Eachj

4、obhasarele留etimerj，aproe哪ingtimePj.Thesejobeneedtobeproeesedon饑七1identiealparallelproeesss.Atask，oneebegun，cannotbeinterruPeteduntiliteomPletes.Ourobjective15tominimizethesumofsquaresofthemachineeompletiontimes.Usingthe3

5、fieldnotationofGrahametal.!31，our___t，__:_J___‘_」__0_._____.孕，。、2pr0D‘em‘5QenoteQas廠mlpre眾，馬疊氣嘛‘)一ThemainresultsofthisPaPerareasfollows.(1)FortheSchedulingmodelPZPj=‘，。.睿(味‘)’the10認(rèn)吧rboundofeomPetitiveratioofanyonlinealg

6、ithm15notlessthans4.(2)Fbrthes比edulingmodelp3腸=1，￡ntroe‘boundofeomPetitiveratioofanyonlinealgorithm(3)凡rtheSchedulingmodelpZ馬=p，eha云ns‘boundofcomP眺itiveratioofanyo企linealgorithm(4)FortheschedulingmodelPZ腸=1，卿e眾releasedat

7、r‘藝(嶸:)2，thelower云=115notlesthan302281.2releasoda之r‘藝(C示‘)“，theloweri=115notl創(chuàng)粥than10681.releasedatr‘藝(嶸)2，the10Wer=1boundofetitiveratioofanyonlinealgitllnl15notlesthan6549.W七alsogiveanonlinealgorithmwitheomPetitiveratio