機(jī)器帶不可用約束和任務(wù)帶運(yùn)輸時(shí)間的排序.pdf

1、蘭州大學(xué)碩士學(xué)位論文機(jī)器帶不可用約束和任務(wù)帶運(yùn)輸時(shí)間的排序姓名：陳伯龍申請(qǐng)學(xué)位級(jí)別：碩士專業(yè)：數(shù)學(xué)運(yùn)籌學(xué)與控制論指導(dǎo)教師：王海明20090501蘭州大學(xué)2009屆碩士學(xué)位論文AbstractInthispaper，weconsiderthenon—resumablecaseofthemachineschedulingproblemwithanonavailabilityconstraintinterval，whichisfixedand

2、knowninadvanceAndthejobhaveadeliverytimehasbeendeliveredtocustomersaftercompletionFirst，weconsidertheproblemoftwoparallelmachineswhereonehasafixednon—availabilityconstraintintervalandtheotheravailablealltimetheobjectivei

3、stominimizethetimebywhichalljobshavebeendeliveredTheproblemisNP—hardWbproposeapolynomialapproximationalgorithmwithaworst—caseperformanceratioof8／5，andshowthattheboundi8tightAtthesametimewepresentadynamicprogrammingmethod

4、andmixedintegerprogrammingmodeltosolvethisproblemSecondlyweconsiderasinglemachineproblemwithannonavailabilityconstraintTheobjectiveistominimizethelargestweightedtimebywhichalljobshavebeendeliveredthisproblemisNP—hardtooW

5、esolvedtheproblemusingdynamicprogrammingmethodandmixedintegerprogrammingmodeli肥alsoproposetwopolynomialapproximationalgorithmsunderthecaseofqi=qowithaworst—caseperformanceratioof2andlerespectiveThirdlywealsoconsiderasing

6、lemachineproblemwithannonavailabilityconstraintTheobjectiveistominimizetheweightedsumoftimebyalljobshavebeendeliveredthisproblemisalsoNPhardWesolvingitwithdynamicprogrammingmethodandmixedintegerprogrammingmodelKeywords：n