Abstract Production, Manufacturing and Logistics Cyclic scheduling of a 2-machine robotic c

Production,ManufacturingandLogistics

Cyclicschedulingofa2-machineroboticcell

withtoolingconstraints

HakanGultekin,M.SelimAkturk*,OyaEkinKarasan

DepartmentofIndustrialEngineering,BilkentUniversity,06800Bilkent,Ankara,Turkey

Received29September2003;accepted8March2005

Availableonline16June2005

Abstract

Inthisstudy,wedealwiththeroboticcellschedulingproblemwithtwomachinesandidenticalparts.InanidealFMS,CNCmachinesarecapableofperformingalltherequiredoperationsaslongastherequiredtoolsarestoredintheirtoolmagazines.However,thisassumptionmaybeunrealisticattimessincethetoolmagazineshavelimitedcapacityandinmanypracticalinstancestherequirednumberoftoolsexceedsthiscapacity.Inthisrespect,ourstudyassumesthatsomeoperationscanonlybeprocessedonthefirstmachinewhilesomeotherscanonlybeprocessedonthesecondmachineduetotoolingconstraints.Remainingoperationscanbeprocessedoneithermachine.Theproblemistofindtheallocationoftheremainingoperationstothemachinesandtheoptimalrobotmovecyclethatjointlymin-imizethecycletime.Weprovethattheoptimalsolutioniseithera1-unitora2-unitrobotmovecycleandwepresenttheregionsofoptimality.Finally,asensitivityanalysisontheresultsisconducted.Ó2005ElsevierB.V.Allrightsreserved.

Keywords:Productionscheduling;Automatedsystems;Roboticcell

1.Introduction

Effortstoimproveproductivitywhilemaintainingtheflexibilityofconventionalsystemsledtothedevel-opmentofFlexibleManufacturingSystems(FMS).ThetermFMScoversarangeofsystemsfromFlexibleManufacturingCells(FMC)toFlexibleTransferLines.AnFMCisanintegratedcomputercontrolledsys-temofasetofcomputernumericalcontrol(CNC)machinesandanautomatedmaterialhandlingdevice.AnFMCinwhichthematerialhandlingisdonebyarobotiscalledaroboticcell.Aroboticcellwithtwomachinesconsistsoftwomachineslocatedseriallyandservedbyarobot.Inthisstudy,consistentwiththe

*Correspondingauthor.Tel.:+903122664126;fax:+903122664054.E-mailaddress:akturk@bilkent.edu.tr(M.S.Akturk).

0377-2217/$-seefrontmatterÓ2005ElsevierB.V.Allrightsreserved.doi:10.1016/j.ejor.2005.03.021

778H.Gultekinetal./EuropeanJournalofOperationalResearch174(2006)777–796

roboticcellschedulingliterature,wewillassumethateachpartbeingprocessedgoesthroughtheinputbuf-fer,thefirstmachine,thesecondmachineandfinallytheoutputbufferinthatorder.Afterloadingaparttooneofthemachines,theroboteitherwaitsfortheparttocompleteitsprocessingormovestounloadan-othermachineassoonastheprocessingofthepartfinishes(thereisnowaitingtimetotakeapartfromtheinputbufferortodropaparttooutputbuffer).Astateofthesystemisdefinedbywhethertherobotandthemachinesareloadedoremptyandbythelocationoftherobot.

Intheexistingliterature,theallocationoftheoperationstoeachmachineisassumedtobeconstantandforgivenprocessingtimestheoptimumrobotmovecycleminimizingthecycletimeistobedetermined.Insomemanufacturingoperationssuchaschemicalelectroplatingthisassumptionismeaningfulandtheseoperationsmostlyrequireno-waitconstraints(seeforexampleDawandeetal.,2003).However,inthecaseofmachiningoperationsforwhichtheCNCmachinesareused,theallocationoftheoperationstothema-chinesisalsoadecisionproblem.ThisisbecauseCNCmachinesarecapableofperformingawiderangeofoperationswithmeansofusingdifferentcuttingtools.Therefore,assumingthatprocessingtimesarefixedoneachCNCmachinemaynotaccuratelyrepresentthecapabilitiesoftheCNCmachinesandlimitsthenumberofalternativesunnecessarilyforthesesystems.

Inthisstudy,weconsideraroboticcelloftwoidenticalCNCmachineswhichrepeatedlyproducesonetypeofproduct.Weassumethatthereisaninfinitenumberofpartstobeprocessed,whereapartisdefinedbyafixedsetofoperationstobeperformedinanyorderandeachoperationrequiresauniquetypeofcut-tingtooltobeperformed.Thatis,onetoolcanperformdifferentoperationsbutanoperationcanonlybeperformedbyauniquetypeoftool.Wealsoassumethatsometoolsareloadedonlyonthefirstmachineandsomeothersareloadedonlyonthesecondmachine.Athirdsetoftoolsareduplicatedandloadedonbothmachines.Asaresultofthis,anoperationcaneitherbeprocessedonlyonthefirstmachine,onlyonthesecondmachineoroneithermachine.Thisassumptionisvalidsincethetoolmagazinesofthesema-chineshavelimitedcapacity.Additionally,thoughduplicatingtherequiredtoolsincreasesflexibility,dupli-catingallofthemmaynotbeeconomicallyjustifiable.ThentheproblemisnotonlysequencingtherobotÕsactivitiesbutalsopartitioningthesetofflexibleoperationsintotwomachines.Theobjectiveistominimizethecycletimewhichisdefinedasthelongrunaveragetimerequiredbytheroboticcelltocompleteonepart.Moreformally,weassumethatwehaveinfinitenumberofpartsandifSndenotesthecompletiontimeofthenthpartthenthelongrunaveragecycletimeislimsupn!1Sn/n(Cramaetal.,2000).Cyclicproduc-tioninaroboticcellreferstotheproductionoffinishedpartsbyrepeatingafixedsequenceofrobotmoves.AsdiscussedinDawandeetal.(2003),themainmotivationforstudyingcyclicproductioncomesfrompractice:cyclicschedulesareeasytoimplementandcontrolandaretheprimarywayofspecifyingtheoper-ationofaroboticcellinindustry.Furthermore,Dawandeetal.(2002a)showthatfortheproblemofsched-ulingoperationsinbufferlessroboticcellsthatproduceidenticalparts(similartoourproblem),itissufficienttoconsidercyclicschedulesinordertomaximizethroughput.Theyprovedthatthereisatleastonecyclicscheduleinthesetofallschedulesthatoptimizesthethroughputofthecell.

Intheliterature,thereexistvariousproblemsconcerningtheroboticcells.AnextensivesurveyoftheroboticcellschedulingproblemscanbefoundinCramaetal.(2000)andDawandeetal.(2003).Roboticcellswithnostoragebuffersatorbetweenmachinesarewidelyusedinpractice(MillerandWalker,1990),andasstatedbyKiseetal.(1991),small-scaleflexiblemanufacturingcellswithsimplematerialhandlingdevicesarequitecommoninrealapplications.Sincetherecanbeseveralmachinesrequestingservicesoftherobotatonce,therewillbeconflictsinwhichonemachinewillhavetowaitwhileanotherisservedandifthiswaitingtimeisnothandledproperly,theoverallthroughputofthecellwilldecrease(Kingetal.,1993).

For2-machines,no-buffer,identicalpartsroboticcellschedulingproblem,Sethietal.(1992)provedthattheoptimalsolutionisa1-unitcyclewhereann-unitcyclecanbedefinedas,startingwithaninitialstateofthesystem,loadingandunloadingallofthemachinesexactlyntimesandreturningtotheinitialstateofthesystem(notethatinann-unitcycleexactlynpartsareproduced).Theyalsoconjecturedthat

H.Gultekinetal./EuropeanJournalofOperationalResearch174(2006)777–796779

optimal1-unitcyclesaresuperiortoeveryn-unitcycle,fornP2.1-unitcyclesareimportantsincetheyaresimple,easytoimplementandcontrol.CramaandvandeKlundert(1997)consideredtheidenticalpartsproblemwithmmachinesandshowedthat,consideringonly1-unitcycles,theproblemcanbesolvedin(strongly)polynomialtime.Halletal.(1997)consideredthreemachinecellsproducingsinglepart-typesandprovedthattherepetitionof1-unitcyclesdominatesmorecomplicatedpoliciesthatpro-ducetwounits.ThevalidityoftheconjectureofSethietal.(1992)for3-machineroboticflowshopsisestablishedbyCramaandvandeKlundert(1999).BraunerandFinke(1997)disprovedthisconjectureforcellsofsizefourorlarge.

Additionally,therearemanystudiesconsideringthemultiplepartsroboticcellschedulingprobleminwhichtheobjectiveistofindtheoptimalrobotmovesequenceaswellastheoptimalpartinputsequencethatjointlyminimizethecycletime.ThecomplexityoftheseproblemscanbefoundinSriskandarajahetal.(1998)andHalletal.(1998).

Withthesettingsofthisstudy,weprovethattheoptimalsolutionisnotnecessarilya1-unitcycleasinthecaseofSethietal.(1992)andthata2-unitcyclecanalsogivetheoptimalcycletimeforsomeparametervalues.WealsoshowthattheproblemconsideredbySethietal.(1992)isaspecialcaseoftheproblemunderconsiderationinthisstudy.Wereportsomesensitivityanalysisresultsontheparameterssuchas:theloadingandunloadingtimeoftherobotandthetransportationtimeoftherobot.

Theremainderofthepaperisorganizedasfollows.Inthenextsectionweintroduceourproblemandpresentthenotations,definitionsandtheassumptionspertainingtothisstudy.Thesolutionoftheopera-tionallocationproblemwithtoolingconstraintsispresentedinSection3andthelastsectionisdevotedtotheconcludingremarks.

