资源描述：
《on the potentially optimal solutions of classical shop scheduling problems》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、InternationalJournalofOperationsResearchInternationalJournalofOperationsResearchVol.4,No.2,80-89(2007)OnthePotentiallyOptimalSolutionsofClassicalShopSchedulingProblems*TankaNathDhamalaCentralDepartmentofMathematics,TribhuvanUniversity,Kathmandu,Nepal.ReceivedApril2006;RevisedAugust2006;Ac
2、ceptedSeptember2006Abstract¾Inthispaper,weconsideranimportantclassofNP-hardshopschedulingproblems,whereoneofthemajortasksistominimizethemakespanobjectiveoverthesetofallsequences.Westudytheexistenceofminimalpotentiallyoptimalsolutioninclassicalshopschedulingproblems.Theconceptofpotentially
3、optimalsolutionhasprovenoneofthemostimportantandfertileresearchtopicsasthissolutionsetcontainsatleastoneoptimalsequenceforarbitraryprocessingtimes.Here,thepotentiallyoptimalsolutionofallirreduciblesequencesissurveyedandanewdecompositionapproachispresentedinthisclass.Thecontributionofthisp
4、aperisabriefsurveyoftheexistingresultstogetherwithfewnewresults.Theresearchresultsobtainedinpastseveralyearsarepresentedalongwithopenproblemsandpossibleextensions.Varietiesofresultsandexamplesweanalyzedprovideusefulstructuralinsightsandenoughmotivationsforthedevelopmentsofexactorheuristic
5、algorithms.Keywords¾Shopschedulingproblems,Computationalcomplexity,Countingproblem,Potentialoptimality,Irreducibility,Sequencedecomposition1.INTRODUCTIONTheproblemO2
6、
7、CmaxissolvableinO(n)time,butitisNP-hardform³3(GonzalesandSahni,1976).BräselandWeconsiderthestronglyNP-hardshopschedulingKl
8、einau(1996)presentanalgorithmofthesameproblema
9、
10、Cmax,wherearepresentsajobshop(a=J)complexityforO2
11、
12、Cmaxbymeansofblock-matricesortheopenshop(a=O).WerefertoGrahametal.(1979)model.TheproblemF3
13、
14、CmaxisNP-hard(Lenstraetal.,fortheclassificationschemea
15、b
16、gofscheduling1977),howeverthisproblemwith
17、onlytwomachinesisproblems,wherebdescribesthemachineenvironment,gO(nlogn)timesolvable(Johnson(1954)).TheproblemgivessomejobcharacteristicsandadditionalrequirementsJ2
18、
19、CmaxisNP-hardastheproblemJ2
20、pijÎ{1,2}
21、Cmaxisandistheoptimalitycriterion.Inanonpreemptivealreadyinthi
