Production Planning and Scheduling in Flexible Assembly Systems 1999 edition

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­ 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. . . . . . . . . . . . . . . . . . . . . . . . . . . . .