资源描述：
《Job Shop Scheduling英文学习资料》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、Chapter7:Job-shopscheduling(pp.134–160)GeneticalgorithmsinengineeringsystemsEditedbyA.M.S.ZalzalaandP.J.FlemingIEEcontrolengineeringseries55c1997:TheInstitutionofElectricalEngineers,ISBN:0852969023Chapter7Job-shopschedulingTakeshiYamadaandRyoheiNakano7.1IntroductionScheduli
2、ngistheallocationofsharedresourcesovertimetocompetingactivities.Ithasbeenthesubjectofasignificantamountofliteratureintheoperationsresearchfield.Emphasishasbeenoninvestigatingmachineschedulingproblemswherejobsrepresentactivitiesandmachinesrepresentresources;eachmachinecanproce
3、ssatmostonejobatatime.Table7.1:A33problemjobOperationsrouting(processingtime)11(3)2(3)3(3)21(2)3(3)2(4)32(3)1(2)3(1)Thenmminimum-makespangeneraljob-shopschedulingproblem,hereafterreferredtoastheJSSP,canbedescribedbyasetofnjobsfJig1jnwhichistobeprocessedonasetofmmachines
4、fMrg1rm.Eachjobhasatechnologicalsequenceofmachinestobeprocessed.TheprocessingofjobJjonmachineMriscalledtheoperationOjr.OperationOjrrequirestheexclusiveuseofMrforanuninterrupteddurationpjr,itsprocessingtime.Ascheduleisasetofcompletiontimesforeachoperationfcjrg1jn;1rmth
5、atsatisfiesthoseconstraints.ThetimerequiredtocompleteallthejobsiscalledthemakespanL.Theobjectivewhensolvingoroptimizingthisgeneralproblemistodeterminetheschedulewhichmin-imizesL.Anexampleofa33JSSPisgiveninTable7.1.Thedataincludesthe1CHAPTER7.JOB-SHOPSCHEDULING2routingofeach
6、jobthrougheachmachineandtheprocessingtimeforeachoperation(inparentheses).TheGantt-ChartisaconvenientwayofvisuallyrepresentingasolutionoftheJSSP.Anexampleofasolutionforthe33probleminTable7.1isgiveninFigure7.1.,,,,M,,1J1J2J3,,,,,,,,JJJM,,,,23,,12,,,,,,,,,,,,,,MJJ,J3213,,,,,,
7、,,,,024681012time,,,Figure7.1:AGantt-Chartrepresentationofasolutionfora33problemTheJSSPisnotonlyNP-hard,butitisoneoftheworstmembersintheclass.Anindicationofthisisgivenbythefactthatone1010problemformulatedbyMuthandThompson[18]remainedunsolvedforover20years.Besidesexhaustiv
8、esearchalgorithmsbasedonbranchandboundmethods,sev-eralapproximationalgorithmshaveb