2.Problemdefinition

Inthissection,wewillstateourproblemmoreformallyandprovidetherequireddefinitionsandnota-tions.Wewillalsohighlightthedifferenceoftheconsideredproblemfromtheearlierstudieswiththeaidofanexample.

TheworkstationsinaroboticcellformachiningoperationsareCNCmachinesandinthesemachinestheprocessingofapartrequiresperformingaseriesofoperationsusingdifferentsetsofcuttingtools.Thecuttingtoolsarestoredinthetoolmagazinesofthesemachines.InanidealFMS,eachmachineiscapableofperformingalloperationsofallpartsscheduledforproductionaslongasithastherequiredtoolsinitstoolmagazine.However,Grayetal.(1993)observethataCNChasalimitedtoolmagazinecapacityandthetotalsetoftoolsrequiredtoprocessalljobsusuallyexceedsthiscapacity.Furthermore,duplicatingalltherequiredtoolsandloadingthemtoeachtoolmagazinemaynotbeeconomicallyjusti-fiableduetohightoolinvestmentcosts.Therefore,weassumethatthereisasinglecopyofsometools.Asubsetofthesesinglecopiesareloadedonthefirstmachineandtheremainingonesareloadedonthesecondmachine.Ontheotherhand,sometoolsareduplicatedandloadedonbothmachines.Asaconse-quence,eachparttobeprocessedhasthreesetsofoperations.O1isthesetofoperationsthatcanonlybeprocessedonthefirstmachine,O2isthesetofoperationsthatcanonlybeprocessedonthesecondmachine,andOisthesetofoperationsthatcanbeprocessedoneithermachine.Theallocationoftheoper-ationsthatareinsetOtothemachinescanbemodifiedforeachindividualpart.Weassumethatwehaveaninfinitenumberofidenticalpartstobeprocessedonthesetwomachinesandeachpartisdefinedbyafixedsetofoperationstobeperformedinanyorder.SotheproblemistofindtheoptimalrobotmovecyclewiththecorrespondingallocationofoperationsthatareinsetOtothemachinesinordertominimizethecycletime.Infact,allocationoftheoperationstothemachinesisequivalenttopartitioningsetOintotwosubsetssothat,theoperationsthatareinthefirstsubsetwillbeprocessedonthefirstmachinewhiletheoperationsintheothersubsetwillbeprocessedonthesecondmachine.

780H.Gultekinetal./EuropeanJournalofOperationalResearch174(2006)777–796

ThefollowingdefinitionswellacceptedintheliteratureareborrowedfromCramaandvandeKlundert(1997).

Definition1.Ann-unitrobotmovecycleisasequenceofrobotmovesduringwhicheachmachineisloadedandunloadedexactlyntimes,andfinallythecellreturnstoitsinitialstate.

Definition2.RobotactivityAicorrespondstothefollowingsequenceofmovements:unloadapartfrommachinei,transportittomachinei+1,andloadmachinei+1.

AccordingtoDefinition2,ina2-machineroboticcellwherethemachinesarenumberedas1and2,theinputbufferisnumberedas0andtheoutputbufferisnumberedas3,wehaveexactlythreerobotactivities:A0,A1andA2.

Sinceinanoptimalcyclewerequirethattherobotmovepathisasshortaspossible,anytwoconsecutiveactivitiesuniquelydeterminetherobotmovesbetweenthoseactivities.Therefore,anyrobotmovecyclecanbeuniquelydescribedbyapermutationoftheaboveactivities.Fortwomachines,wehavetwo1-unitrobotmovecycles:S1:A0A1A2andS2:A2A1A0.Letusrecallthatastateofthesystemisdefinedbywhethertherobotandthemachinesareloadedoremptyandbythelocationoftherobot.Thesetwo1-unitcycleshaveonecommonstateinwhichthefirstmachineisemptyandthesecondmachinehasjustbeenloadedbytherobot.Thus,atransitionfromoneofthesecyclestotheothercanonlybemadeatthiscommonstate.Iftherobotwaitsinfrontofthesecondmachinetofinishtheprocessingofthepart,thentherobotfollowstheactivitiesoftheS1cycle.Elseiftherobottravelstoinputbuffertotakeapartandloadthefirstmachine,thentherobotfollowstheactivitiesoftheS2cycle.Duringthesetransitionsnoextramovementsaremade,thusnolossoccursintermsofrobottransportationtime.

Halletal.(1997)definetwootherrobotmovesequencestorepresenthigherunitrobotmovecycles.ThesearethetransitionmovementsoftherobotfromperformingcycleS1toS2(representedasS12)andS2toS1(representedasS21).IfapartisproducedaccordingtotheS1(S2)cycleinthefirstmachineandaccordingtotheS2(S1)cycleinthesecondmachinethenthetransitionmovementS12(S21)ismade.Toproperlyclarifythesenewrobotmovesequences,weshallusetheterminologyofDawandeetal.(2002b).Fullwaitingisdefinedastherobotwhichhasjustloadedamachinewaitinginfrontofamachinethroughthewholeprocessingtimeofapart.Ontheotherhand,partialwaitingisthewaitingtimefromthearrivaloftherobotatthemachinetilltheprocessingofthepartcompletesatthismachine.Now,wearereadytolisttheS12robotmovementswhichcanbedescribedasA0A1A0:(i)loadthefirstmachineandperformafullwait,(ii)loadthesecondmachineandimmediatelyreturntoinputbuffer,(iii)loadthefirstmachine,and(iv)whileprocessingcontinuesonthefirstmachine,returntothesecondmachineandperformapartialwait.

Inasimilarfashion,inS21movementwhichcanbedescribedasA2A1A2,therobotdoesnotwaitinfrontofthefirstmachineforthepartbutinsteadtravelstothesecondmachine,unloadsitanddropstheparttotheoutputbufferandreturnsbacktothefirstmachinetounloadthepart.Thatis,apartialwaitingonthefirstmachineandafullwaitingonthesecondmachineareencountered.

Furtheranalysisofthesequencesyieldsthefollowing:(i)anexecutionofS1startsandendswithemptymachines,(ii)anexecutionofS2startsandendswithloadedmachines,(iii)anexecutionofS12startswithemptymachinesandendswithfullmachines,and(iv)anexecutionofS21startswithloadedmachinesandendswithemptymachines.Basedontheseobservations,thetransitiondigraphinFig.1depictsthefeasibletransitionsamongsequences.

