Mô tả:
CHÖÔNG 6 :
LAÄP LÒCH TRÌNH SAÛN XUAÁT
I. SAÉP XEÁP THÖÙ TÖÏ CAÙC COÂNG VIEÄC
1. Saép xeáp caùc coâng vieäc treân 1 maùy (1 boä phaän,
1 caù nhaân).
Caùc coâng vieäc ñöôïc thöïc hieän tuaàn töï qua 1
maùy (1 boä phaän, 1 caù nhaân) cho neân vôùi n coâng
vieäc ta coù n ! caùch saép xeáp thöù töï .
Trong thöïc teá ngöôøi ta thöôøng aùp duïng caùc öu
tieân sau ñaây ñeå saép xeáp thöù töï caùc coâng vieäc.
* Nguyeân taéc FCFS (first come first served).
Coâng vieäc naøo ñeán tröôùc thì laøm tröôùc.
* Nguyeân taéc EDD (Earliest due date).
Coâng vieäc naøo ñeán haïn tröôùc thì laøm tröôùc.
* Nguyeân taéc SPT (Shortest processing time).
Coâng vieäc coù thôøi gian thöïc hieän ngaén thì laøm tröôùc.
* Nguyeân taéc LPT (longest processing time)
Coâng vieäc naøo coù thôøi gian thöïc hieän daøi thì laøm tröôùc
Ví duï : FCFS.
T
T
Thôøi gian
gia coâng
(ngaøy)
Thôøi haïn hoaøn
thaønh
(ngaøy thöù .....)
Thôøi ñieåm
hoaøn thaønh
(ngaøy thöù..)
Thôøi gian
treã haïn
(ngaøy)
A
8
12
8
-
B
5
8
13
5
C
9
28
22
D
7
15
29
14
E
6
14
35
21
35
40
Thôøi gian treã haïn trung bình moät coâng vieäc = 40/5 = 8 ngaøy
EDD
T
T
Thôøi gian
gia coâng
(ngaøy)
Thôøi haïn hoaøn
thaønh
(ngaøy thöù .....)
Thôøi ñieåm
hoaøn thaønh
(ngaøy thöù......)
Thôøi gian
treã haïn
(ngaøy)
B
5
8
5
-
A
8
12
13
1
E
6
14
19
5
D
7
15
26
11
C
9
28
35
7
35
Thôøi gian treã haïn trung bình moät coâng vieäc = 24/5 = 4,8 ngaøy
24
SPT
T
T
Thôøi gian
gia coâng
(ngaøy)
Thôøi haïn hoaøn
thaønh
(ngaøy thöù .....)
Thôøi ñieåm
hoaøn thaønh
(ngaøy thöù....)
Thôøi gian
treã haïn
(ngaøy)
B
5
8
5
-
E
6
14
11
-
D
7
15
18
3
A
8
12
26
14
C
9
28
35
7
35
24
Thôøi gian treã haïn trung bình moät coâng vieäc laø 24/5 = 4,8 ngaøy
LPT
T
T
Thôøi gian
gia coâng
(ngaøy)
Thôøi haïn hoaøn
thaønh
(ngaøy thöù .....)
Thôøi ñieåm
hoaøn thaønh
(ngaøy thöù ...)
C
9
28
9
Thôøi gian
treã haïn
(ngaøy)
-
A
8
12
17
5
D
7
15
24
9
E
6
14
30
16
B
5
28
35
27
35
57
Thôøi gian treã haïn trung bình moät coâng vieäc laø 57/5 = 11,4 NGAØY
2.. Saép xeáp caùc coâng vieäc treân 2 maùy
Baøi toaùn: Coâng vieäc ñöôïc thöïc hieän tuaàn töï töø
Maùy1 -> Maùy 2 (do quy trình saûn xuaát yeâu caàu).
Haõy saép xeáp thöù töï caùc coâng vieäc sao cho toång
thôøi gian hoaøn thaønh caùc coâng vieäc nhoû nhaát.
+ Nguyeân taéc Johnson “Coâng vieäc naøo coù thôøi
gian nhoû thuoäc maùy 1 thì xeáp tröôùc , thuoäc maùy 2
thì xeáp cuoái ”
CV
Thôøi gian thöïc hieän (giôø)
Thöù töï saép
xeáp
M1
M2
1
A
10
12
A
B
14
13
C
16
15
D
17
16
E
19
30
2
3
4
5
CV
Thôøi gian thöïc hieän (giôø)
Thöù töï saép
xeáp
M1
M2
1
A
10
12
A
B
14
13
C
16
15
D
17
16
E
19
30
2
3
4
5
B
CV
Thôøi gian thöïc hieän (giôø)
Thöù töï saép
xeáp
M1
M2
1
A
10
12
A
B
14
13
C
16
15
D
17
16
E
19
30
2
3
4
5
C B
CV
Thôøi gian thöïc hieän (giôø)
Thöù töï saép
xeáp
M1
M2
1
A
10
12
A
B
14
13
C
16
15
D
17
16
E
19
30
2
3
4
5
D C B
CV
Thôøi gian thöïc hieän (giôø)
Thöù töï saép
xeáp
M1
M2
1
2
3
4
5
A
10
12
A ED C B
B
14
13
C
16
15
D
17
16
E
19
20
10
M1
M2
A=
10
29
E=19
46
D=17
A =12
10
62
C=16
E = 20
22
29
D = 16
49
76
B=14
C=
15
65
B=
13
80
93
3. Saép xeáp thöù töï coâng vieäc treân 3 maùy
Coù n coâng vieäc vôùi moãi coâng vieäc ñöôïc thöïc hieän tuaàn töï
Maùy 1 -> Maùy 2 – Maùy 3
Yeâu caàu: Saép xeáp coâng vieäc theo tuaàn töï sao cho toång
thôøi gian hình thaønh coâng vieäc laø nhoû nhaát.
Töø ba maùy ta thöïc hieän vieäc chuyeån ñoåi veà hai maùy roài
aùp duïng nguyeân taéc Johnson
CV
CV
Thôøi gian thöïc hieän
M1 + M2
M2 + M3
M1
M2
M3
A
12
10
14
A
22
24
B
13
8
16
B
21
24
C
14
12
15
C
26
27
D
16
10
18
D
26
28
E
19
9
14
E
28
23
PA1
PA2
Thöù töï saép xeáp
1
2
3
B
A
D
B
A
C
4
C
D
5
E
E
13
B = 13
25
A = 12
39
55
D = 16
A=
10
B=
8
C = 14
C=
12
B = 16
21
E = 19
D=
10
A = 14
37
74
E=
9
C = 15
51
D = 18
66
E = 14
84
Ghi chuù: Phöông phaùp treân chæ thöïc hieän toát khi thôøi gian nhoû nhaát treân maùy 1
lôùn hôn hay baèng thôøi gian lôùn nhaát treân maùy2, thôøi gian nhoû nhaát treân M3
thôøi gian lôùn nhaát treân M2.
tmin1 tmax2
tmin3 tmax2
98
Vuøng
1
2
3
Nhaø .maùy
A
Coâng
suaát
20
21
22
120
B
22
25
27
80
C
24
28
30
100
Nhu caàu
90
70
140
bj
90
70
20
140
21
ai
22
120
22
25
27
80
24
28
30
100
Ui
Vj
Vuøng
1
2
3
Nhaø .maùy
A
Coâng
suaát
20
21
22
100
B
22
25
27
100
C
24
28
30
100
Nhu caàu
100
100
100
bj
100
100
20
100
21
22
ai
100
22
25
27
100
24
28
30
100
Ui
Vj
- Xem thêm -