一類加工時間依賴資源的單機(jī)排序問題.pdf

1、論文編號沈陽師范大學(xué)Y850383碩士學(xué)位論文論文題目：一類加工時間依賴資源的單機(jī)排序問題所在院系：數(shù)學(xué)與系統(tǒng)科學(xué)學(xué)院學(xué)科專業(yè)：運(yùn)籌學(xué)與控制論指導(dǎo)教師：趙傳立教授研究生姓名：謝謝學(xué)位授予單位：沈陽師范大學(xué)完成時間：20051215SingleMachineSchedulingProblemswithResourceDependentProcessingTimesAbstractInthispaperweconsideraclassofs

2、chedulingproblemwithn0一preemptiveprocessingtimesdependentontheonlyonetypeofSOnlecontinuouslydivisibleresourcesWegivesomeconclusionsaboutsingleschedulingproblemswithresourcedependentfirstThefollowingpartsarethemajorpartso

3、fthispaperinwhichwediscussthreetypesofresourceconstrainedschedulingproblemswithasingleprocessorandoneadditionaltypeofcontinuousresourcesThefirstproblem，wediscusstheresourceconstrainedschedulingproblemwitllreadytimewhichp

4、rocessingtimeofjobsaregivenaslinearnonincreasingfunctionsdependentontheresourcesassignedtothejobsTheamomltofresourcesassignedtoallthejobsareconstrainedTheobjectiveistofindoptimalsequenceofthejobsandallocationoflimitedres

5、ources，whichminimizethesunlofweightedmakespanandtheresourceconsumptionsWegivesomeconclusionsBasedonsomepropertiesoftheproblem，wepresentapolynominalalgorithmWegiveanexampletoillustrateitThesecondproblem，forprecedentconstr

6、aintsofthefirstproblem，wediscussanoptimalsequenceofthejobsandallocationoflimitedresources，whichminimizethesumofweightedmakespanandtheresourceconsumptionsWealsogiveallexampletoillustrateitThethirdproblem，weconsiderasingle

7、machineschedulingproblemwithresourcedependentsetupandprocessingtimeswhicharegivenaslinear，nonincreasingfunctionsdependentontheresourcesassignedtothejobsTheobjectivefunctionistheslimofmakespanandwetghtedresourceconsumptio

8、nswhichareallocatedtosetuptimesandjobsWegivesomeconclusionsBasedonsomepropertiesoftheproblem，wepresentapolynominalalgorithmWegiveanexampletoillustrateitKeywords：scheduling，resourceconstrained，NP—hard，processingtime，algor