Halletal.(1997)showedthatanyrobotmovecyclecanberepresentedbythefourrobotmovese-quences:S1,S2,S12andS21.Forexample,S12S21isa2-unitrobotmovecycle,actuallyitistheonly2-unitrobotmovecycleandwecandescribethiscyclebytherobotactivitysequence:A0A1A0A2A1A2.S12S21andS21S12representthesamerobotmovecycle,theonlydifferencebeingthestartingstateofthecycle(theani-matedviewsoftheserobotmovecyclescanbefoundatthewebsitehttp://www.ie.bilkent.edu.tr/~robot).

H.Gultekinetal./EuropeanJournalofOperationalResearch174(2006)777–796781

S1 S12 S21 S2Fig.1.Transitiondigraph.Wewillusethefollowingparametersanddecisionvariables:tiPM1PM2P󰀂d

processingtimeofoperationifori2O1[O2[O.NotethattheprocessingtimesofoperationionbothmachinesareequalforanyiinOP

totalprocessingtimeoftheoperationsthatareinsetO1,PM1¼Pi2O1titotalprocessingtimeoftheoperationsthatareinsetO2,PM2¼i2O2titotalPprocessingtimeoftheoperationsthataretobeallocatedtoeitheroneofthemachines,P¼i2Oti

theload(orunload)timeofworkstationsbytherobot

timetakenbytherobottotravelbetweentwoconsecutivestations.Weassumethattherobottra-veltimefrommachineitojisjjÀijd.Sothetriangularequalityissatisfied.Forexample,thetrans-portationtimefrominputbuffertothesecondmachineisj2À0jd=2dandthetransportationtimefromoutputbuffertoinputbufferisj0À3jd=3d

longrunaveragecycletimetoproduceonepart,adecisionvariableofourproblem

T

NotethatifsetOisempty,thatiswhenP=0,thereisnoallocationproblem.Asaconsequence,theproblembecomesidenticalwiththeproblemconsideredbySethietal.(1992).Anotherimportantobserva-tionisthattheorderinwhichtheoperationsareprocessedonthemachinesdoesnothaveaneffectonthecycletime.

Inordertocalculatethecycletimeofanygivenrobotmovecycle,theprocessingtimesofpartsoneachmachinemustbeknowninadvance.However,inordertofindtheprocessingtimesofthepartsonthema-chines,wehavetoknowtheallocationoftheoperationsinsetOtothemachines.Furthermore,theallo-cationoftheoperationstothemachinesneednotbefixedforeachparttobeprocessed.Thatis,foronepart,OcanbepartitionedasZ1and(OnZ1)andforthenextparttobeprocesseditcanbepartitionedasZ2P

and(OnZ2)whereZ15Z2.SotheprocessingtimeofthefirstpartPonthefirstmachineisi2O1[Z1tiwhiletheprocessingtimeofthesecondpartonthesamemachineisPi2O1[Z2ti.TheprocessingtimesofthefirstP

andsecondpartsonthesecondmachinearei2O2[ðOnZ1Þtiandi2O2[ðOnZ2Þti,respectively.Thustheprocess-ingtimesofthemachinesmaychangefromonerepetitionoftherobotmovecycletotheother.Infact,usingdifferentallocationsforeachparttobeprocessedonthesetwomachinesmayyieldashortercycle

782H.Gultekinetal./EuropeanJournalofOperationalResearch174(2006)777–796

timethanthecasewhenwehaveafixedallocationtype.Inwhatfollows,wegiveanexampleofsuchasituationfortherobotmovecycleS2.

Example1.LetusconsidertherobotmovecycleS2.Assumethataparthasfiveoperationstobeprocessedwiththecorrespondingoperationtimes:t1=15,t2=30,t3=45,t4=10,andt5=30.Alsolet󰀂=5andd=10.Furthermore,assumethatbecauseofthetoolingconstraints,operation3mustbeprocessedonthefirstmachineandoperation5mustbeprocessedonthesecondmachine.Thus,PM1¼t3¼45,PM2¼t5¼30andP¼t1þt2þt4¼55.Sethietal.(1992)provedthatthecycletimeofS2forfixedprocessingtime,i.e.,sameallocationoftheoperationsforallparts,is:

T¼6󰀂þ8dþmaxf0;aÀð2󰀂þ4dÞ;bÀð2󰀂þ4dÞg;

whereaandbaretheprocessingtimesofthepartonthefirstandsecondmachinerespectively,i.e.,a¼PM1þa0andb¼PM2þPÀa0wherea0takessomevalueinf0;10;15;25;30;40;45;55g.SincemaxfPM1þa0;PM2þPÀa0gP2󰀂þ4d¼50themaxterminthedescriptionofTwilltakeanonnegativevalueandhencewillbeminimizedwhenjaÀbjisminimized.Withthegivenoperationtimesthishappensifoperation1isallocatedtothefirstmachineandoperations2and4areallocatedtothesecondmachine.Soa¼PM1þt1¼60,b¼PM2þt2þt4¼70andjaÀbj¼10.Thenthecycletimebecomes130(anotheralter-nativeistoallocateoperations1and4tothefirstmachineandoperation2tothesecondmachine).Ontheotherhand,letusnowassumethatforthefirstparttobeprocessedweallocatedtheoperationsasbeforesothatwehavea1¼PM1þt1¼60andb1¼PM2þt2þt4¼70,wherea1andb1representtheprocessingtimeofthefirstpartonthefirstandthesecondmachines,respectively.However,assumethatforthesecondpartweallocatedsuchthata2¼PM1þt1þt4¼70andb2¼PM2þt2¼60wherea2andb2aretherespectiveprocessingtimesofthesecondpartonthetwomachines.Assumefurtherthatthesetwoallocationtypesareusedalternatelyinprocessingtheparts.Then,inonerepetitionofthecycle,apartwiththefirstallo-cationtypewillbeprocessedonthefirstmachineandapartwiththesecondallocationtypewillbepro-cessedonthesecondmachine.Thisisbecause,duringonerepetitionofthecycleS2,twodifferentpartsbecomeavailableinthesystem;onenewpartentersthesystemandonepreviouslyenteredpartexitsthesystem.InthesecondrepetitionofS2,apartwiththesecondallocationtypewillbeprocessedonthefirstmachineandapartwiththefirstallocationtypewillbeprocessedonthesecondmachinebecauseweusethesetwoallocationtypesalternatingly.Then,thelongrunaveragecycletimetoproduceonepartcanbefoundasfollows:Sinceweconsidercyclicrobotmoves,letthecyclestartwiththestateinwhichthesecondmachineisloadedbyapartwiththefirstallocationtypeandtherobotisinfrontoftheinputbuffertotakeapartwiththesecondallocationtype.Inordertofindthelongrunaveragetimetoproduceonepart,wehavetoproducetwopartswithdifferentallocationtypesandtaketheaverage.ThismeansrepeatingtheS2cycletwotimes.Letwijbethepartialwaitingtimeinfrontofmachinei,i=1,2,forthepartwithallocationtypej,j=1,2.Thetotalloading/unloadingandtraveltimesarethesameforbothrepetitionsoftheS2cycle,namely,6󰀂þ8d.Inthefirstrepetitionofthecyclethereispartialwaitinginfrontofmachine2forthepartwiththefirstallocationtype,w21,andanotherpartialwaitinfrontofthefirstmachineforthepartwiththesecondallocationtype,w12.Ontheotherhand,inthesecondrepetitionwehavew11andw22.Onecaneasilyconcludethatw11¼maxf0;a1Àð2󰀂þ4dþw22Þg,w12¼maxf0;a2Àð2󰀂þ4dþw21Þg,w21¼maxf0;b1Àð2󰀂þ4dÞgandw22¼maxf0;b2Àð2󰀂þ4dÞg.Fromthese,

w12þw21¼maxf0;a2Àð2󰀂þ4dÞ;b1Àð2󰀂þ4dÞg;w11þw22¼maxf0;a1Àð2󰀂þ4dÞ;b2Àð2󰀂þ4dÞg.Hence,thelongrunaveragecycletimetoproduceonepartis:

maxf0;a1Àð2󰀂þ4dÞ;b2Àð2󰀂þ4dÞgmaxf0;a2Àð2󰀂þ4dÞ;b1Àð2󰀂þ4dÞg

þ

22

andwiththegivendatathisboilsdowntoT¼125.

T¼6󰀂þ8dþ

H.Gultekinetal./EuropeanJournalofOperationalResearch174(2006)777–796783

Thisexampleshowsthatfixingtheallocationtypeofeverypartlimitsthebetterofavailablealternatives.Notethatfindingtheallocationoftheoperationstothemachineseveniftherobotmovecycleisfixedisnotaneasytask.ThiswillbefurtherexploredinSection3.

Wewillrefertothefollowingdefinitionsthroughoutthispaperespeciallywhenfindingthecycletimesoftherobotmovecycleswithdifferingpartallocationtypes.

Definition3.Inak-allocationtypeproduction,theallocationofeverykthpartintheinfinitesequenceisidenticalandkisminimalwiththisproperty.Thatis,kistheperiodoftheallocation.

Notethata2-unitrobotmovecyclewithone-allocationtypemeansthatallpartstobeprocessedhavethesameallocationofoperationstothemachines.A2-unitcyclewithtwo-allocationtypesmeansthattwoidenticalpartswithdifferentallocationofoperationstothemachinesareproducedalternatingly.Thecycletimeforthiscaseisfoundbycalculatingthetotaltimetofinishonerepetitionofthecycleanddividingbytwo.Ontheotherhand,a2-unitcyclewiththree-allocationtypesmeansthattheallocationofoperationsforparts1;4;...;3zþ1arethesame.Thisalsoholdsforparts2;5;...;3zþ2andparts3;6;...;3z.Inordertofindthecycletimeofann-unitcyclewithk-allocationtypes,wehavetofindtheleastcommonmultipleofnandk;letthisnumberbeM.Tofindtheaveragetimetoproduceonepart,wehavetorepeatthecycleM/ntimesanddividethetotaltimebyM.Inparticular,fora2-unitcyclewiththree-allocationtypes,wehavetorepeatthecycle3timesanddividethetotaltimebyM=6.

Notealsothatinak-allocationtypeproductionforaspecifick,theallocationoftheoperationsisnotuniquebutratherthereexistfinitelymanydifferentallocations.Letrkbeaspecificallocationofoperationsforak-allocationtypeproductionandrÃkbetheoptimalallocationofoperationsforak-allocationtypeproduction.Wefurtherneedthefollowingdefinitionfortheprocessingtimesofthepartsonbothmachines.

Definition4.Consideranyrobotmovecycleusingak-allocationtypeproduction.Letrkbeaspecificallocationoftheoperationstothemachines.Then,Pj(rk)isthesummationoftheoperationtimesthatareallocatedtothefirstmachineforapartwhichusesthejthallocationtypewherej6k.Notethatunderthissetting,thetotalprocessingtimeofthispartonthesecondmachineissimplyPÀPjðrkÞ.

Inlightofthesenewdefinitions,inExample1abovethereexisttwodifferentallocationtypes.Inparticular,a1representsPM1þP1ðr2Þwhereasa2representsPM1þP2ðr2Þ.Thesearetheprocessingtimesonthefirstmachine.Theprocessingtimesonthesecondmachineforthefirstandsecondallo-cationtypesarePM2þPÀP1ðr2ÞandPM2þPÀP2ðr2Þrespectively.Fig.2depictsak-allocationtypeproduction.

Inadditiontothesedefinitions,weletTS2ðrkÞbetheaveragecycletime(toproduceonepart)ofS2usingk-allocationtypeswithspecificallocationrkandTS2ðoptÞ¼minrkfTS2ðrkÞg.LetTS12S21ðrkÞandTS12S21ðoptÞbede-finedinasimilarfashionformovecycleS12S21.

Inthenextsectionwewillreducethenumberofpotentiallyoptimalrobotmovecyclestothreeandwewillfindtheregionsofoptimalityfortheserobotmovecyclesaccordingtothegivenparameterssuchas,theloadingandunloadingtime󰀂andtherobottransportationtimed.

3.Schedulingwithtoolingconstraints

Inordertofindtheoptimalrobotmovecycle,wehavetocomparethecycletimesoftherobotmovecycles.Thecycletimesdependontheallocationoftheoperations.Inthenextsubsectionwewilldeterminetheoptimalallocationtypesforthreerobotmovecyclesandprovethataccordingtogivenparametervaluesoneofthesethreerobotmovecyclesisoptimal.InSection3.2wewilldeterminetheregionsofoptimality

foreachofthethreerobotmovecyclesandSection3.3isdevotedtothesensitivityanalysisonproblemparameters.

3.1.Optimalallocationofoperations

InthissectionwewillfirstobservethatthereisnoallocationproblemforS1.Theorems1and3willdeterminetheoptimalktobeusedwiththecyclesS2andS12S21respectively.InTheorem2wewillprovethatdeterminingtheoptimalallocationofoperationstothemachinesisNP-completeforrobotmovecycleS2.WeshallassumePM1PPM2throughoutallproofs.Theothercasecanbetreatedinasimilarfashion.

ThecycletimesofthethreerobotmovecyclesdiscussedpreviouslyarepresentedinAppendixA.ThecycletimeofS1,giveninEq.(A.1)doesnotdependontheprocessingtimesofthepartsonthemachinesindividuallybutonlydependsonthetotalprocessingtime,inourcasePþPM1þPM2.Thus,whatevertheallocationoftheoperationsbe,thecycletimeisthesameandhencethereisnoallocationproblemforS1.ThefollowingtheoremprovidestheoptimalktobeusedwithS2:Theorem1.Consideracyclicproductionperformingthe1-unitcycleS2.Wehave:1.IfPM1PPþPM2,thenusingone-allocationisoptimal,

2.Otherwise,usingeitherone-allocationortwo-allocationisoptimal.

Proof

1.Thetotaltimetocompleteproductionofallkpartswithk-allocationtypeforcycleS2underspecificallocationofoperationsrk,isgiveninAppendixA,Eq.(A.4).SincePM1PPþPM2,thenPM1þPjðrkÞPPM2þPÀPðjÀ1ÞðrkÞ;8j2½1;...;k󰀄wherefornotationalpurposeswetake

Ã

P0ðrkÞ󰀅PkðrkÞ.Therefore,underoptimalallocationrÃk,wehavePjðrkÞ¼0;8j.However,thisisnoth-ingbutone-allocationtypeandtheoptimalcycletimeis:

TS2ðoptÞ¼6󰀂þ8dþmaxf0;PM1Àð2󰀂þ4dÞg.

H.Gultekinetal./EuropeanJournalofOperationalResearch174(2006)777–796785

2.Consideragain(A.4).SincePM1M2

PM1þPjðrÃÀPðjÀ1ÞðrÃkÞ%PþPkÞ,\"j.Considertwosuchconsecutiverelations,sayforjthandðjþ1Þthmaxterms:

M2

PM1þPjðrÃÀPðjÀ1ÞðrÃkÞ%PþPkÞ;M2PM1þPðjþ1ÞðrÃÀPjðrÃkÞ%PþPkÞ.

ð1Þð2Þ

Fromrelations(1)and(2),iftheequalitiescannotbesatisfied,thenthedifferencebetweenbothsidesof

M2

ÀPðjÀ1ÞðrÃandeachequalitymustbeminimized.Thatis,bothjPM1þPjðrÃkÞÀðPþPkÞÞj

M1M2ÃÃÃÃ

jPþPðjþ1ÞðrkÞÀðPþPÀPjðrkÞÞjmustbeminimized.NotehoweverthatifPjðrkÞandPðjÀ1ÞðrkÞmin-ÃÃ

imizethefirstdifference,thenPjðrÃkÞandPðjþ1ÞðrkÞ¼PðjÀ1ÞðrkÞsimultaneouslyminimizetheseconddiffer-ÃÃence.Thisyieldseitheraone-allocationðPðjÀ1ÞðrÃkÞ¼PjðrkÞ¼Pðjþ1ÞðrkÞforallj)oratwo-allocation

ÃÃÃ

ðPðjÀ1ÞðrÃhkÞ¼Pðjþ1ÞðrkÞandPjðrkÞ¼PjÀ1ðrkÞforallj).ThoughTheorem1guidesusinselectingtheoptimalallocationtypeinacyclicproductionS2,findingtheoptimalallocationofoperationstothetwomachinesisnotaneasyjobevenwhenthereisafixedallo-cationtypeandevenwhenPM1¼PM2¼0.Moreformally,weshallnowshowthatthefollowingdecisionproblemisNP-complete.

S2operationallocationforone-allocationtypedecisionproblem(problemS2TAP):

Instance:AfinitesetofoperationsOwithrespectiveintegerprocessingtimesft1;...;tpg,loading/unloadingtime󰀂,transportationtimedandarealnumberK.

Question:Canwefindanallocationofoperationstothetwomachines,r1,sothatthelongrunaveragecycletimeTS2ðr1Þ6K?

Theorem2.ProblemS2TAPisNP-complete.

Proof.S2TAPisinNPsincewheneverwearegivenaspecificallocationofoperations,wecanreadilyfindthecorrespondinglongrunaveragecycletimeandhencedecideifitislessthanorequaltoK.Itisapparentfromexpression(A.2)forTS2ðr1Þ(seeAppendixA)thatthewellknownNP-completeproblem2-partition(seeGareyandJohnson,1976)readilyreducestoS2TAP.h

ThefollowingtheoremdeterminestheoptimalktobeusedwithS12S21.Theorem3.For2-unitrobotmovecycleS12S21,usingtwoallocationtypesisoptimal.

Proof.Inordertoprovethistheorem,wewillfirstcomparethecycletimeoftwo-allocationtypeforthecycleS12S21withthecycletimeofone-allocationtypeforthecycleS12S21.Thelongrunaveragecycletimesofone-allocationandtwo-allocationtypesforthecycleS12S21aregiveninEqs.(A.5)and(A.6),respectively.

Wefirstarguethattheoptimalallocationfortwo-allocationtypeforthecycleS12S21isfoundbyletting

Ã1P1ðrÃ2Þ¼ðPÀP2ðr2ÞÞ¼0.LetusfirstrewriteEq.(A.6)byentering2ðP1ðr2ÞþðPÀP2ðr2ÞÞÞintothemaxterm,i.e.,addingittoallthethreeargumentsofmax.Thisleadsustothefollowingform:

TS12S21ðr2Þ¼1=2ð12󰀂þ14dþPM1þPM2Þþ1=2ðmaxfP1ðr2ÞþPÀP2ðr2Þ;PM1þP1ðr2Þ

þPÀð2󰀂þ4dÞ;PM2þ2PÀP2ðr2ÞÀð2󰀂þ4dÞgÞ.

786H.Gultekinetal./EuropeanJournalofOperationalResearch174(2006)777–796

Now,P2(r2)onlyappearswithanegativecoefficientandP1(r2)onlyappearswithapositivecoefficient.Tominimize,wemustincreaseP2(r2)anddecreaseP1(r2)accordingly.So,wetakeP1ðrÃ2Þ¼0and

M1M2Ã

P2ðr2Þ¼P.SincewealsohavePPPthecycletimecorrespondingtothisallocationtypebecomes:

12󰀂þ14dþPM1þPM2þmaxf0;ðPþPM1ÞÀð2󰀂þ4dÞg

.ð3ÞTS12S21ðrÃÞ¼2

2LetusmovePinEq.(A.5)insidethemaxterm.Thuswehave:

M1

TS12S21ðrÃþPM2Þþ1=2ðmaxfP;PþPM1þP1ðrÃÞ¼1=2ð12󰀂þ14dþP1Þ1

Àð2󰀂þ4dÞ;PþPM2þðPÀP1ðrÃ1ÞÞÀð2󰀂þ4dÞgÞ.

ComparingthiswithEq.(3),itiseasilyseenthatTS12S21ðr2Þ6TS12S21ðr1Þ.

Nowletusconsiderthecycletimefork-allocation(k>2)typeforthecycleS12S21.Observethat,inrobotmovecycleS12S21,initially,themachinesareemptyandtherobotiswaitinginfrontoftheinputbuffer.Sincethisisa2-unitcycle,exactlytwopartsareloadedandunloadedtoeachmachineandattheend,identicaltotheinitialstate,themachinesareagainemptyandtherobotiswaitinginfrontoftheinputbuffer.Then,inak-allocationtypeforthecycleS12S21,this2-unitcycleisrepeatedexactlyk/2timestoproduceallkpartswithdifferentallocationtypes.Theobjectiveistofindtheoptimalallocationforthesepartstothemachines.However,theoptimalallocationateachrepetitionofthecyclemustbethesameastheoptimalallocationoftheoperationsforauniquecycleS12S21.Thisisbecause,ak-allocationtypeisaconcatenationofk/2two-allocationtypesforthecycleS12S21.Thus,weconcludethattheoptimalcycletimeforak-allocationtypeforthecycleS12S21isthesameastheoptimalcycletimeforatwo-allocationtypeforthecycleS12S21.h

Now,wearereadytoprovideoneofthemajorresultsofourpaperwhichwillrestrictoursearchfortheoptimalcycletothreerobotmovecycles.WefirstrecallaresultduetoHalletal.(1997).

Lemma1(Halletal.,1997).Inanyfeasiblerobotmovecycle,thenumberofS12sequencesisequaltothenumberofS21sequences.

Theorem4.AtleastoneofthecyclesS1,S2orS12S21hasacycletimethatislessthanorequaltothecycletimeofanygivenn-unitrobotmovecycle.

Fortheclarityofthepresentation,thisproofisdeferredtoAppendixB.

Insummary,wehavethreepotentiallyoptimalrobotmovecycles.FortherobotmovecycleS2,wehaveanallocationproblem.However,weknowfromTheorem1thatifPM1PPþPM2,thentheallocationproblemdisappearsandwehaveTS2ðoptÞ¼6󰀂þ8dþmaxf0;PM1Àð2󰀂þ4dÞg.Else,wecanfindlowerandupperboundsforthiscycletime.WegetalowerboundwhenitispossibletohavePM1þPjðr2Þ¼PM2þðPÀPjðr2ÞÞ,j2½1;2󰀄.Sinceanyfeasiblesolutionprovidesanupperboundfortheoptimalcycletime,wewillpresentafeasiblesolutionthatcanbeattainedwithanygivenproblemin-stanceandusethisfeasiblesolutionasanupperbound.Foragivenprobleminstance,letusallocatealloftheoperationsthatareinsetOtothefirstmachineforthefirstpartandtothesecondmachineforthesecondpart.Notethatsuchanallocationisfeasiblewithanygivenproblemparametervalues.Thus,P1ðr2Þ¼ðPÀP2ðr2ÞÞ¼PinEq.(A.3).LetTS2representthelowerboundofcycleS2andTS2representtheupperbound.Inotherwords:

TS2¼6󰀂þ8dþmaxf0;ðPþPM1þPM2Þ=2Àð2󰀂þ4dÞg;

TS2

maxf0;PþPM1Àð2󰀂þ4dÞ;PþPM2Àð2󰀂þ4dÞg

¼6󰀂þ8dþ

2

M1M2

maxf0;PÀð2󰀂þ4dÞ;PÀð2󰀂þ4dÞg

.þ

2

H.Gultekinetal./EuropeanJournalofOperationalResearch174(2006)777–796787

SinceweassumedthatPM1PPM2theupperboundbecomes:TS2¼6󰀂þ8dþ

11

maxf0;PþPM1Àð2󰀂þ4dÞgþmaxf0;PM1Àð2󰀂þ4dÞg.22

NowwearereadytopresenttheoptimalS2cycletimesalongwithlowerandupperboundsbasedona

setofbreakpointspartitioningthesearchspace.(1)IfPM1PPþPM2,then

(i)IfPM1P2󰀂þ4d,then

TS2ðoptÞ¼4󰀂þ4dþPM1.(ii)Otherwise,

TS2ðoptÞ¼6󰀂þ8d.

(2)Else(i.e.PM1(i)IfðPþPM1þPM2Þ=2P2󰀂þ4d,then

TS2¼4󰀂þ4dþðPþPM1þPM2Þ=2.(ii)Otherwise,

TS2¼6󰀂þ8d.

Theupperboundsareasfollows:(i)IfPM1P2󰀂þ4d,then

TS2¼4󰀂þ4dþPM1þP=2.(ii)ElseifPþPM1<2󰀂þ4d,then

TS2¼6󰀂þ8d.

(iii)Else,

TS2¼5󰀂þ6dþðPþPM1Þ=2.

ð4gÞð4fÞð4eÞð4dÞð4cÞð4bÞð4aÞ

Ontheotherhand,thecycletimeoftwo-allocationtypeforthecycleS12S21isgiveninEq.(A.6).SincePPPM2andemployingTheorem3,wegetthefollowingcycletime:

M1

TS12S21ðoptÞ

ðPM1þPM2Þ1

þmaxf0;ðPM1þPÞÀð2󰀂þ4dÞg.¼6󰀂þ7dþ

22

Therefore,wehavethefollowingbreakpointsforthiscycletime:(1)IfPþPM1P2󰀂þ4dthen,TS12S21ðoptÞ¼5󰀂þ5dþP(2)Else,TS12S21ðoptÞ

ðPM1þPM2Þ

.¼6󰀂þ7dþ

2

ð5bÞ

M1

ðPþPM2Þ

.þ

2

ð5aÞ

788H.Gultekinetal./EuropeanJournalofOperationalResearch174(2006)777–796

3.2.Regionsofoptimality

Inthesequel,wewillproveagroupoflemmaswhichwilljointlyleadtoTheorem5presentingthere-gionsofoptimalityforthesethreerobotmovecycles.

Lemma2.IfPM1þPM2P2d,thenS2givestheminimumcycletime.

Proof.AssumePM1þPM2P2d.LetusfirstcompareTS1andTS12S21ðoptÞ.TS1isasgiveninEq.(A.1).1.IfPþPM1P2󰀂þ4d,TS12S21ðoptÞisgiveninEq.(5a).AsimplecomparisonyieldsTS12S21ðoptÞTS1¼6󰀂þ6dþPþP

M1

þP

M2

ðPM1þPM2Þ2d

þPTS12S21ðoptÞ)TS12S21ðoptÞ6TS1.P6󰀂þ6dþPþ

22

WewillnowcompareTS2ðoptÞwithTS12S21ðoptÞ.

(1)IfPM1PPþPM2,then

(1.1)IfPM1P2󰀂þ4d,thisimpliesthatPþPM1P2󰀂þ4d.Then,TS2ðoptÞandTS12S21ðoptÞaregivenby

Eqs.(4a)and(5a)respectively.Hence,weconcludethatinthisregionTS2ðoptÞregionisgiveninEq.(4b).SincePþPM1P2󰀂þ4dandPM1þPM2P2dwehave:

TS12S21ðoptÞ

PþPM1þPM1þPM22󰀂þ4dþ2d

¼6󰀂þ8d¼TS2ðoptÞP5󰀂þ5dþ¼5󰀂þ5dþ

22

)TS2ðoptÞ6TS12S21ðoptÞ.

(1.3)IfPþPM1<2󰀂þ4d,TS2ðoptÞandTS12S21ðoptÞarepresentedinEqs.(4b)and(5b),respectively.

SincePM1þPM2P2dwehave:

TS12S21ðoptÞ

ðPM1þPM2Þ

P6󰀂þ8d¼TS2ðoptÞ)TS2ðoptÞ6TS12S21ðoptÞ.¼6󰀂þ7dþ

2

(2)ElseifPM1thatTS26TS12S21ðoptÞ,thenwecanconcludethatTS2ðoptÞ6TS12S21ðoptÞ.Wehavethefollowingcases:(2.1)IfPM1P2󰀂þ4d,thisimpliesthatPþPM1P2󰀂þ4d.TS2andTS12S21ðoptÞaregiveninEqs.(4e)

and(5a),respectively.WeconcludeeasilythatTS2ðoptÞ6TS2(2.2)IfPM1<2󰀂þ4dandPþPM1P2󰀂þ4d,TS2andTS12S21ðoptÞaregiveninEqs.(4g)and(5a),

respectively.SincePM1þPM2P2d,wehave:

TS12S21ðoptÞ

PþPM1þPM1þPM2PþPM1þ2dðPþPM1Þ

¼5󰀂þ6dþP5󰀂þ5dþ¼5󰀂þ5dþ

222)TS2ðoptÞ6TS26TS12S21ðoptÞ.

(2.3)IfPþPM1<2󰀂þ4d,thisimpliesthatPM1<2󰀂þ4d.Forthiscase,TS2andTS12S21ðoptÞaregiven

inEqs.(4f)and(5b),respectively.SincePM1þPM2P2dweconcludeeasilythatforthiscasealsoTS2ðoptÞ6TS26TS12S21ðoptÞ.SinceinallofthecasesTS26TS12S21ðoptÞ,weconcludethatS2hastheminimumcycletime.

h

H.Gultekinetal./EuropeanJournalofOperationalResearch174(2006)777–796789

Lemma3.If2PþPM1þPM262d,thenS1givestheminimumcycletime.

Proof.2PþPM1þPM262d)PþPM1<2󰀂þ4d.TS12S21ðoptÞisgiveninEq.(5b).WhenwecomparethiswithTS1giveninEq.(A.1),since2PþPM1þPM262d,wehave:

TS1¼6󰀂þ6dþPþP

M1

þP

M2

2PþPM1þPM2þPM1þPM2ðPM1þPM2Þ

66󰀂þ7dþ¼6󰀂þ6dþ

22

)TS16TS12S21ðoptÞ.

