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

1、碩士學(xué)位論文論文作者：學(xué)科專(zhuān)業(yè)：指導(dǎo)教師：培養(yǎng)單位：培養(yǎng)類(lèi)別：完成時(shí)間：沈陽(yáng)師范大學(xué)學(xué)位評(píng)定委員會(huì)帶有不可用區(qū)間的可拒絕排序問(wèn)題帶有不可用區(qū)間的可拒絕排序問(wèn)題閆力君運(yùn)籌學(xué)與控制論趙玉芳數(shù)學(xué)與系統(tǒng)科學(xué)學(xué)院全日制2015年05月22日單位代碼：?jiǎn)挝淮a：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