生产管理：Scheduling -HOMEWORK SOLUTION.ppt

文档介绍：By: Prof. Y. Peter Chiu
Scheduling
~ HOMEWORK SOLUTION ~
1
HW # 9
To minimize mean flow time
SPT:6-4-2-1-3-5
(b) To minimize “Number of Tardy Jobs”
Moore’s Algorithm
2
Job
ti
Delivery
ti
di
1
1:12
15
1:27
3:30
2
:40
15
55
2:00
3
2:12
15
2:27
3:00
4
:30
15
45
5:00
5
3:06
15
3:21
4:00
6
:25
15
40
6:00
HW # 9
3
HW # 9
(b) Moore’s Algorithm
starting from EDD
Job
ti’
Fi’
di
Li
2
55
55
2:00
-1:05
3
2:27
3:22
3:00
22
1
1:27
4:49
3:30
1:19
5
3:21
8:10
4:00
4:10*
4
45
8:55
5:00
3:55
6
40
9:35
6:00
3:35
Delete Job # 3
4
Job
ti’
Fi’
di
2
55
55
2:00
1
1:27
2:22
3:30
5
3:21
5:43
4:00
4
45
5:00
6
40
6:00
Job
ti’
Fi’
di
2
55
55
2:00
1
1:27
2:22
3:30
4
45
3:07
5:00
6
40
3:47
6:00
HW # 9
(b) Moore’s Algorithm
Delete Job # 5
5
2-1-4-6-3*-5* (by SPT for tardy jobs)
or 2-1-4-6-5*-3*
# of Tardy Jobs = 2
(c) To minimize maximum lateness
EDD:2-3-1-5-4-6
Max Li=4:10
HW # 9
(b) Moore’s Algorithm
6
3 M/C’s
To Minimize the makespan.
≧ Max. Bi
Job
A
B
C
1
4
2
6
2
2
3
7
3
6
5
6
4
3
4
8
Max
Bi=5
Ci=6
HW # 14
7
2 M/C’s
Johnson’s 2 – 1 – 4 – 3
Job
A’
B’
1
6*
8
2
5*
10
3
11
11
4
7*
12
HW # 14

Convert it to a two-machine problem :
1
2
3
8
2
12
1
18
4
26
3
32
Fi
F’=(12+18+26+32)/4
= 22
Total Flow Time = 32
HW # 14
A
B
C
9
HW # 15
Total time = 115+20 =135
Total time = 115+45 = 160
∴ Total makespan =135
10