NowwewillcompareTS1withTS2ðoptÞ.Wehavethefollowingcases:

(1)AssumePM1PPþPM2.Since2PþPM1þPM262d,thenPM1<2󰀂þ4d.UsingTS2ðoptÞasgivenin

Eq.(4b)wehave:

TS1¼6󰀂þ6dþPþPM1þPM266󰀂þ6dþ2PþPM1þPM266󰀂þ8d

)TS16TS2ðoptÞ.

(2)IfPM1isgiveninEq.(4d).Thecomparisonincase1aboveisvalidforthiscasealso.Hence,weconcludethatTS16TS2ðoptÞ.hLemma4.IfPM1þPM2<2d,2PþPM1þPM2>2dandPþ2PM1þPM262󰀂þ6d,thenS12S21givestheminimumcycletime.

Proof.SincePM1þPM2<2d,thenPM1<2󰀂þ4d.IfPM1PPþPM2thenTS2ðoptÞisgiveninEq.(4b),whichis6󰀂þ8d.IfPM1(1)IfPþPM1P2󰀂þ4d,TS1andTS12S21ðoptÞaregiveninEqs.(A.1)and(5a),respectively.Observingthese

cycletimesweconcludethatTS12S21ðoptÞTS12S21ðoptÞ

Pþ2PM1þPM22󰀂þ6d

