帶時間維度的Packing問題的研究.pdf

1、蘭州大學(xué)碩士學(xué)位論文帶時間維度的Packing問題的研究姓名：王俊嶺申請學(xué)位級別：碩士專業(yè)：計算機(jī)軟件與理論指導(dǎo)教師：李廉20090501AbstractInrecentyears，withthedevelopmentofscienceandtechnologythereisincreasingawarenessthattimeisefficiencyandtimeisthelifelineThus，inthelargescalefoo

2、dandlatheprocessinghowtorationallyarrangetheprocessingsequenceSOthatthetotalprocessingtimeisminimalbecomesthesubjectofconstantattentionIntheabove—mentionedprocess，iftheprocessingtime，theproperty，isremoved，itisaPackingpro

3、blemSo，theabovementionedproblemCallberegardedasaPackingproblemwithtimedimensionThisproblemisregardedastheBakingproblem，sinceitssolvingprocessisverysimilartothecourseofmeatbakingSincePackingproblem，whichisNP—hard，couldber

4、egardedasonesubproblemoftheBakingproblem，ourBakingproblemisNP—hardtoo。Thatis，thereneverexiststheoptimalalgorithmwithpolynomialtimeforBakingproblemThereforewetumtothenearoptimalalgorithms，whichcontainheuristicalgorithmsan

5、dapproximationalgorithm。Thesetwokindsofalgorithmshavetheiradvantagesanddisadvantages。Theformeralgorithmisdesignedtobesimplebutineffective；latteralgorithmisdesignedtobedifficultbutwithabetterandstablerresultsWhenthebaking

6、sequenceisordered，thegreedyalgorithmisproventobeoptimalforbakingproblembyintroducingtheconceptoftheworkingscheme；whileitsNP—hardforbakingproblemwhenthebakingsequenceisoutoforderTherefore，forone—dimBakingproblem，someheuri

7、sticalgorithmsalegiven，togetherwi睡allapproximationalgorithmundertheworstsituationandfourstrategiesbasedonshelfideaUndermulti—dimensionalsituation，unfortunatelytheeffectsofcorrespondingheuristicalgorithmsarerelativelypoor