1、蘭州大學碩士學位論文機器帶不可用約束和任務帶運輸時間的排序姓名：陳伯龍申請學位級別：碩士專業(yè)：數(shù)學運籌學與控制論指導教師：王海明20090501蘭州大學2009屆碩士學位論文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