¼6󰀂þ8d)TS12S21ðoptÞ6TS2ðoptÞ.65󰀂þ5dþ¼5󰀂þ5dþ

22

(2)Otherwise,TS12S21ðoptÞisgiveninEq.(5b).Since2PþPM1þPM2>2d,wehave:

TS1

2PþPM1þPM2PM1þPM2ðPM1þPM2Þ

¼TS12S21ðoptÞþ>6󰀂þ6dþ2d=2þ¼6󰀂þ6dþ

222

)TS12S21ðoptÞWhenwecomparethecycletimeofS2withthecycletimeofS12S21,sincePM1þPM2<2d,usingEq.(5b)wehave:

TS12S21ðoptÞ¼6󰀂þ7dþðPM1þPM2Þ=2<6󰀂þ7dþ2d=2¼6󰀂þ8d)TS12S21ðoptÞ790H.Gultekinetal./EuropeanJournalofOperationalResearch174(2006)777–796

Lemma5.IfPM1þPM2<2d,2PþPM1þPM2>2dandPþ2PM1þPM2>2󰀂þ6d,theneitherS2orS12S21givestheminimumcycletime.

Proof.InthisregionsinceweassumedthatPM1þPM2<2d,wehave:

2󰀂þ6d6Pþ2PM1þPM22󰀂þ4d.

