DYNAMIC SCHEDULING IN TWO-MACHINE FLOW-SHOP WITH RECIRCULATION em-plant( SiMPLE++) Jen-Shiang Chen, Jar-Her Kao, Chun-Chieh Chen, Po-Cheng Liu, and Wen-Pin Lin Department of Industrial Engineering and Management, Far East College ABSTRACT This paper concerns a two-machine flow-shop scheduling problem with job recirculation. A simulation model to deal with this problem is developed and several dispatching rules are implemented. The impact of each rule on the quality of the schedules is measured, namely, according to makespn, mean flow time, mean tardiness, and average machine utilization. Computational results are also presented and em-plant (prior: SiMPLE++) is the simulation language used. Keyword: scheduling, two-machine flow-shop, recirculation, dispatching rules, em-plant 9
92 (When) (Where) (What) (Productivity) (Efficiency) () (2) (3) (4) (5) (6) (7) em-plant( SiMPLE++) Scheduling When Where Productivity Efficiency [5]
2. () n [5] (2) () (i) (3) n / m / A / B (ii) n m A A m = (2) A F Flow Shop (a) Flow Shop A P Permutation Flow Shop A G Job Shop B (b) Permutation Flow Shop 2.2 F max C max F C L L max T T max N T (4) Processing Time; P ij i j Set-up Time (5) Arrival Time; R i (c) Job Shop i R i = 0 (6) Due Date; D i i (7) Completion Time; C i (d) Open Shop i (8) Queue Time; Q i i (9) Flow Time; F i i 93
i (6) L max C i = R i + F i R i = 0 C i = F i (0) Lateness; L i L i = C i D i () Tardiness; T i i i T i = max {0, L i } = max {C i D i } (2) Mean Completion Time; C C = n n i= C i (3) Mean Queue Time; Q Q = n n i= Q i (4) Number of Tard Job; N T (5) F max F max = max{ Fi } i n L max = max{l, L 2,, L n } 2, 2 Minimum Slack MS First Come First Served [, 2, 3, 8, 9, 0,, 94
2] () (Fist Come First Served) FCFS (9) (Least Work Remaining) LWKR MWKR (2) (Shortest Processing Time) SPT (0) (Most Operations Remaining) MOPNR () (Work In Next Queue) WINQ (3) (Longest Processing Time) LPT (2) (Value) (4) (Earliest Due Date) EDD 4. L max (5) (Critical Ratio) CR (a) (b) (c) (d) (e) (f) (g) (h) (j) (6) (Ranm) 4.2 (7) (Slack Time) Slack [, 3, 7] (8) ( ost Work Remaining) MWKR 95
(7) T max T max = max{t, T 2,, T i } Mean Flow Time (8) Utilization Makespan Throughput Cycle Time Mean Lateness Mean Tardiness (9) WIP T max Utilization Setup Time WIP () Mean Flow Time; F F n F = F i n i= () (2) MakespanC max (2) C max = max {C, C 2,, C n } (3) Cycle Time (3) 2 2 (4) Throughput (4) (5) Mean Lateness L = n n i= L i (6) Mean Tardiness n T = T i n i= 96
em-plant 5. STEP Entity Name Job 2 2 Cust.Attri Insert step_no = 4 6 step_no = 2 First_opn 0 step_no = 20 0 true boolean 000 step_no 4 integer () Uniform(0, 0) (Uniform ) (2) Uniform(, 25) (3) 000 (4) 000 (5) (Setup time) (6) (7) d i i R i i 逹 F F Uniform(3, 6) k i l l p ilk STEP 2 Frame i l k i L 2 d i = R i + F l= k= P ilk L L CR 5.2 CPU Intel Pentium III GHzSDRAM 52M Microsoft Winw 2000 Professional em-plant V4.6 5.3 em-plant 2 97
STEP 3 Source Uniform,0.0000, 0.0000 2 Frame EventController Source Entity Buffer Store SingleProce Drain TableFile Method Reset EndSim 98
STEP 4 Buffer Capacity 000 STEP 7 Dimension Rows 000 Columns 29Width 20 STEP 5 TableFile STEP 8 Format Column Index STEP 6 Store X-Dim Y-Dim 00 Store 0000 Format 99
STEP 9 STEP 2 Column Integet Column Time STEP0 Column Format STEP 3 STEP Column Object STEP 4 TableFile Column index job_id step_no due_date fcfs_intime ranm remaining_t slack cr M 200
M2 Enter STEP 7 TableFile2 Column index job_id step_no due_date fcfs_intime ranm remaining_t slack cr STEP 5 WaitToM2 Column index job_id M step_no due_date remaining_t M2 Enter M2 M Enter STEP 6 Store2 X-Dim Y-Dim STEP 8 WaitToM Column 00 Store 0000 index job_id step_no due_date M2 M Enter 20
if @.first_opn the-- TableFile[, TableFile.yDim+]:= @; TableFile[2, TableFile.yDim]:= @.step_no; TableFile[4, TableFile.yDim]:= eventcontroller.simtime; TableFile[5, TableFile.yDim]:= z_uniform(, 0, ); TbDrain[, @.getno]:= @.getno; TbDrain[3, @.getno]:= eventcontroller.simtime; from index:=; -- until index > @.step_no loop TableFile[index+9, TableFile.yDim]:= STEP 9 MbDrain Column z_uniform(,, 25); index job_id index:= index+ ; DueTime InTime from index:=; -- OutTime FlowTime until index > @.step_no Tardiness loop Makespan MeanFlowTime TableFile[6, TableFile.yDim]:= TableFile[6, TableFile.yDim] MeanFlowTime +TableFile[index+9, TableFile.yDim]; MeanFlowTime index:= index+ ; Enter ablefile[3, TableFile.yDim]:= eventcontroller.simtime+ z_uniform(,3,6)*tablefile.sum(`[0,tablefile.yd im]..`[9+@.step_no,tablefile.ydim]); TbDrain[2, @.getno]:= TableFile[3, TableFile.yDim]; TableFile[7, TableFile.yDim]:= TableFile[3, TableFile.yDim] - eventcontroller.simtime - TableFile[6, TableFile.yDim]; TableFile[8, TableFile.yDim]:= (TableFile[3, TableFile.yDim]- eventcontroller.simtime)/tablefile[6, TableFile.yDim]; @.first_opn:= False; move_up; -- move_up STEP 20 Record Method is local index:integer; --index 202
STEP 2 Store Record Control Entry STEP 23 M Move_up Control Entry STEP 22 Move_up is local index: integer; --index is local index: integer; --index TableFile2[, TableFile2.yDim+]:= WaitToM2[, ]; if Store.numMu > 0 and M.empty then TableFile2[2, TableFile2.yDim]:= M WaitToM2[2, ]; TableFile.sort(8, "up");--tablefile TableFile2[3, TableFile2.yDim]:= 8 cr WaitToM2[3, ]; M.procTime:= TableFile[0, ]; TableFile2[4, TableFile2.yDim]:= TableFile[2, ]:= TableFile[2, ]- ; eventcontroller.simtime; WaitToM2[, WaitToM2.yDim+]:= TableFile2[5, TableFile2.yDim]:= TableFile[, ]; z_uniform(, 0, ); WaitToM2[2, WaitToM2.yDim]:= TableFile2[6, TableFile2.yDim]:= TableFile[2, ]; WaitToM2[6, ]; WaitToM2[3, WaitToM2.yDim]:= TableFile2[7, TableFile2.yDim]:= TableFile[3, ]; TableFile2[3, TableFile2.yDim] WaitToM2[6, WaitToM2.yDim]:= - eventcontroller.simtime TableFile[6, ]- TableFile[0, ]; - TableFile2[6, from index:= ; --TableFile TableFile2.yDim]; WaitToM2 until index > TableFile[2, ] loop WaitToM2[index+9, WaitToM2.yDim]:= TableFile[index+0, ]; index:= index+ ; TableFile[, ].move(m); --TableFile[, ] M TableFile.cutrow(); -- TableFile STEP 24 Record2 TableFile2[8, TableFile2.yDim]:= (TableFile2[3, TableFile2.yDim] - eventcontroller.simtime)/tablefile2[6, TableFile2.yDim]; from index:=; --WaitToM2 TableFile2 until index > WaitToM2[2, ] loop TableFile2[index+9, TableFile2.yDim]:= WaitToM2[index+9, ]; index:= index+ ; WaitToM2.cutRow(); -- WaitToM2 203
move2_up; -- move2_up STEP 25 Store2 Record2 Control Entry STEP 26 Move2_up WaitToM[6, ]; is local index: integer; --index if store2.nummu > 0 and M2.empty then-- TableFile2.sort(8, "up");-- TableFile.yDim]:= WaitToM[index+9, ]; M2.procTime:= TableFile2[0, ]; index:= index+ ; TableFile2[2, ]:= TableFile2[2, ]- ; WaitToM[, WaitToM.yDim+]:= WaitToM[, ].move(buffer); TableFile2[, ]; WaitToM[2, WaitToM.yDim]:= --WaitToM[, ] Buffer TableFile2[2, ]; else WaitToM[3, WaitToM.yDim]:= WaitToM[, ].move(drain); -- TableFile2[3, ]; WaitToM[, ] Drain WaitToM[6, WaitToM.yDim]:= TableFile2[6, ]- TableFile2[0, ]; WaitToM.cutRow(); -- WaitToM from index:= ; --TableFile2 WaitToM until index > TableFile2[2, ] loop STEP 27 outm2 is local index: integer; --index if WaitToM[2, ] /= 0 then TableFile[, TableFile.yDim+]:= WaitToM[, ]; TableFile[2, TableFile.yDim]:= WaitToM[2, ]; TableFile[3, TableFile.yDim]:= WaitToM[3, ]; TableFile[4, TableFile.yDim]:= eventcontroller.simtime; TableFile[5, TableFile.yDim]:= z_uniform(, 0, ); TableFile[6, TableFile.yDim]:= TableFile[7, TableFile.yDim]:= TableFile[3, TableFile.yDim] - eventcontroller.simtime - TableFile[6, TableFile.yDim]; TableFile[8, TableFile.yDim]:= (TableFile[3, TableFile.yDim] - eventcontroller.simtime)/tablefile[6, TableFile.yDim]; from index:=; --WaitToM TableFile until index > WaitToM[2, ] loop TableFile[index+9, move2_up; -- move2_up 204
STEP 28 M2 OutM2 Control Exit Method Reset is deletemovables;-- TableFile.delete; TableFile2.delete; WaitToM.delete; WaitToM2.delete; TbDrain.delete; Is i]; TbDrain[4, @.getno]:= if (TbDrain[4, i]- TbDrain[2, i])>0 then eventcontroller.simtime;--tbdrain[6, i]:= TbDrain[4, i]- STEP 30 Drain MtDrain Control Entry STEP 32 EndSim Method Method EndSim Method EndSim is local i:integer;--i STEP 29 MtDrain from i:= ; until i>0000 loop TbDrain[5, i]:= TbDrain[4, i]- TbDrain[3, TbDrain[2, i]; else TbDrain[6, i]:= 0; i:= i+; TbDrain[7, ]:= TbDrain.max(`[4, ]..`[4, 0000]);-- TbDrain[8, ]:= TbDrain.sum(`[5, ]..`[5, 0])/0000;-- TbDrain[9, ]:= TbDrain.sum(`[6, ]..`[6, 0])/0000; -- TbDrain[0, ]:= (M.workingPercentage+ M2.workingPercentage)/2; -- STEP 33 Init Method Init Method Init is eventcontroller.seedreset:= False; STEP 3 Reset Method Reset 205
STEP 34 Model MtDrain CR TableFile2[2, ]:= TableFile2[2, ]- ; Method Name move_up move2_up FCFS TableFile.sort(4, TableFile2.sort(4, "up") "up") SPT TableFile.sort( TableFile2.sort( 0, "up") 0, "up") LPT TableFile.sort( TableFile2.sort( 0, "wn") 0, "wn") EDD TableFile.sort(3, TableFile2.sort(3, "up") "up") Ranm TableFile.sort(5, TableFile2.sort(5, "up") "up") Slack TableFile.sort(7, TableFile2.sort(7, "up") "up") MWKR TableFile.sort(6, TableFile2.sort(6, "wn") "wn") LWKR TableFile.sort(6, TableFile2.sort(6, "up") "up") MOPNR TableFile.sort(2, TableFile2.sort(2, "wn") "wn") up wn STEP 35 Method(move_up move2_up) Sort 0 4 Move_up is local index: integer; --index if Store.numMu > 0 and M.empty then 6. 2 TableFile.sort(8, "up"); 2 0 3 M.procTime:= TableFile[0, ]; TableFile[2, ]:= TableFile[2, ]- ; 2~5 MWKRFCFSSPT Move2_up LWKRSlackEDD is LWKRSlackEDD local index: integer; --index SPTFCFSMWKR if store2.nummu > 0 and M2.empty then TableFile2.sort(8, "up"); M2.procTime:= TableFile2[0, ]; 206
3 2 FCFS * 7:7:52 :02:0 0:58:07 0.98792 SPT 7:9:06 0:58:59 0:55:57 0.9995 LPT 7:39:4 0:58:05 0:55:02 0.94625 EDD 7:23:22 0:50:45 0:46:49 0.98344 CR 7:2:09 0:56:05 0:52:20 0.98500 Ranm 7:22:56 0:52:35 0:48:40 0.982735 Slack 7:22:35 0:50:06 0:46:37 0.98059 MWKR 7:6:43 :09:24 :06:23 0.986647 LWKR 7:20:56 0:47:44 0:44:43 0.986077 MOPNR 7:9:55 :3:08 :27:4 0.986538 *HHMMSS 2 2 4 3 5 6.2 6 207
6 0 4 LWKRSlackEDD 6~9 LWKRSlackEDD SPTMOPNRMWKR SPTRanmEDD 4 6 FCFS * 2:5:0 0:23:59 0:2:6 0.992262 SPT 2:47:33 3:3:2 3:03:30 0.996357 LPT 22:44:08 3:55:05 3:43:35 0.953865 EDD 2:52:47 2:48:42 2:36:57 0.993689 CR 2:54:4 2:57:40 2:45:53 0.990066 Ranm 2:49:3 6:20: 6:08:30 0.993783 Slack 2:50:48 2:35:49 2:24:8 0.99248 MWKR 2:48:49 4:22:35 4:0:53 0.992529 LWKR 2:50:45 2:27:5 2:7:49 0.989432 MOPNR 2:48:27 6:9:54 6:08: 0.993395 *HHMMSS 6 6 7 8 208
9 6.3 0 0 0 5 0~3 LWKRRanmSPT SlackLWKRCR SlackLWKRCR SPT FCFSCR 5 0 FCFS * 36:2:53 24:08:32 23:49:03 0.99457 SPT 36:9:22 5:34:3 5:7:32 0.995947 LPT 38:06:9 7:00:36 6:4:09 0.9536 EDD 36:26:2 4:53:34 4:34:02 0.993644 CR 36:22:23 4:49:22 4:29:47 0.99367 Ranm 36:9:9 5:6:45 4:57:4 0.993384 Slack 36:25:00 4:35:09 4:5:36 0.993385 MWKR 36:2:3 28:38:26 28:8:56 0.993324 LWKR 36:8:28 4:38:52 4:2:20 0.993553 MOPNR 36:22:20 30:5:54 30:32:26 0.993389 *HHMMSS 0 0 209
2 3 [2] 996 pp02-38985 e [4] 999 [5] 999 [6] pp99-05pp 343-36984 [7] 996 [8] pp293-327 98 [9] pp625-665997 [0] pp339-3498 [] pp528-54 2 6 984 0 0 [2] Steven Nahmias, Poduction and Operations 0 Analysis, 997. () SPTMWKR LWKR (2) LWKRSlack EDD (3) LWKRSlack EDD (4) SPTFCFS MOPNR [] pp373-390984 [3] LWKR SPT EDD 20