Chương 4 L CH TRÌNH S N XU T
Ả
Ấ
Ị
Vuong van Duc
1
S P X P T T
Ế Ứ Ự ƯU TIÊN
Ắ
Nh n hàng tr
ậ
ớ
ư c: ớ FCFS
ư c làm tr (First Come First Served)
Giao hàng trư c làm tr
ớ
ư c:ớ EDD
(Earliest Due Date)
ắ
ấ
ả
ờ
ư c:ớ
ờ
ả
ấ
ư c: ớ
Th i gian s n xu t ng n làm tr SPT (Shortest Processing Time) Th i gian s n xu t dài làm tr LPT (Longest Processing Time)
Vuong van Duc 2
Ch tiêu tính toán
ỉ
=
Tht
=
Cth
=
Ttb
Tdt n Tdt Tsx Ttr n
Vuong van Duc 3
ả
M C Đ H P LÝ Ch tiêu hi u qu ờ ờ
Ứ Ộ Ợ ệ ỉ t trung bình công vi c. 1. Th i gian hoàn t ệ ấ 2. Th i gian tr h n trung bình công vi c. ệ ễ ạ i trung bình trong h 3. S công vi c còn l ệ ạ
ố
ệ
th ng.ố
M c ứ đ h p lý (MDHL): ộ ợ MDHL= A / B
V i :ớ A: S th i gian còn l B: S công vi c còn l
ố ờ ố
ệ
i. ạ i tính theo th i gian. ạ
ờ
Vuong van Duc 4
Nguyên t c JOHNSON
ắ
Laäp lòch trình N coâng vieäc treân 2 maùy:
Neáu coâng vieäc coù thôøi gian thöïc hieän nhoû nhaát: 1. Treân maùy 1 ñöôïc xeáp laøm tröôùc tieân. 2. Treân maùy 2 ñöôïc xeáp laøm sau cuøng.
tmax2£
Laäp lòch trình N coâng vieäc treân 3 maùy:
1. tmin1‡ tmin3 2. Tieán haønh thöïc hieän: t1+t2 vaø t2+t3 3. Saép xeáp thöï töï öu tieân coâng vieäc.
Laäp lòch trình N coâng vieäc treân M maùy:
1. Saép xeáp thöù töï öu tieân caùc coâng vieäc. 2. Xaùc laäp vaø tính giaù trò caùc aån soá cuûa heä phöông trình. 3. Tính T vaø löïa choïn Tmin.
Vuong van Duc 5
Nguyên t c : JOHNSON
ắ
ậ ờ ỗ
L p danh sách th i gian làm trên m i máy v i các công vi c ớ ệ
ờ ắ
Ch n th i gian làm ng n nh t ấ (N u th i gian b ng nhau ch n tùy ý) ọ ờ ọ ế ằ
ế t ế t N u th i gian ng n nh t ầ ệ ươ ứ ứ
ắ ờ ng ng 1 công vi c trên máy 1 : X p đ u tiên ế ầ ế
N u th i gian ng n nh t ầ ắ ờ ng ng 1 công vi c ệ ươ trên máy 2 : X p cu i ố cùng
Xóa công vi c đã đ c s p x p ra kh i danh sách c n b trí. ệ ượ ố ỏ ế ấ ắ
Còn công vi c nào c n đ ệ ầ ượ c b ố
CÓ
trí
KHÔNG
V i th t công vi c v a s p x p s có t ng th i gian là nh nh t. ứ ự ớ ệ ừ ắ ỏ ổ ờ ế ẽ ấ
Vuong van Duc 6
N Công vi c M máy ệ
I
II
III
IV
5
x1
7
4
x’’1
2
x’1
A
3
x2
5
6
x’’2
4
x’2
B
1
x3
3
5
x’’3
3
x’3
C
I
II
III
IV
5
x1=0
7
4
x’’1=5
2
x’1=1
A
3
x2=4
5
6
x’’2=1
4
x’2=0
B
1
x3=8
3
5
x’’3=0
3
x’3=3
C
Vuong van Duc 7
PHÂN CÔNG CÔNG VI C Ệ CHO CÁC MÁY
ề
I A1
II A2
III A3
ủ ế ẩ
A
B1
B2
B3
B
ệ
C1
C2
C3
C
Đi u ki n áp d ng ụ : ệ 1. N công vi c và N máy. ệ 2. Tính năng c a máy có th thay th l n ể nhau. 3. M i công vi c ch ỗ ỉ ti n hành trên m t ộ ế máy.
4. Chi phí các máy đ u ề
khác nhau.
Tmin= A2 + B3 + C1
Vuong van Duc 8
Bài toán PHÂN CÔNG CÔNG VI CỆ
MA TR NẬ
ế ấ
ấ
Bi n đ i: ổ - Hàng xu t hi n ít nh t 1 s 0 ố ệ - C t xu t hi n ít nh t 1 s 0
ố
ộ
ệ
ấ
ấ
CH N HÀNG,C T CÓ 1 S 0 Ọ Ộ Ố
SAI
ọ
ả
Ch n theo gi thuy tế
ĐÚNG
ọ
ọ
ạ
Ch n c t g ch b ỏ ộ ạ hàng
Ch n hàng g ch b ỏ c tộ
KI M TRA S ô ch n b ng h ng Ma tr n Ể ằ
ố
ọ
ạ
ậ
SAI
BI N Đ I Ổ Ế
ĐÚNG
K T THÚC Ế
Vuong van Duc 9
• S đ GANT
ơ ồ
2002
Start
Finish
ID Task Name
Mar
Apr May
Jun
Jul
Aug Sep Oct Nov Dec
Jan Feb
1 2 3 4
Cong viec A1 Cong viec A2 Cong viec A3 Cong viec A4
3/1/2002 3/1/2002 5/1/2002 9/2/2002
5/31/2002 8/30/2002 10/31/2002 2/28/2003
Vuong van Duc 10
GI I SẢ Ơ Đ PERT
Ồ
Vuong van Duc 11
PERT (1957-Program Evaluation and Review Technique)
j
i
Dij
ts j
tm j
ts i
tm i
tij
Dj
Di
+
+
=
tij
tij
bm4a 6
=
-
min(
)
t
t
t
m i
m j
ij
tm i
=
+
max(
t
t
t
s j
s i
) ij
ts j
-
Di
t
= tD i
m i
s i
-
Dj
t
= tD j
m j
s j
- -
t
t
= tD ij
m j
s i
ij
Dij
Vuong van Duc 12
ơ ồ
•
• S đ PERT (Programme Evaluation and Review Technique - K thu t đánh giá và duy t l
i K ho ch)
ệ ạ ế ạ
ậ
ỹ
2
2 ( 1 )
A4 (2)
A
A1 (2)
A6 (3)
0
1
4
A
5 (6)
)
7 ( 4
A3 (5)
A
3
Vuong van Duc 13
PERT
Theo t l
và ph
ỷ ệ
ương n m ngang ằ
đây:
• C th có s ụ ể
ơ đ sau ồ
Th i gian th c hi n (tháng) ự
ờ
ệ
1
2
3
4
5
6
7
8
9
10
0’
2
4’
0
1
3
4
0”
3’
1’
4”
Vuong van Duc 14