TS12S21ðoptÞisgiveninEq.(5a).WhenwecomparethiscycletimewithTS1giveninEq.(A.1),weconcludethatTS12S21ðoptÞAsaresultofthislemmaweshowedthatS1isdominatedinthisregion.OntheotherhandthefollowingexamplewillshowthatwecannotestablishanydominancerelationbetweencyclesS2andS12S21.

Example2.Letussupposethatwehavefouroperationswithatotalprocessingtimeof100,and󰀂=10andd=10.Becauseofthetoolingconstraints,oneoftheoperationswithaprocessingtimeof10mustbeprocessedonthefirstmachine,andanotheronewithaprocessingtimeof5mustbeprocessedonthesecondmachine.Therefore,PM1¼10andPM2¼5.Theremainingtwooperationswithatotaloperationtimeof85willbeallocatedtothemachines.Whenweobservetheparameters,weseethatLemma5isapplicabletothiscase.SincePþPM1P2󰀂þ4d,thecycletimeforS12S21isgiveninEq.(5a)andwithgivenparametersbecomes155.

ForS2,theallocationoftheoperationsbecomesimportant.Forthefirstcase,assumethatwehaveatotaloftwooperationstobeallocatedforwhich,oneoperationhasaprocessingtimeof50andtheother35makingatotalof85.CalculatingthecycletimeofS2giveninEq.(A.3),weget140,whichislessthanthecycletimeofS12S21.Forthesecondcase,assumethatwehaveagaintwooperationstobeallocatedforwhich,oneoperationhasaprocessingtimeof75andtheother10makingatotalof85.Now,thecycletimeforS2isequalto160.Sincethisisgreaterthan155,forthiscaseS12S21isoptimal.There-foreweconcludethatdependingontheallocationoftheoperationsofS2,eitherS2orS12S21canbeoptimal.

CombiningthefindingsinLemmas2–5,wenowprovidethemainresultofthispaper.Theorem5

(1)IfPM1þPM2P2d,thenS2givestheminimumcycletime,(2)Else,

(2.1)If2PþPM1þPM262d,thenS1givestheminimumcycletime,(2.2)Else,

(2.2.1)If2PM1þPM2þP62󰀂þ6d,thenS12S21givestheminimumcycletime,

(2.2.2)Else,dependingontheallocationoftheoperationsforS2,eitherS2orS12S21givesthemin-imumcycletime.RememberthatforthistheoremandtheproofweassumedthatPM1PPM2.Forthereversecase,theresultscaneasilybeadaptedinanalogywiththeaboveanalysisresultinginthefollowingcorollary:Corollary1.IfweassumethatPM1(2.2.1)IfPM1þ2PM2þP62󰀂þ6d,thenS12S21givestheminimumcycletime.

H.Gultekinetal./EuropeanJournalofOperationalResearch174(2006)777–796

PM1706050ε+3δ40302δ2010S1010δ1S12S212030402506070S23Sor SSor S12SS2 12 212 2180902ε+6δ100110120P791

Fig.3.OptimalRegionsforS1,S2andS12S21.3.3.Sensitivityanalysis

Inthissubsectionwewillperformasensitivityanalysisonparameterssuchastherobottransportationtimed,andtheloading(orunloading)timeofthemachines󰀂,andshowhowtheregionsofoptimalitychangewithachangeintheseparameters.WerepresentPM2asaPM1,where06a61.Thefollowingexamplewillbeusefulinordertoanalyzetheparametersgraphically.

Example3.Assumethat󰀂¼d¼10anda¼0,whichmeansthatPM2¼0.WecanshowtheregionsforthiscaseasagraphofPversusPM1asinFig.3.

Considerparameters󰀂,d,andaoneatatime.Theorem5,case1statesthatifPM1þPM2P2d,thenS2givestheminimumcycletime.Fromhereweconcludethatifthetransportationtimeiszeroornegligible,thenS2alwaysgivestheminimumcycletime.Thisislogicalsincewecanconsidertherobotasathirdmachinewhichisthebottleneckone.Then,themainconcernistominimizethewaitingtimeoftherobotinfrontofthemachines.Inordertoachievethis,incycleS2,whileprocessingofapartcontinuesononeofthemachines,therobotmakesotheractivities(suchastransportation,loadingorunloadingoftheothermachine,waitinginfrontoftheothermachine,etc.)withoutbeinglate.

Thedefinitionofn-unitcyclesstatesthateverymachineisloadedandunloadedexactlyntimes.Thustheloading/unloadingtimesareequivalentforallcycles.However,incyclesS2andS12S21,whileprocessingcontinuesononeofthemachines,therobotdoesnotwaitinfrontofthemachineandmakesotheractivitiesandwhentherobotreturnsbacktothemachinetounloadthereisapartialwaitingtimeinfrontofthismachine.Theloading/unloadingtimeaffectsthesepartialwaitingtimes.

WedefinedaasPM2/PM1andassumedthat06a61.WhenweincreasePM2from0toPM1,thisisinfavorofS2becauseincycleS2theoptimalallocationistheonewhichbalancestheprocessingtimesonbothmachinesandwhenPM2isclosetoPM1,theabilitytobalancetheprocessingtimesincreases.4.Conclusion

Inthispaper,westudiedthe2-machines,identicalpartsroboticoperationallocationproblemwithtool-ingconstraints.TheoperationallocationflexibilityisadirectconsequenceofassumingthatthemachinesintheroboticcellareCNCmachinesasisthecaseformachiningoperations.Theproblemistofindtheallo-cationoftheoperationstothemachinesandthecorrespondingrobotmovecyclethatjointlyminimizethe

792H.Gultekinetal./EuropeanJournalofOperationalResearch174(2006)777–796

cycletime.Asasolutiontothisproblem,weprovedinTheorem4thattheoptimalsolutioniseithera1-unitora2-unitcycle.InTheorem5,wepresentedtheregionsofoptimalityfortheserobotmovecycles.WeshowedthatthestudyofSethietal.(1992)becomesaspecialcaseofourstudy.Weconductedasensitivityanalysisonparameters.Suggestedfutureresearchdirectionsincludeconsideringnon-identicalmachinessothatthetimetocompleteaspecificoperationisdifferentforthetwomachines.Anothertopicistoconsideradual-gripperrobotwhichmanagesloadingandunloadingatthesametime.Acknowledgments

Theauthorswouldliketoacknowledgethethreeanonymousrefereesfortheirhelpfulguidanceonimprovingthepresentationandthecontentsofthepaper.ThisworkwassupportedinpartbytheScientificandTechnicalResearchCouncilofTurkeyundergrant#2211.AppendixA.Cycletimecalculations

WewillfindthecycletimesofS1,S2andS12S21foragivenk-allocationtype.LetusstartwithS1.Sethietal.(1992)provedthecycletimeofS1tobe:

TS1¼6󰀂þ6dþaþb;

whereaandbaretheprocessingtimesofthepartonthefirstandsecondmachinesrespectively.Withournotationthiscycletimeisthefollowing

TS1¼6󰀂þ6dþPþPM1þPM2

ðA:1Þ

anditdoesnotdependontheallocationtype.Sowhatevertheallocationis,thiscycletimeisthesame.NowconsiderS2.Sethietal.(1992)alsoprovidedthat:

TS2¼6󰀂þ8dþmaxf0;aÀð2󰀂þ4dÞ;bÀð2󰀂þ4dÞg;

whereaandbaredefinedasabove.WithourdefinitionstheaboveequationisthecycletimeofS2withone-allocationtypewhere,a¼PM1þP1ðr1Þandb¼PM2þPÀP1ðr1Þ.Thenthecycletimeofaone-allocationforcycleS2withournotationisthefollowing:

TS2ðr1Þ¼6󰀂þ8dþmaxf0;PM1þP1ðr1ÞÀð2󰀂þ4dÞ;PM2þPÀP1ðr1ÞÀð2󰀂þ4dÞg.

ðA:2Þ

Nowconsideratwo-allocationtypeforthecycleS2:forapartwiththefirstallocationtype,theprocess-ingtimeonthefirstmachineisPM1þP1ðr2ÞandonthesecondmachineisPM2þPÀP1ðr2Þ.Forapartwiththesecondallocationtype,theprocessingtimesonthefirstandthesecondmachinesarePM1þP2ðr2ÞandPM2þPÀP2ðr2Þrespectively.Then,thelongrunaveragecycletimetoproduceonepartwithcycleS2withaspecifictwo-allocationtyper2is:

TS2ðr2Þ¼6󰀂þ8dþ1=2ðmaxf0;PM1þP1ðr2ÞÀð2󰀂þ4dÞ;PM2þðPÀP2ðr2ÞÞÀð2󰀂þ4dÞgÞ

þ1=2ðmaxf0;PM1þP2ðr2ÞÀð2󰀂þ4dÞ;PM2þðPÀP1ðr2ÞÞÀð2󰀂þ4dÞgÞ.

Wecaneasilygeneralizethisforak-allocationtypeforthecycleS2asfollows:

