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