Production Planning and Scheduling in Flexible Assembly Systems

Flexibleassemblysystems(FASs)haveemergedasaresultofthedevelop- mentsinmanufacturingandcomputertechnology. Currentmarketrequire- mentscharacterizedby -increasingnumberofdifferenttypesandversionsofproducts, -smallerbatchsizes,and -shorterlife-timeofproducts, stronglydeterminethecompetitivenessinproductionassemblyandaddi- tionallycontributetothedevelopmentofflexibleautomatedassembly. For example,attheendof1986[33]40%ofJapaneserobotswerespecialized inassemblyascomparedwithonly10%ofEuropeanrobots. Theremain- ing90%wereusedinwelding,painting,andhandling. Theintroductionof flexibleautomatedassemblytohigh-techsectorswhereassemblycostsare criticalistheaimofmajorEuropeanprojectssuchasESPRITandBRITE programmesandtheFAMOS-EUREKAproject,e. g. ,[33,34]. Thebookdealswithproductionplanningandschedulinginflexibleassem- blysystems. ThereaderisfamiliarizedwiththeFASplanningandschedul- ingissuesforwhichvariousoperationsresearchmodellingandsolutionap- proachesarediscussed. Inparticular,applicationsofintegerprogrammingto theFASshort-termplanningandfastcombinatorialheuristicstotheFAS schedulingarediscussed. Thematerialinthebookhasbeendividedintosevenchapters. Chapter1presentstheoverallstructureandhardwarecomponentsand featuresofaflexibleassemblysystem. TheFASsclassificationisprovided andillustratedwithindustrialapplicationsofmechanicalpartassemblyand printedcircuitboard(PCB)assembly. Chapter2discussesmajorissuesinthedesign,planningandschedulingof flexibleassembly. BasicconfigurationsofFASsandmaterialflownetworksare presentedandvariousapproachestodesignforautomatedassemblyandto assemblyplanningarediscussed. TheFASproductionplanningandschedul- ingareconsideredwithinahierarchicalframeworkwithmachineloadingand assemblyroutingatanupperlevelandmachineandvehicleschedulingata lowerlevel. Finally,specificissuesinplanningandschedulingofPCBassem- blyarediscussed. VIII Preface InChapter3variousbi-objectiveintegerprogrammingmodelsandso- lutionapproachesarepresentedformachineloadingandassembly-routing inFASs. Aninteractiveprocedureisproposedforsimultaneousloadingand routingbasedonweightingapproachandalexicographicalgorithmisgiven forsequentialloadingandroutingwithalinearrelaxationloadingheuristic andanetworkflowroutingmodel. Numericalexamplesillustratepossible applicationsofthemodellingandsolutionapproachespresented. InChapter4thesequentialmodellingandsolutionapproachproposedin Chapter3hasbeenextendedforabicriterionmachineloadingandassembly routingwithsimultaneousassemblyplanselectioninageneralFASandina flexibleassemblyline. Numericalexamplesareprovidedtoillustratepossible applicationsoftheapproachproposed. Chapter5presentsmathematicalprogrammingformulationsforsimul- taneousloadingandschedulinginflexibleassemblycells. Theformulations areillustratedwithpracticalapplicationsinmechanicalpartassemblywith arobotassemblycellandinPCBassemblyonacomponentplacementma- chine. Chapter6isdevotedtoproductionschedulinginflexibleassemblylines whereseveralassemblystagesinseriesareeitherseparatedbyfiniteinter- mediatebuffersortherearenobuffersbetweenthestages,andeachstage consistsofoneormoreidenticalparallelmachines. Fastpush-typeschedul- ingheuristicsareproposedforthelinewithlimitedintermediatebuffersor thelinewithnoin-processbuffers. Foracomparison,apull-typeschedul- ingstrategyisillustratedwithsomerecentresultsfortheJust-In-Timeand multilevelschedulingofflexibleassemblylines. Numericalexamplesprovide thereaderwithpossibleapplicationsofthevariousmodellingandsolution approachespresented. InChapter7simultaneousschedulingofassemblystationsandautomated guidedvehiclesisdiscussedforageneralFASandtwodifferentsolutionap- proachesarepresented:(i)amulti-levelapproach,inwhichfirstmachine loadingandassemblyroutingproblemissolvedandthen,giventaskassign- mentsandassemblyroutesselected,detailedmachineandvehicleschedules aredetermined;(ii)asingle-levelapproach,inwhichmachineandvehicle schedulesaredirectlydeterminedwithnoinitialloadingandroutingdeci- mentscharacterizedby -increasingnumberofdifferenttypesandversionsofproducts, -smallerbatchsizes,and -shorterlife-timeofproducts, stronglydeterminethecompetitivenessinproductionassemblyandaddi- tionallycontributetothedevelopmentofflexibleautomatedassembly. For example,attheendof1986[33]40%ofJapaneserobotswerespecialized inassemblyascomparedwithonly10%ofEuropeanrobots. Theremain- ing90%wereusedinwelding,painting,andhandling. Theintroductionof flexibleautomatedassemblytohigh-techsectorswhereassemblycostsare criticalistheaimofmajorEuropeanprojectssuchasESPRITandBRITE programmesandtheFAMOS-EUREKAproject,e. g. ,[33,34]. Thebookdealswithproductionplanningandschedulinginflexibleassem- blysystems. ThereaderisfamiliarizedwiththeFASplanningandschedul- ingissuesforwhichvariousoperationsresearchmodellingandsolutionap- proachesarediscussed. Inparticular,applicationsofintegerprogrammingto theFASshort-termplanningandfastcombinatorialheuristicstotheFAS schedulingarediscussed. Thematerialinthebookhasbeendividedintosevenchapters. Chapter1presentstheoverallstructureandhardwarecomponentsand featuresofaflexibleassemblysystem. TheFASsclassificationisprovided andillustratedwithindustrialapplicationsofmechanicalpartassemblyand printedcircuitboard(PCB)assembly. Chapter2discussesmajorissuesinthedesign,planningandschedulingof flexibleassembly. BasicconfigurationsofFASsandmaterialflownetworksare presentedandvariousapproachestodesignforautomatedassemblyandto assemblyplanningarediscussed. TheFASproductionplanningandschedul- ingareconsideredwithinahierarchicalframeworkwithmachineloadingand assemblyroutingatanupperlevelandmachineandvehicleschedulingata lowerlevel. Finally,specificissuesinplanningandschedulingofPCBassem- blyarediscussed. VIII Preface InChapter3variousbi-objectiveintegerprogrammingmodelsandso- lutionapproachesarepresentedformachineloadingandassembly-routing inFASs. Aninteractiveprocedureisproposedforsimultaneousloadingand routingbasedonweightingapproachandalexicographicalgorithmisgiven forsequentialloadingandroutingwithalinearrelaxationloadingheuristic andanetworkflowroutingmodel. Numericalexamplesillustratepossible applicationsofthemodellingandsolutionapproachespresented. InChapter4thesequentialmodellingandsolutionapproachproposedin Chapter3hasbeenextendedforabicriterionmachineloadingandassembly routingwithsimultaneousassemblyplanselectioninageneralFASandina flexibleassemblyline. Numericalexamplesareprovidedtoillustratepossible applicationsoftheapproachproposed. Chapter5presentsmathematicalprogrammingformulationsforsimul- taneousloadingandschedulinginflexibleassemblycells. Theformulations areillustratedwithpracticalapplicationsinmechanicalpartassemblywith arobotassemblycellandinPCBassemblyonacomponentplacementma- chine. Chapter6isdevotedtoproductionschedulinginflexibleassemblylines whereseveralassemblystagesinseriesareeitherseparatedbyfiniteinter- mediatebuffersortherearenobuffersbetweenthestages,andeachstage consistsofoneormoreidenticalparallelmachines. Fastpush-typeschedul- ingheuristicsareproposedforthelinewithlimitedintermediatebuffersor thelinewithnoin-processbuffers. Foracomparison,apull-typeschedul- ingstrategyisillustratedwithsomerecentresultsfortheJust-In-Timeand multilevelschedulingofflexibleassemblylines. Numericalexamplesprovide thereaderwithpossibleapplicationsofthevariousmodellingandsolution approachespresented. InChapter7simultaneousschedulingofassemblystationsandautomated guidedvehiclesisdiscussedforageneralFASandtwodifferentsolutionap- proachesarepresented:(i)amulti-levelapproach,inwhichfirstmachine loadingandassemblyroutingproblemissolvedandthen,giventaskassign- mentsandassemblyroutesselected,detailedmachineandvehicleschedules aredetermined;(ii)asingle-levelapproach,inwhichmachineandvehicle schedulesaredirectlydeterminedwithnoinitialloadingandroutingdeci- sionsrequired. Foreachapproachaschedulingalgorithmbasedondynamic complexdispatchingrulesisproposedandnumericalexamplesareprovided toillustrateandcomparethetwoschedulingapproaches. Thematerialpresentedinthebookisillustratedwithnumerousexamples, figuresandextensivetables. Thereaderisprovidedwithdetailedmathemat- icalmodelsoftheFASplanningandschedulingproblemsanddescriptions ofthesolutionalgorithmsproposed. Theirapplicationsareillustratedwith manynumericalexamplesandresultsofvariouscomputationalexperiments withthemodelsandalgorithmsarereported. Preface IX Thebookisaimedprimarilyatstudentsandprofessionalsinproduction andoperationsmanagement,industrialandsystemsengineering,andauto- matedmanufacturing. Thisbookbenefitedfromnumerousdiscussionswithmycolleagues. Pro- fessorAndreasDrexlandDr. RainerKolischfromtheChristian-Albrechts UniversityofKieldeservespecialthanksforthecarefulreadingofvarious partsofthemanuscriptandtheirvaluablecomments. ThebookhasbeenpreparedwithpartialsupportbyKBNresearchgrant #8TllF01513,AGHgrant#10. 200. 10,andTEMPUS-PHAREproject #S_JEP-09434-95. TadeuszSawik DepartmentofComputerIntegratedManufacturing FacultyofManagement UniversityofMiningandMetallurgy Krakow,Poland TableofContents 1. FlexibleAssemblySystems-HardwareComponentsand Features...1 1. 1 BasiccomponentsofaFAS...1 1. 1. 1Robots...1 1. 1. 2 PeripheraJequipment...4 1. 2 Classificationof'flexibleassemblysystems 5 1. 3 Examplesofindustrialinstallations...8 1. 3. 1 Mechanicalassembly...8 1. 3. 2 Printedcircuitboardassembly...9 2. IssuesinDesign,PlanningandSchedulingofFlexible Assembly...17 2. 1 FASdesignissues...18 2. 2 Networkdesignformaterialflowsystems...22 2. 3 Designforassembly...27 2. 4 Assemblyplanning 30 2. 5 Planningandscheduling...32 2. 5. 1 Machineloadingandassemblyrouting...35 2. 5. 2 Machineandvehiclescheduling 37 2. 5. 3 Planningandschedulinginelectronicsassembly...38 3. LoadingandRoutingDecisionsinFlexibleAssembly Systems 41 3. 1 Descriptionofaflexibleassemblysystem...43 3. 2 Optimizationofstationworkloadsandproductmovements. . 44 3. 3 Designandbalancingofflexibleassemblylines...50 3. 4 Numericalexamples 52 3. 5 Simultaneousloadingandrouting 56 3. 5. 1 Problemformulations...56 3. 5. 2 Aninteractiveheuristicforloadingandrouting 60 3. 5. 3 Numericalexamples...61 3. 6 Sequentialloadingandrouting...68 3. 6. 1 Problemformulations...