TS2ðrkÞ¼6󰀂þ8dþ1=kðmaxf0;PM1þP1ðrkÞÀð2󰀂þ4dÞ;PM2þðPÀPkÞðrkÞÀð2󰀂þ4dÞgÞ

þ1=kðmaxf0;PM1þP2ðrkÞÀð2󰀂þ4dÞ;PM2þðPÀP1ðrkÞÞÀð2󰀂þ4dÞgÞþ1=kðmaxf0;PM1þP3ðrkÞÀð2󰀂þ4dÞ;PM2þðPÀP2ðrkÞÞÀð2󰀂þ4dÞgÞþÁÁÁþ1=kðmaxf0;PM1þPkðrkÞÀð2󰀂þ4dÞ;PM2þðPÀPðkÀ1ÞðrkÞÞÀð2󰀂þ4dÞgÞ.

ðA:4ÞðA:3Þ

H.Gultekinetal./EuropeanJournalofOperationalResearch174(2006)777–796793

NowletusconsidercycleS12S21.Thelongrunaveragecycletimeforone-allocationtypeforthecycleS12S21canbederivedasfollows:TheactivitysequenceofthisrobotmovecycleisA0A1A0A2A1A2.Initiallybothmachinesareemptyandtherobotisinfrontoftheinputbufferjuststartingtotakeapart.Therobottakesapartfromtheinputbuffertransportsittothefirstmachineandloadsit,(󰀂+d+󰀂);waitsinfrontofthemachinetofinishtheprocessingofthepart,(PM1þP1ðr1Þ);unloadstheparttransportsittothesecondmachineandloadsit,(󰀂+d+󰀂);returnsbacktotheinputbuffer,takesanotherpart,transportsittothefirstmachineandloadsit,(2d+󰀂+d+󰀂);travelstothesecondmachine,(d);waitsifnecessary,(w21);unloadsthemachine,transportstheparttotheoutputbufferanddropsit(󰀂+d+󰀂);travelstothefirstmachine,(2d);waitsifnecessary,(w11);unloadsthemachine,transportstheparttothesecondmachineandloadsit,(󰀂+d+󰀂);waitsforthemachinetofinishtheprocessing,(PM2þðPÀP1ðr1ÞÞ);unloadsthemachine,transportsittotheoutputbuffer,dropsthepartandreturnsbacktotheinputbuffersothattheinitialandthefinalstatesarethesame,(󰀂+d+󰀂+3d).Asaresult,totaltimetoproducetwopartsis:

TS12S21ðr1Þ¼12󰀂þ14dþPþPM1þPM2þw11þw21;

wherew11¼maxf0;PM1þP1ðr1ÞÀð2󰀂þ4dþw21Þgandw21¼maxf0;PM2þPÀP1ðr1ÞÀð2󰀂þ4dÞg.Inotherwords,w11þw21¼maxf0;PM1þP1ðr1ÞÀð2󰀂þ4dÞ;PM2þPÀP1ðr1ÞÀð2󰀂þ4dÞg.Hencethecycletimeforone-allocationforthecycleS12S21is:

12󰀂þ14dþPþPM1þPM2þmaxf0;PM1þP1ðr1ÞÀð2󰀂þ4dÞ;PM2þPÀP1ðr1ÞÀð2󰀂þ4dÞg

.TS12S21ðr1Þ¼

2

ðA:5ÞNowconsiderthecasewhenwehavetwo-allocationtypes:

12󰀂þ14dþPM1þPM2þP1ðr2ÞþðPÀP2ðr2ÞÞþw12þw21

;TS12S21ðr2Þ¼

2

wherew12¼maxf0;PM1þP2ðr2ÞÀð2󰀂þ4dþw21Þgandw21¼maxf0;PM2þPÀP1ðr2ÞÀð2󰀂þ4dÞg.Inotherwords,

TS12S21ðr2Þ¼1=2ð12󰀂þ14dþPM1þPM2þP1ðr2ÞþðPÀP2ðr2ÞÞÞþ1=2ðmaxf0;PM1þP2ðr2Þ

Àð2󰀂þ4dÞ;PM2þPÀP1ðr2ÞÀð2󰀂þ4dÞgÞ.

ðA:6Þ

AppendixB.ProofofTheorem4

Thefollowingdefinitionwillplayacrucialroleintheforthcomingcontext.

Definition5.State0isdefinedtobethestateinwhichbothmachinesareemptyandtherobotisinfrontoftheinputbuffer.

Consideranyn-unitrobotmovecycleduringwhichState0isencountered.Clearly,theallocationsimmediatelyprecedingandthoseimmediatelyfollowingthisstatecanbetreatedascompletelyindependentfromeachother.Asfarasthecycletimecomputationsareinvolved,thecontributionoftheportionofthecyclebetweentwoState0Õsissimplyadditive.Thisobservationdeservesfurtherattention:

Fact1.Theaveragecycletimeofann-unitrobotmovecycleissimplytheaverageofthecycletimecorrespondingtoasub-cyclebetweentwoState0Õsandthecycletimeoftheremainingcycleafterthesub-cycleisextracted.

Afterinspectingthecycleswehaveintroducedthusfar,itiseasytostatethat:

794H.Gultekinetal./EuropeanJournalofOperationalResearch174(2006)777–796

Fact2.S1cyclestartsandendswithState0.S12sequencestartswithState0andS21sequenceendswithState0.

Withtheseobservations,wearenowreadytoproceedwiththeproofofTheorem4.

Proof.Halletal.(1997)showedthatanyn-unitrobotmovecyclecanberepresentedbythefourrobotmovesequences:S1,S2,S12andS21.However,notallofthesesequencescanfollowanyothersinceotherwisethebasicfeasibilityassumptionsofCramaetal.(2000)statingthattherobotcannotloadanalreadyloadedmachineandcannotunloadanalreadyemptymachinemaybeviolated.Fig.1depictsthefeasibletransitionsfromonesequencetoanother.Nowletusconsideranyn-unitrobotmovecyclewiththeoptimalallocationtype.Initsgenerality,weassumethiscycletocontainatleastoneofthesefourrobotmovesequences.Theallocationoftheoperationsdoesnotaffecttheloading/unloadingandtransportationtimesbutonlyaffectstheprocessingtimeswhichinturnaffectthewaitingtimesoftherobotinfrontofthemachines.LetusfirstanalyzeoneoftheS1cycleswithinthisn-unitrobotmovecycle.UsingFacts1and2aboveweconcludethattheallocationforthiscycledoesnotaffecttheremainingpartofthecycle.Also,asmentionedpreviously,thereisnoallocationproblemforS1cycle,andthewaitingtimeforS1isPþPM1þPM2,independentoftheallocation.WhenweremovetheactivitysequenceA0A1A2,correspondingtoS1fromtheactivitysequenceofthen-unitrobotmovecycle,wegetanewfeasibleðnÀ1Þ-unitrobotmovecycleforwhichtheoptimalallocationfortheremainingpartsdoesnotchange.AssumethatthereareatotalofzS1cycleswithinthen-unitrobotmovecyclewherez¼0;1;...;n.LetTnÀzbethecycletimeofthenewðnÀzÞ-unitrobotmovecycle,sayCnÀz,whichisattainedbyremovingtheactivitysequencesofallS1cycles.Hence,thecycletimeofourn-unitrobotmovecycleis:

zÃTS1þðnÀzÞÃTnÀz

.Tn¼

n

ThisequationstatesthatTnPminfTS1;TnÀzg.

NowletusconsiderCnÀz.FromFig.1weseethatbetweentwoS12sequencesoneS21sequencemustbeperformed.BetweenoneS12andoneS21anynumberofS2sequencescanbeperformed.ThuswecanpartitionCnÀzintosub-cycleseachofwhichstartswithS12performsanumberofS2ÕsandendsupwithS21.Furthermore,asstatedasFact1above,theallocationforsuchcyclesdoesnotaffecttheallocationfortheremainingpartofthecycleandisnotaffectedbytheallocationoftheremainingpartofthecycle.Thecycletimeofthewholen-unitrobotmovecycleisaconvexcombinationofthecycletimesofthesesub-cycles.LetTibethecycletimeoftheithsub-cyclewiththeoptimalallocationtypethen,clearly,TnÀzPminifTig.Henceforth,TnPminfTS1;minifTigg.

NowletusconsideranysuchcyclewhichstartswithS12,performsatotaloflS2Õsl¼0;1;...andendsupwithS21.Notethatthisisanðlþ2Þ-unitcycle.LetusrepresentthiscycleasS12ðlÀS2ÞS21.Sinceineverycycleeachmachineisloadedandunloadedanequalnumberoftimes,theaverageloading/unloadingtimetoproduceonepartforallcyclesareequaltoeachother,namely,6󰀂.RepeatingcycleS2ltimesrequiresatotalof8ld.RepeatingS12onetime,whichhasanactivitysequenceofA0A1A0,requires5dandthefollowingactivityofthissequencecanonlybeA2whichrequiresanadditionaldtotravelbetweenfinalstateofS12(firstmachine)totheinitialstateofthenextsequence(secondmachine).InasimilarwayrepeatingS21(A2A1A2)onetimerequires5dandanadditional3dtotravelbetweenthelaststateofS21(outputbuffer)toinitialstateofthefollowingsequencewhichmuststartwithactivityA0(inputbuffer).ThentheaveragetraveltimetoproduceonepartwiththecycleS12ðlÀS2ÞS21is:

6dþ8ldþ8d8lþ14

¼d.

lþ2lþ2

