352 Tesu-o-Hagané Vol. 97 (2011) No. 6 Tesu-o-Hagané Vol. 97 (2011) No. 6 * * * * * A TZBM-Based Algorihm for Flow Shop Scheduling Problem Considering he Decision Maker s Preference Tesuo SAWARAGI, He XU, Yaie TIAN, Yukio HORIGUCHI and Jidong REN Synopsis : Nowadays seel manufacuring pays a criical aenion o on-ime delivery and invenory reducion. In our sudy, we propose a heurisic algorihm o solve he hybrid flow shop scheduling problem (HFSP) considering reducing oal ardiness and invenory ime. In order o achieve a feasible soluion in limied compuaional ime, he algorihm is based on Three-zone Buffer Managemen (TZBM) approach. TZBM approach combines he Drum Buffer Rope (DBR) mehod proposed in heory of consrains (TOC), wih a conrac ne proocol in muli-agen sysem (MAS). The effeciveness of he proposed algorihm is shown by simulaion resuls comparing wih he resuls obained by a Tabu search (TS) algorihm. In he producion field, a shipmen buffer is se beween he due dae and he shipping ime in order o avoid possible lae shipmen. The size of shipmen buffer is always decided according o he experience of a sysem operaor who has responsibiliy o draw up a producion schedule. Wherein, an operaor needs o ake a decision considering rade-off beween on-ime delivery and invenory reducion. Therefore, a new ineracive decision suppor sysem is proposed which is based on he wo-sage TZBM approach. The operaor needs o make his/her udgmen wheher an opimal soluion shown by he sysem is preferable or no, hen o change he rade-off beween he wo conflicing obecives. The sysem needs o compue anoher opimal soluion according o udgmen given by he operaor. Under he resul of numerical experimens, o inegrae he experience of operaors wih he compuaional inelligence of sysems proves o be an effecive scheduling mehod. Key words : producion engineering; hybrid flow shop scheduling problem (HFSP); heory of consrains (TOC); hree-zone buffer managemen (TZBM); ineracive decision suppor sysem. 1) 1) 1 (HFSP) 22 10 1823 1 6 (Received on Oc. 18, 2010; Acceped on Jan. 6, 2011) (Kyoo Universiy, Honmachi Sakyo Kyoo 606 8501) 38
TZBM 353 Tian (TZBM) 2) 2 TZBM HFSPTZBM 2) TOC (Theory of Consrains) DBR (Drum Buffer Rope) 3 2,3) TZBM (k 1,2,...K ) (2) P 1 p i (3) D 0 ST (ST D 0 ) HFSP (1) (2) (3) (4) ST D 0 Fig. 1 3 HFSP S, L, R, C LT HFSP (1) N J i (i 1,2,...,N) H P ( 1,2,...,H) P 1 P K M k Fig. 1. Esimaed sar and compleion ime. 39
354 Tesu-o-Hagané Vol. 97 (2011) No. 6 (1) P 1 S 1 S S p S 0 1 1 (1) (2) P L N L p / K i i 1 (2) Fig. 2. Mehod of Drum-Buffer-Rope (DBR). (3) P R R [ D ( S L )] 0 H H (3) (4) P C C S L R C D 1 (5) P LT LT C S (4) (5) (6) P p p p / N N i 1 (6) D sum I dis 2 C ih P H J i N sum D max{, C D } (7) i 1 i 0 ih 0 I max { C } min { C } dis ih 1 i N 1 i N H H J L ih L (8) Fig. 2 TOC DBR 4) TZBM 0 Fig. 3. TZBM approach. Green-Zone (GZ), Yellow-Zone (YZ) Red-Zone (RZ) (Fig. 3) GZ YZ RZ DBR RZ RZ GZ, YZ RZ RZ HFSP 2 (Fig. 4) TZBM 3 40
TZBM 355 RZ : ε LT LT (11) Fig. 4. Two sages of TZBM approach. STEP 1 STEP 2 STEP 3 STEP 2 TZBM 2 D 0 ST 3 3 1 LT LT GZ LT LT e YZ LT e RZ RZ GZ : LT LT 0 (9) YZ :0 LT LT ε (10) e g d (0 e ST D 0 ) g d 3 3 2 l Cl C (12) (14) GZ, YZ, RZ RZ GZ : C C 0 ( 1 l K ) (12) YZ :0 C C ε (13) RZ : ε C C l l l (14) 3 3 3 S GZ YZ RZ CB p 2 CB p CB p CB p CB p M CB S GZ YZ RZ CB M ( 1,2,...,H) Sep 1 Dispaching rule SPT (Shores Processing Time) S 0, e 0 Sep 2 (1) (8) LT D sum I dis (9) (11) GZ, YZ RZ Sep 3 CB p {P 1 H} f (Sep 6)max {LT LT } P (P CB p ) Sep 4 Sep 4 CB M {M k 1 k K } f P P 41
356 Tesu-o-Hagané Vol. 97 (2011) No. 6 CB P Sep 3 Sep 5 P {S 1 } a a 0 1 P Backward Scheduling Forward Scheduling P D 1 sum D sum D 1 sum D sum I dis 1 Idis S 1 S S 1, CB P f CB M f Sep 8 D sum I dis 1 Sep 7 Sep 6 CB P D 0 D 0 d 10 d d 1, D g D 0 e D 0 CB P f CB M f Sep 8 d 10 D 0 ST Sep 7 * * Sep 5 1 Sep 4 Sep 8 * 1 Sep 5 Sep 5 Sep 4.1 CB M {M k 1 k K } f P Sep 4.4 max k {C k } M k (M k CBM ) Sep 4.2 M k CBkSep J 4.1 M k J ki (J ki CBk J ) Iima 5) 0.75 J ki C k {S 1 } b b 0 b 0 Sep 4.3 J ki CBk J Sep 4.2 Sep 4.3 M k {S 1 } b 1 LT 1 LT LT 1 LT RZ 1 RZ {S 1 } a (a 0) Sep 5 J ki CBk J Sep 4.2 Sep 4.4 Sep 3 (TS) Glover 6,7) Chen 8) dispaching rule SPT s 0 TS s 0 s bes-so-far s b s n 4 s n s b N(s)Chen 8) TS Firs Come Firs Served (FCFS) rule 42
TZBM 357 Chen 8) bes-fi (J i, J ) Firs In Fis Ou (FIFO) rule 7 D sum I dis 1 s n s b D 1 sum Dsum D 1 sum DsumI 1 dis I dis Taillard 9) Table 1TS D sum 0 D TS TS 3 Table 2 TS Table 1 TS D sum I dis Table 3 Table 4 Table 3 Table 4 2 (1) 3TS TS Table 1. Experimen daa of proposed mehod. D sum 0 I dis (2) 6TS TS 3 D sum 0 D sum 0 I dis Glover Chen TS TS 2TZBM Fig. 55100 2 Table 3. Comparison of oal ardiness D. Table 2. Experimen daa of TS. Table 4. Comparison of variaion of invenory ime. 43
358 Tesu-o-Hagané Vol. 97 (2011) No. 6 Fig. 6. Desiring level of he operaors A and B. Fig. 5. Search process of soluion space for he proposed mehod. D sum I dis D sum I dis 10 12) 13) ST MS I dis MS I dis A B Fig. 6 A A MS f MS * D 0 ST 50% B B MS f MS * 75% Upper bound of f * MS for A D 0 (ST D 0 ) 0.5 Upper bound of f * MS for B D 0 (ST D 0 ) 0.75 f MS * D 1 sum Dsum D 1 sum DsumI 1 dis I dis max{ms 1,MS } f * MS I 1 dis I dis MS I dis (15) (16)MS n MS I dis n dis before afer ν MS before afer ν dis MS max{ MS I max{ I MS before afer dis dis before I I } dis di, MS } (15) (16) A Fig. 7 MS (609,495) 44
TZBM 359 Fig. 7. Process of dialogue wih operaor A. Fig. 8. Process of dialogue wih operaor B. (609,495)A A I dis MS f * MS 50% ( 23.6%) (622,408) A (622,408) (609,495) MS I dis A I dis MS 23.6% 50% f * MS 40% ( 23.6%) (625,436) A (625,436) (622,408) A23.6% 40% 40% 50% f * MS 45% ( 29.3%) (627,412) A (627,412) (625,436) MS I dis A MS A (622,408) (627,412) 2 (622,408) B Fig. 8B f * MS 65% (641,394) AB (609,495) (622,408) (641,394) (1) (2) (3) 3 2TZBM 1 ) T.Iwaani: CAMP-ISIJ, 22 (2009), 994. 2 ) Y.Tian, Y.Liu, N.Sannomiya and K.Shimohara: Proc. of In. Manufacuring & Logisics Sysems, Technical Session III-1, (2005), 1. 3 ) Y.Liu, Y.Tian and T.Sawaragi: J. Jpn. Soc. Fuzzy Theory Inelligen Informaics, 18 (2006), No. 6, 837. 4 ) P.Hui, Y.Tian, T.Sawaragi, H.Nakanishi and Y.Horiguchi35 (2008), 31. 5 ) S.Suzuki and T.Enkawa: J. Jpn. Ind. Manage. Assoc., 52 (2001), 163. 6 ) H.Iima, S.Nakayama and N.Sannomiya27 (2000), 67. 7 ) F.Glover: ORSA Journal on Compuing, 1 (1989), 190. 8 ) F.Glover: ORSA Journal on Compuing, 2 (1990), 4. 9 ) L.Chen, L.Xi, J.Cai, N.Bosel and P.Deax: J. Zheiang Universiy Science A, 7 (2006), 234. 10) E.Taillard: Euro. J. Operaional Res., 64 (1993), 278. 11) H.Nakayama: Trans. Operaions Res. Soc. Jpn., 33, (1988), 375. 12) H.Nakayama: Trans. Operaions Res. Soc. Jpn., 35 (1996), 343. 13) H.Kia and Y.Oda: 1996 (1996), 36. 45