TELKOM NIKA , Vol. 11, No. 5, May 2013, pp. 2508 ~   2515   ISSN: 2302-4 046           2508      Re cei v ed  De cem ber 1 2 , 2012; Re vi sed  March 11, 20 13; Accepted  March 20, 20 13   Automated Guide Vehicles Dynamic Scheduling  Based on Annealin g Genetic Algorithm      Zou Gan* 1 ,   Li Tao 1, 2 ,  Qi n Ying 1,2   1 Mechan ical  a nd Electric al E ngi neer in g Col l ege, K unm in g Univers i t y   of Scienc e an d T e chno log y   Kunmi ng, 65 01 18, PR Chi na.   2 Chin a Ship bu il din g  T r ading (Kunmi ng) Co., Ltd,650 05 1, PR Chin a.   *Corres p o ndi n g  author, e-ma i l : zouga n@h o t m ail.com* 1 , zxs t @126.com 2       Abstrac t   Dispatc h in g au tomat ed g u id e d  veh i cles (AG V s)  is the co mmo n  a ppro a ch  for AGVs schedu lin g   in practic e , the informatio n  ab out loa d  arriva l s  in  adva n ce w a s not used to  opti m i z e th e pe rforma nce of th e   auto m ate d  gu i ded ve hicl es system (AGVsS). Accord ing  to the chara c teristics of the AGVsS, th e   math e m atic al  mo de l of AGVs schedu li ng w a s establ ish ed.  A heuristic a l g o rith m cal l ed A nne ali ng Ge ne tic   Algorit h m  (AGA) w a s prese n t ed to d eal w i t h  the AG Vs s c hed uli ng  prob le m, an d a ppl i ed the  al gorith m   dyna mical l y by  usi ng  it re peat edly  un der  a c o mbi ned  ro l l i n g o p ti mi z a ti on   strategy. the  p e rformanc e of   the   prop osed a ppr oach for AGVs schedu lin g w a s comp are d  w i th the dispatch ing rul e s by si mu lati on. Resu lt s   show ed th at the  appr oac h p e rforms  sig n ifi c antly b e tter t han  the  disp at chin g ru les  an d prov ed  that  it is   really  effective for AGVsS.    Key w ords :   a u tomated  gu i de ve hicl es ( A GVs), dyna mic  sc hed ul in g, rolli ng  opti m i z at io n strategy,  ann eal in g ge n e tic alg o rith m ( A GA)        Copy right  ©  2013 Un ive r sita s Ah mad  Dah l an . All rig h t s r ese rved .       1. Introduc tion  Automated  G u ided V ehi cl es  (AGVs)  a r e u n man n e d  mea n s of  inplant tran sportation   whi c h are commonly used in facilities  such as  warehouses, manuf acturi ng plants, terminal s and   distrib u tion  centers. AGV s  in crea se  e fficienc y  and  red u ce  co sts by  helpi ng  to auto m ate  a  manufa c turi n g  facility o r   wareh o u s e [1].  Appli c ation  o f  AGVs  ha s b een  bro ade n ed  sin c e th e l a te   20th centu r y. In the past few decade s, much rese a r ch has be en d e voted to the improveme n t of  AGVs syste m  (AGVsS).  Basically, the releva nt  issue s  of AGVsS can b e  divided into  the  followin g  mai n  cate go rie s : guide -path   desi gn, e s tim a ting the  req u ired  num ber of AGVs, id le  AGVs p o sitio n ing, AGV s   sche duling,  ba ttery m ana ge ment an d  co nflict re sol u tion. The s e  issues  relate  to diffe rent level s  of  the d e ci sio n   makin g   pro c e s s [2]. As on e  of the  en abli ng te chn o logi es,  sched uling of  AGVs have  attracte d co n s ide r abl e atte ntion. The A G Vs  sch eduli ng is  re spo n sible  for managi ng  AGVs efficiently to guarantee se rve  j obs a s  qui ck as possibl e. Many rules  or  algorith m s for the sch eduli ng of AGVs h a ve been p r o posed [2-5].   In gene ral,  AGVsS can  be divide d  into two  main  catego ries:  ce ntrali zed  and   dec ent rali ze d  co nt rol  sy st e m s.  Th e cent ralized syste m   u s es  info rm ation avail a ble at th e  ce ntral  controlle r whi l e the decentralize d  syste m  dispat ch e s  A G Vs ba se d o n  local info rm ation availabl e   at the d e ci sio n  mom ent [3] .  In practi ce,  due to   thei r e fficiency,  cen t ralize d   cont rol sy stem s a r e  more  po pula r . Since  di spat chin g rule s a r e quite  st raig htforwa r d  an d ea sy to  use .  A wid e  vari e t y  of dispatchin g rule s in clu d ing  nea re st-workstation -first  (NWF ), n eare s t ve hicl e first (NVF)  and   modified firs t  c o me firs t s e rved (MOD-FCFS) ar e use d  for centralized cont rol AGVsS [4]. Ba sed   on the   ways  in which tran spo r tation  re que sts  ar e a ssi gne d, Egb e lu h a ve divi ded  dispatchi ng  rule s into two  catego rie s : load-i n itiated  disp atch i ng rules in  whi c h  jobs at wo rkstation have t h e   prio rity to cl aim vehi cle s  and  vehi cle - initiat ed  dispatchi ng  rule s in  which v ehicl es have  the   prio rity to clai m jobs [5]. Di spat chin g is  related to imm ediate d e ci si ons  su ch  as  whe r e a ve hi cle  sho u ld be se nt to at a  spe c ific mome nt. Howeve r,  if  advan ce load  arrival information is kn o w n,  they are outp e rform ed by sche duling a p p roa c h e s [2].  In the literat ure, vehi cle  routing  pro b l e ms  with time wind ows  (VRPTW) hav e been  studie d  exten s ively.  B.L. Golden  et al.  provid e a  re view of v ehi cle ro uting  with time wi ndo ws  inclu d ing  the Pick-up and Delie ry  Probl em  with  Tim e  Wind ow  (PDPTW), multi - Travel Sale sman  Evaluation Warning : The document was created with Spire.PDF for Python.
                               ISSN: 23 02-4 046     TELKOM NIKA  Vol. 11, No . 5, May 2013 : 2508– 251 5   2509 Problem  with  Time Wind o w (m -TSPT W) and solutio n s app roa c h e s [6].They me ntion two ma in   types of optimization al go rithms for V R PT W: dyna mic pro g ram m ing and b r anch-a n d - bo und.  Both method s a r e very t i me co nsumi ng an d  can not  solve practical  probl ems within an  accepta b le time limit. Xu  et al. propose the co lumn -gen eration a l gorithm to solve VRPTW.  In   orde r to d eal  with practi cal - size proble m s. They u s e  several h e u r ist i cs to  gen erat e col u mn s wit h   negative re d u ce d co sts and elimin ate unattra c tive column s by sop h i s ticate d col u mn  manag eme n t scheme s  [7].  Wenfe ng  Wa ng et al.  pr e s ent an i m proved ge netic al gorithm  to sol v e  the VRPTW [8]. Corde au e t  al. summari zed  several  o f  the most important an d mode rn heu ri stics  for vehicle ro uting pro b le m [9], Victor  Pillac et  al. provide a surv ey on solutio n  approa che s  for  dynamic vehi cle ro uting problem s [10].Two main  ap proache s inclu de an ada pt a t ion of the static  solutio n  and  an implem ent ation of stat ic algorithm s u nder a  rolling  hori z on.   After studying  the literature on  the vehicl e sched uling,  we fi nd t hat  most  st u d ie s con c e r n   external tran spo r t sy stem s. Fe w aut h o rs u s e m e thod s succe s sfully depl oyed for  external  transpo rt pro b lems for i n te rnal t r an spo r t  like  th e AGV s S. The  probl em of dyn a mi c  scheduli ng  o f   AGVs h a s  no t attracted  m any re se arch ers [2]. Since  the sch eduli ng ap proa ch  has  bee n u s ed  widely a nd ef ficiently for e x ternal tra n sp ort. We   devel op such sch e duling  strate g y  for AGVsS  in   this pa per. T he main  purpose is to in vestigat e the  potential co ntribution  of the sche duli n g   approa ch for  AGVs. AGVs sch eduli ng p r oble m  is si m ilar to the vehicle  sched uling pro b lem f o r  external tra n s po rt. Ho we ver, it also has  some   di fferences  su ch a s  the o b jective s , tra v e l   distan ce s an d load a rrival  rate. There i s  so me  litera t ure on  sche duling met h o d s for AGV s   [3 ]  [11]. Several obje c tives are also u s e d , inclu d ing min i mizing the a v erage lo ad  waiting time  and   minimisi ng e m pty vehicle  travel dista n ces, but  they focu s on  static problem s. An AGVsS is a  system  with  a high degree of  uncertai nty, short  travel times and, often, high  vehicle utilization   rates. In AGVsS, normally,  we only kno w  a limit ed numbe r of jobs in advan ce.  The sched ule of  vehicle s  sho u ld be u pdat ed wh en n e w  tran sp ortat i on re que st informatio n arrives. Thi s  p aper  focu se s mainl y  on dynamic sch edulin g p r oble m  of  AGVs, adapts  su ccessful dyna mic sche dulin g  approa ch for AGVsS, and comp are s   its perfo rma n ce s with co mmon dispat chin g rule s by  s i mulation.  The remai n d e r of thi s  pa per i s  o r ga ni zed  as follo ws: In  se ctio n 2, we de scrib e  the  mathemati c al  model, Ann e a ling G eneti c  Algorithm  (A GA) an d the  rolling o p timization st rategy  o f   AGVs  sched uling  pro b lem .  Re sults an d  discu s sion  a r e p r e s e n ted  in sectio n 3. we  co ncl ude  the  pape r in Secti on 4.      2. Rese arch  Metho d   2.1.   Mathem atical Model  of AGV s  Sch e duling  In AGVsS, AGVs picks-up load s at  some l o catio n s an d deliv ers th em to their  destin a tion s satisfying ce rtain  time-win dows.  the A G Vs  scheduli ng proble m  can be fo rmul ated  as  a V R PTW. m-TSPT W i s  a   spe c ial  case  of th e V R PTW in  whi c h th e ve hicl e capa citie s   are   infinite [6]. We formul ate the sch eduli n g pro b le m fo r AGVs a s  a  m-TSPTW  by proje c ting ti me- wind ows at delivery stait ons to the  corre s p ondin g  pick-u p st ations a nd a  pick-up a n d  a   corre s p ondin g  delivery job  is co nsi dere d  logica lly as a singl e job-node. We ma ke the follo wi ng   assumptio n s  for the studyi ng AGVsS:     All AGVs have unit-loa d  ca pacity.    AGVs ope rat e  contin uou sl y without bre a kd own.    There are n o  traffic pro b le ms.     AGVs ch oo se  the sho r test  path to pick u p  and delive r  load s.    AGV loading  and unl oadin g  times are fixed and con s idere d  in trav el times.     AGVs ca n al ways p a rk at their drop-off locatio n s.     Only one de p o t in AGVsS.  the following notations will  help in the descripti on of formulation of AG Vs scheduling problem.   D  — AGVs  depot.  N — set of jobs.   K — s e t of AGVs .  ijk x — take the value 1 if job  i  and job  j are served by AG V  k  Conse c uti v ely, and 0 otherwise.  i e  — relea s e time of job  i .  Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM NIKA   ISSN:  2302-4 046     Auto m a ted  Guide Vehicles Dynam ic Scheduling Based on Annealing Genetic …  ( Z ou Gan)   2510 i l  — the latest pick-u p time allowed of job   i .  i s  —  pick-up ti me of job  i .  ij t  — T h e  travel  time from j o b - nod e  i  to  j , eq uals the  trave l  time from th e o r igin  of jo b   i  to the   destin a tion of  job  i , plus the  travel time from the destin a tion of job  i  to the origin of  job  j .  Dk s  — the s t art time of AGV  k  at the AGVs depot.  kD s  — the arrival  time of AGV  k  at the AGVs depot.   B  — a sufficien tly large positi v e numbe r.     Normally, mi nimizin g  the  averag e job   waiting  tim e  i s  the m o st i m porta nt obj ective of  AGVs sche du ling pro b lem.  The AGVs  scheduli ng prob lem can b e  formulate d  as f o llows:      N i i i e s N mize i min 1  (1)     s ubjec t to:    N i , x K kN j ijk   1  (2)     K k , N i , x x N D j jik N D j ijk  (3)     K x x K kN i Dik K kN j jDk      (4)     K k , N j , x B s t s Djk j Dj Dk 1  (5)     K k , N j , i , x B s t s ijk j ij i 1  (6)      K k , N i , x B s t s iDk kD iD i 1  (7)     N D i , l s e i i i  (8)     Con s trai nts (2)-(4 ) form a  multi-commo dity flow fo rm ulation. The  constraint  (5 )  sho w s that if an  AGV  k serve s  job  j  after job  i , the const r ain t   j ij i s t s must be satisfied. Con s traints (5 )-(7 )  ensure fea s ib ility of  the sch edule. Equat i ons (9) i s  time-wi ndo w for  job  i .   For the stati c  AGVs sched uling problem , we  assume  that all AGVs start at the  AGVs  depot.  Ho we ver, du ring  the p r o c e s s  of optimizat io n, AGVs m a y start at  an y load’ s d r op -off  station. The r efore, we ne ed to modify  the formul ation to refle c t this by re pla c in g (4 ) and  (6 )  by  con s trai nts (9 ) and (10)  re spectively, wh ere  k D  is the virtual startin g  d epot of AGV  k .    K x x K kN j jDk K kN i ik D k      (9)     K k , N j , x B s t s jk D j j D k D k k k 1  (10 )         Evaluation Warning : The document was created with Spire.PDF for Python.
                               ISSN: 23 02-4 046     TELKOM NIKA  Vol. 11, No . 5, May 2013 : 2508– 251 5   2511 2.2. Anneali ng Gene tic Algorithm (AGA)  Thoug h opti m al solution s to AGVs  sch edulin g probl em can b e  o b tained  usi n g  exact  method s, the  comput ation a l time requi red to so lve  this pro b le m to optimality is prohibit i ve .  Heu r isti c met hod s su ch a s  Gen e tic Algorithm s (GA ) ,Simulated  Annealin g (S A) often prod uce   optimal  o r  ne ar optimal sol u tions  in a re aso nabl e am ount of  co mp uter time.  He uristi c m e tho d s  have been p r oved useful in a variet y of search a nd  optimizatio n  probl em s over the years. But  most of si ngl e heu risti c  al gorithm s h a ve their o w n  shortcomin gs i n  the optimi z ation [12]. In many  probl em s, GA may have a tenden cy to conve r g e   towa rd s lo cal  optima rath er than the glo bal   optimum  of t he p r o b lem [ 13]. The  exe c ution  time  of SA is sen s itive to the  scal e of th e p r o b l e m.  In dealin g wit h  larg e-scale  issue,  the  co mputational ti me of SA for  getting a  sati sfacto ry solut i on   is not acce ptable [14]. Accordin g to the cha r a c teri stics of AGVsS, we propo se a  hybrid algo rithm   calle d Ann e a ling  Geneti c  Algo rithm  (AGA) to  op timize AGV s  sche duling  pro b lem. A G A  facilitates the exhaustive and para ll el treatment of the problem  an d to increase t he probability of  finding glob al  minimums in  a reasona ble  computatio n time.  The propo se d AGA is describ ed a s  follows:  Step1:  Initial i ze th e pa ra meters, i.e., pop ulation  size  p opsize , Maximum g ene ra tions  of  evolution gen MAX ,crossover probability  c p ,mutation rate   m p , initial tem perature  0 T ,  temperature cooli ng  coefficient  q , final te mperature  end T .  Step2:  ge nerate i n itial popul ation  0 P , compute indi viduals’ fitness val u e    popsize , , , i f i 2 1 .   Step 3:  set cycle co unt variable  0 gen .   Step 4:  ope ration of sel e ction, cro s so ver and m u ta tion, com p u t e the fitness value of n e w  individual  ' i f , if i ' i f f ,new in dividua l is acce pted,  otherwise , n e w individ ual  is a c cepted  with a   probability  ) T ) f f exp(( p i ' i .   Step 5:  if  MAXgen gen , then  1 gen gen , go to step 4, otherwi se ,go to step 6.   Step 6:  if  end i T T ， Termin ate th e alg o rithm  a nd p r int the  solution, oth e rwise,  i i qT T 1 ， go   to step 3.  The fram ewo r k of the AGA  is given in Figure 1.   In this  pap er,j obs have  be e n  num be red   according  to i n crea sing  job s ’ relea s e  tim e , a   solutio n  is e n co ded a s  a  chromo som e  formed  of multiple se gments.  kj x  rep r esents AGV   k serv e s  jo b j ,a ch romo som e  of the A G VsS sch e d u ling p r obl e m  ca n be  e x presse d a s   （ , 0 , , , , , 0 , , , i 0 2 22 21 1 12 11 t s i i i i i ， ， 0 , , , , , 0 , 2 1 mw m m i i i ） with   0 repre s ent s the  AG Vs de pot. Fo r  example, the  chromo som e    0 , 8 , 7 , 0 , 6 , 5 , 4 , 0 , 3 , 2 , 1 , 0 expre ss  3 AGVs se rve  8 jobs, It indicate s that  AGV 1 s e rves    0 , 3 , 2 , 1 , 0  in se quen ce, AGV 2 serves  0 , 6 , 5 , 4 , 0  in se que nce a nd AGV  3 serve s    0 , 8 , 7 , 0  in seq uen ce  respe c tively. Roul ette-whe el schem e is  applie d in the  sele ction p r o c ed ure.   The metho d   of gene ration  of the initial popul ation,  the crossove r o perato r  an d  mutation op erator  in this pap er  are o r igin ated  from literature [8].    2.3. Rolling Optimiza tion  Strate g y  for  AGVs Sche duling  In AGVsS, we may kno w  informatio n a bout  job s ’ arrival in advance. Base d on  this  informatio n, we can u s e rolling optimi z ation stra te gy to sche dule  AGVs. Whe n  an AGV start s  to  serve  a job, it  has to fini sh  it. Cancellatio n  of  job s  is n o t allowe d. Normally, there  are two rolli n g   optimizatio n strategie s , i.e. rolling  by time and  ro lli ng  by the num be r of job s  [2]. F o r the  rollin g  by  time, we sch edule all  kn o w n job s  d u rin g  a time pe ri od  H , Dependi ng on diffe re nt con d itions,   the numbe r o f  sche duled j obs can diffe r signifi cantly  for the time  hori z on  H . Howev e r, AGVs  only follow th e re sultin g  schedul e du rin g  a time  peri o d  1 H h After the time period  h  the  system invo kes the  sche duling al go rithm agai n  to  sched ule al l kno w n jo bs in the pe ri od   H h h , . The pro c e s s stop s when  all jobs have  been  finishe d . Rolling o p timization  stra tegy by  Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM NIKA   ISSN:  2302-4 046     Auto m a ted  Guide Vehicles Dynam ic Scheduling Based on Annealing Genetic …  ( Z ou Gan)   2512 the num ber  of jobs i s   simil a r to the one rolling by  time, the differences  are rol ling time peri od  H ,  h  repla c in g b y  the rolling n u mbe r  of the jobs  M , m  respe c ti vely (sho wn i n  Figure 2).           Figure 1. The  framework of  t he anneali n g geneti c  alg o rithm (AGA )      i t 1 i t im m 1 i     Figure 2. Roll ing optimization strat egies illustrati on (by time - left a nd by the number of jobs- right)      As sh own in  Figure 2, in rolling by time  po licy, the n u mbe r  of sch edule d  job s  a t  each   step ca n differ signifi cantly.  Wh en   too m any  job s   are t a ke n into  a c count, the  ru n n ing tim e  of t he  sched uling al gorithm may   increa se sig n ificantly  an d  may not m eet the real  time sche duli n g   requi rem ents.  Whe n  we  use rollin g opti m ization  stra tegy by the nu mber  of jobs,  sometim e s, t he  numbe r of j o bs  we  kn ow i n  advan ce  m a y be n o t en ough. In thi s   pape r, we p r opo se a  com b ined  rolling optimi z ation st rategy  .When the  numb er of jobs known in  adv ance is suffici ent  M i , we   apply the rolling optimi z ati on strategy b y  the numbe r of jobs, othe rwi s e  rolling  by time policy is  use d .  Evaluation Warning : The document was created with Spire.PDF for Python.
                               ISSN: 23 02-4 046     TELKOM NIKA  Vol. 11, No . 5, May 2013 : 2508– 251 5   2513 3. Results a nd Analy s is  In this  study, the layout  we  have  sele cte d   is  sh own in  Figure 3.  We  model th e A G VsS  in Plant 9 si mulation  software. In our  experim en t, the job s ’ inter-arrival times for the loadi ng   station s  a r e expon entially distribute d   with inter arrival  times equal   80 70 60 50 40 5 4 3 2 1 ， ， ， ， ， ， ， ， seconds. T h e probability that  a load is  sent f r om a   loadin g  statio n  i  to a unlo ading  station   j  are  ij p ( n p ij / 1 , n  is th e numb e r of  unloadi ng  station s ).Fo r  the numbe r  of AGVs, 3 levels have b een u s ed  6 5 4 ， ， . Informatio n a bout job s ’  arrival s  is  kn own in a d van c e of 240  se con d s.  the sp eed of AGVs is 2 m/s. The para m eters for   the combin e d  rolli ng  strategy and  the AGA:  250 H ,  25 M ,   8 . 0 ,   30 popsize ,   200 gen MAX ,   6 . 0 c p , 05 . 0 m p ,  1000 0 T ,  9 . 0 q ,  1 end T .   The m a in  pe rforma nce  cri t erion  is min i mizing  the   averag e jo b  waiting  time. The   se con dary  ob jective is mini mizing  the m a ximum  job  waiting time. Result s of the  experim ents  are   sho w n in Ta b l e 1.          Figure 3. The  experime n tal  AGVsS layout      Table 1. Re sults of differe nt sch eduli n g  strategi e s  (±  rep r e s ent s the 95% confid ence interval )  No.AGVs   4 5 6  Method   MOD-  FCFS   NVF   ROLL -   AG A   MOD-  FCFS   NVF   ROLL -   AG A   MOD-  FCFS   NVF   ROLL -   AG A   A v er-wai t  (s )  192.8   (±5.6)   136.5   (±3.8)   65.3  (±2.2)   132.5   (±3.1)   87.9  (±2.5)   34.8  (±1.8)   93.6  (±2.7)   68.4  (±2.3)   17.2  (±1.1)   Max - wait  (s )  958.4   1267.2   792.3   407.6   563.4  354.7   187.7  239.3   130.6   No.  AGVs: nu mber of  AGVs;  A v er -wait:averag e  job waiti n g  t i me ;  Ma x - w a i t :  ma x i mu m j o b  w a i t i n g  t i me ;   MO D - FC F S :   m odified first com e  first served; NVF:  nearest ve hicle first;  RO LL-AG A: Rolli ng optim i z a t ion strat egy based on annealing   genetic algorithm.      Table 1 a nd  Figure 4 sh o w  that the Mo dified First Come First Served (MO D -F CFS) i s   the wo rst stra tegy for the A G VsS in  all th ree  ca se s. Th e Ne arest Ve hicle  First (NVF) pe rform s  a   bit better tha n  the  MO D-F C FS. Th e av erag e j ob  wa iting time s a nd the  maxi mum jo b  wai t ing   times obtai ni ng by Rolli ng  optimizatio n strategy  b a se d on Anne ali ng Gen e tic A l gorithm  (RO L L - AGA) are si g n ificantly sm a ller than th e  MOD-F C FS a nd the  NVF strategy, whi c h are  amon g  th e   best di spat ch ing rul e s in li teratures. Th e ROL L -AGA  sho w s  goo d  performan ce  for the AGVs  sched uling a nd prove to b e  robu st to different ope rati ng co ndition s.  In general, we have found  that the dispat chin g rule s such as MO D-F C FS an d NVF   don’t perfo rm  well for the  AGVsS. The disp atchi ng rules di sp atch  AGVs only base d  on di sta n ce   betwe en the l oad s and th e  AGVs or th e  jobs’  waiting  time, the information ab out  jobs a rrival s  in   advan ce i s   n o t co nsi dere d  an d in crea se th e ave r a ge a nd m a ximum jo b  wai t ing times.  T h e   Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM NIKA   ISSN:  2302-4 046     Auto m a ted  Guide Vehicles Dynam ic Scheduling Based on Annealing Genetic …  ( Z ou Gan)   2514 AGVsS is a  system of u n certainty, ba se d on th e info rmation a bout  job s  a rrival s   in advan ce, t he  prop osed RO LL-AGA, whi c h sha r e s   th e  advant a g e s  of both SA and GA, redu ce s the ave r age  and maximu m job waiting  times greatly  and imp r ove the syste m  pe rforma nce.      4 A G V s 5 A G V s 6 A G V s 0 20 40 60 80 10 0 12 0 14 0 16 0 18 0 20 0 A v er a g e  j o b w a i t i n g t i m e s     M O D - FC FS NV F RO L L - A G A 4 A G V s 5 A G V s 6 A G V s 0 200 400 600 800 10 00 12 00 14 00 Ma x i mu m j o b  w a i t in g  t i me s     M O D - FC FS NV F RO L L - A G A     Figure 4. The  performan ce  of the three sche duling  strategie s       4. Conclusio n   AGVsS is b e comi ng p o p u lar in  auto m atic mate ri als h andlin g  system s, flexible  manufa c turi n g  sy stem s a n d  even   contai ner-ha ndling  appli c ation s .  AGVs sched uling  i s  a cru c ial  probl em to improve the e fficiency of the AGVsS.  In this pape r, we have di scussed the A G Vs  sched uling issue s  in AGVsS. Usi ng si m u lation, we p r ove that the  MOD-F C FS  rule and the NVF   rule, both  a m ong the  be st dispatchin g rule s in lit eratu r e, pe rform s  not so  well in  simul a tion   environ ment. They dispatching AGVs  o n ly base d  on  distan ce b e twee n the loa d s an d the A G Vs  or the j o b s ’ waiting time, th e inform ation  about lo ad a rrival s  in a d vance is  not u s ed to  optimi z e   the pe rforma nce  of the  A G VsS. Lite ra ture  on  external transpo rt ha s  sho w n  that  sche duli n g   vehicle s  may  lead to bette r pe rform a n c e than di spat chin g them. In this pa pe r, we Apply thi s  to   the AGVsS, f o rmul ate the   AGVsS  sche duling  proble m  a s  a  m-T SPTW.   AGV s S is  an  s y s t em   with  a hig h  d egre e  of  un certainty, We  prop ose AGA  to deal  with t he AGVs  sch edulin g probl em,  and a pply thi s  he uri s tic  dynamically by  usin g it  re pea tedly unde r a  combi ned  roll ing optimi z ati on  strategy. We  comp are the  performan ce  of the pr opo sed a pproa ch with the di spat chin g rul e s.  Re sults  sho w  that the approa ch  pe rforms sig n ifica n t ly better t han the dispat ching rul e s. From  pra c tical  p o in t of view, it   make s the  p r opo se d  sch edulin g a pproach m o re  a ttractive fo r t h e   AGVs S.      Ackn o w l e dg ement  This wo rk wa s  supp orted by  the  intern ational   coo p e r ation p r oj ect s  of China  Mi nistry   of scie n ce an d techn o logy  (201 0DFB70 700).       Referen ces   [1]    Mantel  RJ a n d  La nde w e er d  HRA. Des i g n   and  op erati o n a l co ntrol  of a n  AGV s y stem .  Internatio na l   Journ a l of Prod uction Eco n o m ics . 1995; 4 1 (3 ): 257-26 6.  [2]    Le-An h T .   Intelli ge nt Contro l of Vehic l e-B a s ed Inter nal  T r ansport S y stems. PhD the s is, Erasmu s   Univers i t y  R o tterdam. 20 05.   [3]    T a lbot L. Desi gn an d perfor m ance a n a l ysi s  of  multi station aut omated  gui ded  v ehic l e  s y stems. Ph.D   T hesis, Univer site Catho liq ue  de Louv ai n. 2003.   [4]    Le-An h T and  De Koster, R(M) BM. A  revie w   of desi gn  and co ntrol of   automated g u i de d vehic l e  s y stems.  Euro pea n Jour nal o f  Operationa l R e searc h . 200 6; 171(1): 1– 23.   [5]    Egbe lu PJ  a n d  T anchoc o J M A. Char acter i zati o n  of  auto m ated  gui de d  veh i cle  dis p a t ching  rul e s.  Internatio na l Journ a l of Prod uction R e se arch . 1984; 2 2 (3): 359- 374.   Evaluation Warning : The document was created with Spire.PDF for Python.
                               ISSN: 23 02-4 046     TELKOM NIKA  Vol. 11, No . 5, May 2013 : 2508– 251 5   2515 [6]    BL Gol d e n  a n d  AA Ass ad.  Vehic l e  Ro utin g: Metho d s  an d Stud ies.  Nor t h-Holl an d,  Els e vier  Scienc e  Publ ishers. 19 88; 65-8 4 .  [7]    Xu H, C hen Z L , Raja gop al  S and Arun ap uram S. Solvin g a practica l p i ckup a nd d e li ver y  pr ob lem.   T r ansportati on Scienc e . 200 3; 37(3): 347- 36 4.  [8]    W enfeng  W a n g ,  Z untong W ang, F e i Qi ao . An Impr ove d  Gen e tic A l g o rithm for  Ve hicle  R outi n g   Probl em w i t h   time w i nd o w .  Internatio na l S y mp osi u m o n  Co mp ut er S c ienc e a n d  C o mputati o n a l   T e chno logy ,  S han gh ai . 200 8;  189-1 94.   [9]    Cord eau, JF   Gendre au, M  Lap orte, G Po tvin, JY Seme t F .  A guide  to veh i cle  routi ng h eur istics.   Journ a l of the  Operatio nal R e search Soc i ety . 2002; 53( 5): 512-5 22.   [10]    Victor Pill ac, Michel Ge ndr e au, Christe l l e  G uéret, André s  L. Medag lia.  A revie w  of d y n a mic ve hicl e   routin g pro b le ms.  Europea n Journ a l of Ope r ation a l Res ear ch . 2012; 2 25( 1): 1-11.   [11]    Vis IFA, De K o ster, R(M) BM   and Savelsber gh MWP. Minimum vehi cle fleet siz e  under  time- w indo w   constrai nts at a contain e r terminal.  T r ans port a tion Sci enc e . 200 5; 39(2): 24 9–2 60.   [12]    KC T an, LH Lee, QL Z hu, K Ou, Heuristic met hods for v ehicl e routi ng  prob lem  w i th ti me  w i n d o w s.   Artificial Intel lig ence i n  Eng i ne erin g . 200 1; 15 (3): 281-2 95.   [13]    Yi Z han g,  Xi a opi ng  Li, Qia n  W ang. H y b r id  gen etic a l g o ri thm for perm u tation fl o w  sh o p  sche d u lin g  problems w i th  total  fl o w  time  minimiz a tion.  Europ e a n  Jour nal of Operati o nal R e searc h . 200 9; 196( 3):  869 –8 76.   [14]    Cha ndra Sek h ar Pedam all u , Linet Ozdam ar. In vestigatin g a h y brid si mulate d ann e a lin g an d loca l   search a l g o rit h m for constrain ed o p timiza tion.  Euro pea n  Journa l of Operati ona l Res earch . 2 008 ;   185( 3): 123 0–1 245.     Evaluation Warning : The document was created with Spire.PDF for Python.