帶有不可用區(qū)間的可拒絕排序問題.pdf

1、碩士學(xué)位論文論文作者：學(xué)科專業(yè)：指導(dǎo)教師：培養(yǎng)單位：培養(yǎng)類別：完成時間：沈陽師范大學(xué)學(xué)位評定委員會帶有不可用區(qū)間的可拒絕排序問題帶有不可用區(qū)間的可拒絕排序問題閆力君運籌學(xué)與控制論趙玉芳數(shù)學(xué)與系統(tǒng)科學(xué)學(xué)院全日制2015年05月22日單位代碼：單位代碼：10166SchedulingproblemwithnonavailabilityintervalrejectionAbstractTheactualprocessingtimeofajob

2、islongerifitisprocessedlaterinasequenceinmanyrealisticproblems.Examplescanbefoundinfinancialmanagementsteelproductionfirefightingresourceallocationnationaldefenseetc.inwhichanydelayinprocessingajobmayresultindeteriationi

3、naccomplishingthejob.Atthesametimethemachinemaybeunavailablebecauseofperiodicalrepairspreventivemaintenancesnamelynonavailabilityinterval.Inmanymanufacturingenvironmentshoweverajobneedtobepreprocessedbefeitundergoesproce

4、ssing.Thispreprocessingtimecanbeconsideredasjobreleasetime.Atthesametimemachinesarenotavailableatalltimesbecauseofperiodicalrepairspreventivemaintenancesduringtheschedulingperiodnamelynonavailabilityinterval.Itisalwaysas

5、sumedintraditionalresearchthatallthejobshavetobeprocessed.Inthesettingofschedulingwithrejectionthemanagermaydecidenottoprocesssomejobsiftheyarenotprofitable.Whilesavingsomedirectproductioncostarejectedjobincurssomepenalt

6、yduetotherejectionnamelyrejectionpenalty.Examplescanbefoundinmanyindustriessuchasaircraftelectronicsetc.Thispaperstudiedtheschedulingproblemswithreleasetimedeteriatingeffectrejectionanonavailabilityinterval.Inthismodelre

7、leasedatesofallthejobsareequal.Jobprocessingtimesarenotfixedbecausejobsmaydeteriatewhilewaitingtobeprocessed.Ajobiseitherrejectedinwhichcasearejectionpenaltyhastobepaidprocessedonthemachine.Themachinecan’tprocessanyjobin

8、thenonavailabilityinterval.Thespecificcontentissummarizedasfollows:1.Westudythesinglemachineschedulingproblemthattheobjectiveistominimizethesumofthemakespanoftheacceptedjobsthetotalrejectionpenaltyofalltherejectedjobs.Fi

9、rstweproposeapseudopolynomialtimedynamicprogrammingalgithm.thenwedesignafullypolynomialtimeapproximationschemetosolvetheproblemanalyzethetimecomplexity.2.Westudythesinglemachineschedulingproblemthattheobjectiveistominimi