Thelastcomponentinourcycletimerepresentationsisthetotalwaitingtimeoftherobotinfrontofthemachines.Wecanfindthewaitingtimeasfollows:AssumeforthecycleS12ðlÀS2ÞS21usingkallocationtypesisoptimalandconsiderthespecificallocationrk.Thefirstpartwillbeproducedaccordingtothecycle

H.Gultekinetal./EuropeanJournalofOperationalResearch174(2006)777–796795

S12whichimpliesafullwaitingtimeinfrontofthefirstmachine:PM1þP1ðrkÞ,andwillbeprocessedaccordingtoS2onthesecondmachinewhichmeansapartialwaitingtimeinfrontofthesecondmachine:w21¼maxf0;PM2þðPÀP1ðrkÞÞÀð2󰀂þ4dÞg.ThenextlpartswillbeprocessedaccordingtoS2cycleonbothmachines.Thepartialwaitingtimeforthesecondpartonthefirstmachineis:w12¼maxf0;PM1þP2ðrkÞÀð2󰀂þ4dþw21Þg.Thenwehave:

w12þw21¼maxf0;PM1þP2ðrkÞÀð2󰀂þ4dÞ;PM2þðPÀP1ðrkÞÞÀð2󰀂þ4dÞg.Proceedinginthesamewayforallparts,totalwaitingtimetoproducel+2partsis:PM1þPM2þP1ðrkÞþðPÀPðlþ2ÞðrkÞÞ

þmaxf0;PM1þP2ðrkÞÀð2󰀂þ4dÞ;PM2þðPÀP1ðrkÞÞÀð2󰀂þ4dÞgþmaxf0;PM1þP3ðrkÞÀð2󰀂þ4dÞ;PM2þðPÀP2ðrkÞÞÀð2󰀂þ4dÞgþmaxf0;PM1þP4ðrkÞÀð2󰀂þ4dÞ;PM2þðPÀP3ðrkÞÞÀð2󰀂þ4dÞgþÁÁÁþmaxf0;PM1þPðlþ1ÞðrkÞÀð2󰀂þ4dÞ;PM2þðPÀPlðrkÞÞÀð2󰀂þ4dÞgþmaxf0;PM1þPðlþ2ÞðrkÞÀð2󰀂þ4dÞ;PM2þðPÀPðlþ1ÞðrkÞÞÀð2󰀂þ4dÞg.

IntheaboveequationletusinsertP1(rk)andðPÀPðlþ2ÞðrkÞÞintothefirstandlastmaxtermsrespectively.Bythischangeallothermaxtermsremainthesamebutthesetwobecome:

maxfP1ðrkÞ;PM1þP2ðrkÞþP1ðrkÞÀð2󰀂þ4dÞ;PM2þPÀð2󰀂þ4dÞg

and

maxfPÀPðlþ2ÞðrkÞ;PM1þPÀð2󰀂þ4dÞ;PM2þðPÀPðlþ1ÞðrkÞÞþðPÀPðlþ2ÞðrkÞÞÀð2󰀂þ4dÞg.

Ã

UndertheoptimalallocationwemusthaveP1ðrÃkÞ¼0andPðlþ2ÞðrkÞ¼P.ThismeansforthefirstpartallocatingalloperationsthatareinsetOtothesecondmachineandforthelastpartallocatingthemtothefirstmachine.Furthermore,sinceweassumedthatPM1PPM2,lettingPðlþ1ÞðrÃkÞ¼0doesnotchangethecycletime.Asaresultofthese,thelastmaxtermoftheaboveequationbecomes:

maxf0;PM1þPÀð2󰀂þ4dÞ;PM2þPÀð2󰀂þ4dÞg¼maxf0;PM1þPÀð2󰀂þ4dÞg.

Afterincludingtheloading/unloadingandtraveltimes,thecycletimeofS12ðlÀS2ÞS21underoptimalallocationrÃkbecomes:

6󰀂þ

ð14þ8lÞ1

dþðPM1þPM2Þ

ðlþ2Þðlþ2Þ

ðB:1ÞðB:2ÞðB:3ÞðB:4ÞðB:ðlþ1ÞÞðB:ðlþ2ÞÞ

M2

þ1=ðlþ2Þðmaxf0;PM1þP2ðrÃþPÀð2󰀂þ4dÞgÞkÞÀð2󰀂þ4dÞ;P

M2þ1=ðlþ2Þðmaxf0;PM1þP3ðrÃþðPÀP2ðrÃkÞÀð2󰀂þ4dÞ;PkÞÞÀð2󰀂þ4dÞgÞM2þ1=ðlþ2Þðmaxf0;PM1þP4ðrÃþðPÀP3ðrÃkÞÀð2󰀂þ4dÞ;PkÞÞÀð2󰀂þ4dÞgÞþÁÁÁ

þ1=ðlþ2Þðmaxf0;PM1Àð2󰀂þ4dÞ;PM2þðPÀPlðrÃkÞÞÀð2󰀂þ4dÞgÞþ1=ðlþ2Þðmaxf0;PM1þPÀð2󰀂þ4dÞgÞ.

LetWðS12S21Þrepresentthewaitingtimeoftwo-allocationforcycleS12S21withoptimalallocationrÃk,

M11

whichinEq.(3)wasfoundtobe:WðS12S21Þ¼2ðmaxf0;PþPÀð2󰀂þ4dÞgÞ.Then,the(B.(l+2))ndcom-2

ponentintheaboverepresentationisðlþWðS12S21Þ.Considerlines(B.2)–(B.(l+1))above.Theysharethe2Þsamepatternasthewaitingtimecomponentcorrespondingtoanl-allocationtypeforthecycleS2in(A.4).LetWðS2Þbethiswaitingtimecomponentin(A.4)whenweplugintherespectiveallocationsfrom(B.2)–

l

(B.(l+1)).Thesummationofthecomponents(B.2)–(B.(l+1))isthenlþWðS2Þ.Inconclusion,2796H.Gultekinetal./EuropeanJournalofOperationalResearch174(2006)777–796

TS12ðlÀS2ÞS21¼

2ð6󰀂þ7dþP

M1þPM2

2þWðS12S21ÞÞþlð6󰀂þ8dþWðS2ÞÞ

.

lþ2

Inparticular,thecycletimeofS12ðlÀS2ÞS21isaconvexcombinationofthecycletimesoftwo-allocationforS12S21andl-allocationforS2.Clearly,

TS12ðlÀS2ÞS21PminfTS2ðoptÞ;TS12S21ðoptÞg.

Finally,wehavemanagedtoshowthatthecycletimeofthen-unitcyclewestartedoutwith,TnPminfTS1;TS2ðoptÞ;TS12S21ðoptÞg.h

References

Brauner,N.,Finke,G.,1997.FinalResultsontheOne-cycleConjectureinRoboticCells.Internalnote,LaboratoireLEIBNIZ,

InstitutIMAG,Grenoble,France.

Crama,Y.,vandeKlundert,J.,1997.Cyclicschedulingofidenticalpartsinaroboticcell.OperationsResearch45,952–965.Crama,Y.,vandeKlundert,J.,1999.Cyclicschedulingin3-machineroboticflowshops.JournalofScheduling4,35–54.

Crama,Y.,Kats,V.,vandeKlundert,J.,Levner,E.,2000.Cyclicschedulinginroboticflowshops.AnnalsofOperationsResearch96,

97–124.

Dawande,M.,Geismar,H.N.,Sethi,S.P.,2002a.Dominanceofcyclicsolutionsandchallengesintheschedulingofroboticcells.

Workingpaper,UniversityofTexasatDallas,toappearinSIAMReview.

Dawande,M.,Sriskandarah,C.,Sethi,S.P.,2002b.Onthroughputmaximizationinconstanttravel-timeroboticcells.Manufacturing

andServiceOperationsManagement4,296–312.

Dawande,M.,Geismar,H.N.,Sethi,S.P.,Sriskandarajah,C.2003.Sequencingandschedulinginroboticcells:Recentdevelopments.

Workingpaper,UniversityofTexasatDallas,toappearinJournalofScheduling.

Garey,M.G.,Johnson,D.S.,1976.ComputersandIntractability:AGuidetotheTheoryofNP-completeness.W.H.Freeman.

Gray,A.E.,Seidmann,A.,Stecke,K.E.,1993.Asynthesisofdecisionmodelsfortoolmanagementinautomatedmanufacturing.

ManagementScience39,549–567.

Hall,N.G.,Kamoun,H.,Sriskandarajah,C.,1997.Schedulinginroboticcells:Classification,twoandthreemachinecells.Operations

Research45,421–439.

Hall,N.G.,Kamoun,H.,Sriskandarajah,C.,1998.Schedulinginroboticcells:Complexityandsteadystateanalysis.European

JournalofOperationsResearch109,43–65.

King,R.E.,Hodgson,T.J.,Chafee,F.C.,1993.Robottaskschedulinginaflexiblemanufacturingcell.IIETransactions25,80–87.Kise,H.,Shioyama,T.,Ibaraki,T.,1991.Automatedtwo-machineflowshopscheduling:Asolvablecase.IIETransactions23,10–16.Miller,R.K.,Walker,T.C.,1990.FMS/CIMSystemsIntegrationHandbook.TheFairmontPress,Lilburn,GA.

Sethi,S.P.,Sriskandarajah,C.,Sorger,G.,Blazewicz,J.,Kubiak,W.,1992.Sequencingofpartsandrobotmovesinaroboticcell.

InternationalJournalofFlexibleManufacturingSystems4,331–358.

Sriskandarajah,C.,Hall,N.G.,Kamoun,H.,1998.Schedulinglargeroboticcellswithoutbuffers.AnnalsofOperationsResearch76,

287–321.