S t u d y o n D e p e n d a b l e S c h e d u l i n g o n M a n u f a c t u r i n g S y s t e m s b a s e d
o n H y b r i d E v o l u t i o n a r y A l g o r i t h m s
Wan-Ling LI
2016 02
De p e nd a b i l i t y m e a n s r e s i l i e n ce to b e j u s t i f i a b l y t ru s t e d on s e rv i c e s i t d e l i v er s ; i t i s a n in t e gr a t i ng c on ce p t th at enc o m p a s s e s t he f o l l o w in g a t t r i b u t e s a s r o b u s tn e s s a n d s t ab i l i t y. I n r ec e n t f l ex i b l e a n d j u s t i n t i m e m a nu f a c tu r i ng sy s t e m s , i t b ec o m e s m o re i m p or t a n t t o h a n d l e d i s t ur b a n c e s s u ch a s in t e rn a l ev en t of u n ex p ec t e d m a ch i n e b r e a kd o wn a n d ex t e rn a l ev e n t o f e xc e p t i on a l e m e rg en t j o b ( s ) in s e r t i on t o m a k e m a nu f a c tu r in g sc he d u l e m o r e f e a s i b l e a n d d e p en d a b l e . F ur t h er m o re , unc e r t a i n ty o f m a ch in e s ’ pr o c e s s i ng t i m e i s a l s o ne e d t o b e t a k en in t o co n s i d er a t i o n f o r de p e n d a b l e s ch e du l e. Th e r e f or e, D e p en d a b l e s ch e du l i ng m e t ho d s ar e r e q u ir e d t o h a v e f un c t i on a l i t i es t h a t c a n re c ov er or i g i n a l s ch e du l e r e ac t i ve l y ag a i n s t i n t er n a l a n d e x t er n a l d i s t ur b a n c e s c o n d i t i o n s m en t i o n e d a b o ve w i t h m i n i m i z i ng t o t a l t a r d in e s s o f j o b s a s w e l l a s m in i m i z i ng d i ff e r enc e o f j o b s ’ s t a r t i n g t i m e f or m th a t o f or i g i n a l s ch e d u le ( i t i s c a l l e d r e ac t i v e s c he d u l in g ) a nd it i s a l s o re q u i r ed t o m a k e b a t ch j o b s c he d u l e m o r e r o bu s t a g a i n s t m a ch i n e pr o c e s s i ng t i m e u nc er t a i n t y s o t h a t m in i m i z e s p er f o r m an c e d ec re m e n t i n J u s t in t i m e pr o du c ti on ( i t i s c a l l e d r o bu s t s c he d u l i ng ).
To f i n d t he r e a c t i ve a nd r o b u s t s ch e du l i ng m e th o d s m en t i o ne d a b o ve un d e r th e d i s t ur b a n c e s in v a r i ou s t y p e s o f m an u f ac t u r ing s y s t e m s i s p a r t ic u l ar l y d i f f i cu l t b e c au s e i t i s c o m p l ex an d c o m p l i c a t e d co m b i n a t o r i a l o p t i m i z at i o n pr o b l e m u n d er unc e r t a i n t i e s i n m a nu f a c tu r in g s y s t e m s a nd i t i s a t e ch n ic a l c h a l l en ge t o r e a l i z e s uc h s ch e du l i ng m e t h o d s a g a in s t u nc er t a i n t i e s i n d i v er s e an d f l ex i b l e t y p e s o f m a nu f a c t ur i ng s y s t e m s .
Th i s d i s s e r t a t i o n f oc u s e s o n d e p en d a b l e s ch e du l i ng in m a nu f a c tu r in g s y s t e m a n d p r op o s e s i nn ov a t i v e me t h o d s th a t s a t i s f y t he a f or e m e n t i on e d re q u i re m e n t s o f r e a c t i ve a n d ro b u s t s c he d u l in g m en t i o n e d a b o v e. N ov e l tw o m e t ho ds s ch e d u l in g b a s e d on h y br i d ev o l u t i on a ry a l g o r i th m a r e a d dr e s s e d i n th i s s t u d y. On e i s v er s a t i l e m e t ho d o f r e ac t i v e s c he d u l i ng o n j u s t in t i m e p r o du c t i on an d t he o th er on e i s r o b u s t s ch e du l i ng m e t h od o n j u s t i n t i m e b a t c h pr o du c t i on un d er unc e r t a i n p ro c e s s i ng t i m e .
F ir s t l y, r e q u ir e m en t s o f d ep e n d a b l e sc h e du l i ng in m a nu f a c tu r in g s y s t e m s ar e d e s c r i b e d, s e c on d l y f unc t i o n a l r e q u ir e m en t s o f re a c t i v e s ch e du l i ng an d ro b u s t sc h e du l i n g ar e f or m u l a t e d a s m a t h e m at i c a l m o d e l s , an d t h i rd l y, n o ve l sc h e du l i ng a l g or i t h m b a s e d o n h y br i d ev o l u t i on a ry a lg o r i th m s a r e p r op o s e d t o a ch i e v e r e ac t i v e an d r o b u s t s ch e du l i ng a n d a r e e v a lu a t e d t hr ou gh c a s e s t u d ie s, r e s p ec t i v e l y.
Th i s d i s s e r t a t i o n i s or g an i z e d in t o 6 c h a p t er s . 2
C h a p t e r 1 [ I n tr o d uc t i o n] d e sc r i b e s t he b a c kg ro un d , m o t i va t i on , an d o b j e c t iv e s o f t h e r e s e a rc h s t u d y.
C h a p t e r 2 [ L i t e r a t ur e R ev i ew ] g i v e s a l i t e r a tu r e r ev i ew on co nc e p t a n d t h eo ry of d e p en d a b l e s ch e d u l in g u n d er u nc er t a i n t i e s en v ir on m e n t s .
C h a p t e r 3 [ Pr o p o s e d D e p en d a b l e Sc h e du l i ng M e t ho d s] pr o p o s e s d e pe n d a b l e s ch e d u l in g m e t h o d s w h ich co n si s t o f r e ac t i v e sc h e du l i n g m e t ho d a n d ro b u s t sc h e du l i ng m e t ho d . Th e f or m u l a t i o n of un e x pe c t e d e m er ge nc y j o b on f l ex i b l e j o b - s h o p s y s t e m ( F J S ) a n d t he f o r mu l a t i o n o f un p l a nn e d m ac h i ne b r e a kd o wn on ce l l u l a r m an u f ac t ur in g sy s t e m ( C M S ) a re p r o po s e d t o c o p e w i t h n o t on l y in s e r t i ng un p l a n ne d e m er g en cy j o b on F J S w i th m in i m i z i ng s u m o f t ar d in e s s o f ex p r e s s jo b and a l s o e a c h j o b , s u m of d i f fe r en c e o f e a ch op e r a t i o n s t a r ti n g t i m e b e t w e en or ig i n a l a n d r ep a i r e d sc h e du l e , an d in cr e a s i ng m a ke s p a n , bu t a l s o r e a s s i g n i n g a f f ec t e d op e r a t i o n j o b s f or n on - d i s r up t i v e CM S a g a in s t i n t er n a l e v en t o f un ex p ec t e d m ac h i ne br e a k d ow n t o m i n i m i z e a v er a ge tar d i n e s s , a ve r ag e d i f fe r en c e o f s t a r t i ng t i m e o f e a ch b a t ch j o b an d e a ch o p er a t i o n b e t we e n or i g in a l a n d r ep a i re d s ch e du l e , i nc re a s i n g m a k e s p a n , a ver a ge n u m b er o f i n t er c e l lu l a r m ov e m e n t o f b a t ch j o b s , a n d av er a g e un u s e d c e l l c a p ac i t y. T h e s e r e a c t iv e s ch e du l i ng pr o b l e m s f or f l ex i b l e m a nu f ac t u r in g s y s t e m s ar e f or m u l a t e d a s o p t i mi z a t i o n p ro b l e m s o f m i x e d i n t eg er pr o gr a m m i ng . T h e f o r mu l a t i o n of unc e r t a i n p r oc e s s i ng t i m e s on F J S i s pr e s e n t e d a s a r o bu s t o p ti m i z a t i o n p ro b l e m b y u s i ng sc e n ar i o - b a s e d a p pr o a ch wh i ch i s a d o p t e d t o g e n er a t e a r o bu s t s ch e du l e . A r o bu s t ev a l u a t i o n f unc t i o n i s m o d e le d b a s e d o n a gg re g a t i o n- b a s e d o p t i m i z a t i o n a p pr o a ch w h er e t wo o b j ec t i v e s ar e a ggr e g a t e d. A b i - o b j e c t iv e ev a l u a t i o n m e a s ur e o f r o bu s t s ch e d u l e a i m s a t m in i m i z i ng th e e xp e c t e d m a k e s p an un d er po s s i b l e s c e n ar i o s a nd a l s o m i n i m i z in g v ar i a b i l i t y o f i t .
C h a p t e r 4 [R e a c t iv e Sc he d u l i ng o n Ju s t In Ti m e P ro d uc t i o n w i t h Un p l a n ne d a n d Un e x pe c t e d D i s t u r b an c e s ] p r e s en t s th e v e r s a t i l e a n d a d a p t i v e H S A B P SO a l g or i t h m o f H y br i d i z e d B in a ry P a r t i c l e Sw a r m Op t i m i z a t i o n ( B P SO ) an d Si m u l a t e d An n e a l i ng ( S A ) m e t ho d i s p ro p o s e d t o r e s o l ve i n t ern a l ev en t o f un e x p ec t e d m a ch i ne b r e a k d own s o n C M S , b u t a l s o ex t e rn a l ev en t o f u n p l a nn e d e m erg e ncy j o b o n F J S t o m i n i m i z e m en t i o n e d r e qu i r e m en t s . Th e B P SO i s u s e d t o ex p l or e n e a r o p t i m a l f e a s i b l e s o l u t i on w i t h m i n i m i z i ng a b ov e r e q u i r e m en t s ; m o re o ve r, v ar i a b l e n e ig h b or ho o d s e a rc h e s ar e a d d e d in t o SA t o en h an c e qu al i t y o f s o l u t i on s s o a s t o e s c a p e ou t fr o m l o c a l o p ti m u m .
Th e p r op o s e d H S A B P S O m e t ho d c o m p a r ed w i t h M e m e t i c A lg o r i th m (M A ) , m o d i f i ed A O R ( m AO R ), a nd R i gh t - S h i f t R e s ch e du l i ng ( R S R ) , t h e
3
r a t e o f j o b t a r d i ne s s i s s m a l le r a s 7. 5 7 % , 11. 6 3 %, a n d 1 5 . 4 5 % , re s p e c t iv e l y. M or e ov er, ch a ng e r a t e o f s t a r t i ng t i me of j o b o p er a t i o n i s s m a l l e r a s 8 . 0 6 %, 1 6 . 5 3 % , a n d 2 0 . 3 3% , r e s p ec t i v e l y. B e s i d e s , c a lc u l a t i o n t i m e i s r e du ce d 2 1 . 5 3% u s in g pr o p o s e d m e th o d . In a d d i t i on , i t i s a l s o u s e d t o r e s o lv e a f f ec t e d j o b o p e r a t i on s ag a i n s t in t e rn a l d i s ru p t i o n of un e xp e c t e d m ac h in e b re a k do wn . Th e p ro p o s e d H SA B P S O co m p a r e d w i t h B r a nc h an d B o un d ( B & B ) , m AO R , a n d R S R , ch a ng e r a t e o f b a t ch j o b s t a r t i ng t i m e on e a ch ce l l i s s m a l l e r a s 3 . 7 5 %, 5 . 0 1 % , an d 4 . 5 3 %, r e s p e c t iv e l y. B e s i d e s , ch a ng e r a t e o f j o b o p e r a t i o n s t a r t i n g t i me i s s m a l l e r a s 3 . 7 1 %, 8 . 4 4 %, and 1 4 . 3 1 % , re s p ec t i v e l y. C l e ar l y, H S A B P S O p ro d uc e s b e t t e r s o lu t i o n s in c o m p a r i s on w i t h t he co nv en t i o n a l m e t ho d s re g ar d i ng t he m e a s ur es o f r o bu s t n e s s a n d s t a b i l i t y a g a i n s t un ex p ec t e d d i s t ur b a nc e s.
C h a p t e r 5 [ R o b u s t Sc h e du l i ng Me t h o d o n B a tc h F J S P un d e r Un c er t a i n Pr oc e s s i ng Ti m e s ] pr e s e n t s a n e nh a n ce d t ec hn i q u e o f r o b u s t f l ex i b l e j o b - s h o p s s ch e du l i ng m e t h o d i s pr o p o s e d w h ich c an b e a p p l i e d t o a d d re s s t h e r o bu s t b a t c h m a nuf a c t ur i ng s ch e d u l in g pr o b l e m w i t h unc e r t a i n p ro c e s s i ng t i m e s . Mo re ov e r, a hy b r i d i z i ng m e t h o d of HG A B P S O w h ic h c on s i s t s o f hy b r i d i z e d G en e t i c A l go r i th m ( G A) a n d B P S O i s c a p a b l e o f m in i m i z i ng b o t h e x pe c t e d m a k e s p a n by B P S O an d a l s o t he c o rr e s p on d i ng v a r i a nc e u nd e r p o s s i b l e sc e n ar i o s b y GA re s p e c t iv e l y. M o r e ov er, GA u s e s s i m p l e s t r a t e gy o f p o pu l a t i o n - b a s e d s e a rc h m e t h o d w i t h ge n er a l pr i n c i p a l of s ur v iv a l o f th e f i t t e s t a nd i t h a s d i v erg e n t s e a rc h s p a c e o f p o pu l a t i o n . Th e re f or e , t h e pr o p o s e d en h an c in g t e ch n i q ue i s a b l e t o e ff e c t iv e l y i m p r o ve r o b u s t ne s s a nd v ar i a b i l i t y, a n d i t i m p l i e s m i n i m i z i ng tw o ob j ec t i v e s s o t h a t n u m b er o f j o b or d er s c an c o m p l e t e ly b e f i l l e d i n un ce r t a i n e nv i r on m e n t s .
Th e pr o p o s e d H G A B P SO m e t h o d c o m p a r e d w i t h c o nv en t i o n a l m e t ho d of M S% R o b-h GA a nd B P SO, t he in cr e a s i n g r a t e o f m a k e s p a n i s s m a l l e r a s - 1 . 5 2 % an d 3 . 0 5 % , a n d t he r o b u s t ne s s i s gr e a ter 6. 7 9 % a n d 6 . 2 5 %, r e s p e c t iv e l y. To d e m on s t r a t e t h e e ff e c t iv e ne s s o f th e pr o p o s e d HG A B P S O m e t h o d, r e s u l t in g p er f or m a n ce a r e r e g a r de d a s t he m a i n a t t r i b u t i on f r o m t he f o r m a l i z i ng r o b u s t s c he d u l i ng m e th o d t h a t i s cr i t i c a l l y re q u i re d t o en h an c e r o bu s t n e s s a n d r e du c e v a r i a b i l i t y c a p a b i l i t i e s , s i m u l t a n e ou s l y.
C h a p t e r 6 [ C on c l u s i on s ] c o nc l u de s th e d i s s e r t a t i o n a n d g i v e s a d i s cu s s i o n t o f u t ur e re s e a r ch o n r o b u s t s ch e d u l i ng p ro b l e m u n d er unc e r t a i n r e s o ur ce s , a n d ro b u s t - re a c t i ve sc h e du l i ng pr o b l e m ag ai n s t unc e r t a i n p ro c e s s i ng t i m e an d un p l a nn e d a d d i t i o n of e m er ge nc y j o b s .
4
