CHƯƠNG 6
LẬP LỊCH TRÌNH SẢN XUẤT
I. SẮP XẾP THỨ TỰ CÁC CÔNG VIỆC
1. Sắp xếp các công việc trên 1 máy (1 bộ phận, 1 cá nhân).
Có n công việc thì có n ! cách sắp xếp công việc theo thứ tự.
Trong thực tế người ta thường áp dụng các ưu tiên sau đây để sắp xếp thứ tự
các công việc.
* Nguyên tắc FCFS (first come first served).
Công việc nào đến trước thì làm trước.
* Nguyên tắc EDD (Earliest due date).
Công việc nào đến hạn trước thì làm trước.
* Nguyên tắc SPT (Shortest processing time).
Công việc có thời gian thực hiện ngắn thì làm trước.
* Nguyên tắc LPT (longest processing time)
Công việc nào có thời gian thực hiện dài thì làm trước .
Ví dụ1 :
FCFS.
TT
Thời gian
gia công
(ngày)
Thời hạn hoàn
thành
(ngày thứ )
Thời điểm hoàn
thành
(ngày thứ )
Thời gian trễ
hạn
(ngày)
74

A 8 12 8 -
B 5 8 13 5
C 9 28 22
D 7 15 29 14
F 6 14 35 21
∑
35 40
Thời gian trễ hạn trung bình một công việc = 40/5 = 8 ngày
EDD
TT Thời gian
gia công
Thời hạn hoàn
thành
(ngày thứ )
Thời điểm hoàn
thành
(ngày thứ )
Thời gian trễ
hạn
(ngày)
75
(ngày)
B 5 8 5 -
A 8 12 13 5
E 6 14 19 5
D 7 15 26 11
C 9 28 35 7
∑
35 24
Thời gian trễ hạn trung bình một công việc = 24/5 = 4,8 ngày

SPT
TT
Thời gian
gia công
(ngày)
Thời hạn hoàn
thành
(ngày thứ )
Thời điểm hoàn
thành
(ngày thứ )
Thời gian trễ
hạn
(ngày)
B 5 8 5 -
E 6 14 11 -
D 7 15 18 3
76
A 8 12 26 14
C 9 28 35 7
∑
35 24
= 24/5 = 4,8 ngày
LPT
TT
Thời gian
gia công
(ngày)
Thời hạn hoàn
thành

(ngày thứ )
Thời điểm hoàn
thành
(ngày thứ )
Thời gian trễ
hạn
(ngày)
C 9 28 9 -
77
A 8 12 17 5
D 7 15 24 9
E 6 14 30 16
B 5 28 35 27
∑
35 57
= 57/5 = 11,4 NGÀY
- FCFS : Thể hiện sự công bằng.
- SPT : Thời gian trễ hạn ngắn.
- LPT : Đáp ứng được khách hàng quan trọng.
- SPT : chỉ đáp ứng được nhu cầu của những khách hàng nhỏ
LPT : Thời gian trễ hạn nhiều hơn nhưng lại làm hài lòng khách hàng quan
trọng .
* Mỗi nguyên tắc đều có ưu nhược điểm khác nhau nên tùy theo những trường
hợp cụ thể mà lựa chọn cách sắp xếp cho phù hợp.
2. Sắp xếp các công việc trên 2 máy
Bài toán: Công việc được thực hiện tuần tự từ Máy1 -> Máy2 (do quy trình sản
xuất yêu cầu). Hãy sắp xếp thứ tự các công việc sao cho tổng thời gian hoàn thành
các công việc nhỏ nhất.
+ Nguyên tắc Johnson “Công việc nào có thời gian nhỏ thuộc máy 1 thì xếp trước ,
thuộc máy 2 thì xếp cuối ”

78
Ví dụ2 :
CV Thời gian thực hiện (giờ) Thứ tự sắp xếp
M1 M2 1 2 3 4 5
A 10 12 A E D C B
B 14 13
C 16 15
D 17 16
E 19 30

M
1
A=10 E=19 D=17 C=16 B=14
79
M
2
A =12 E = 20 D = 16 C = 15 B = 13
10 22 29 49 65 80 93
3. Sắp xếp các công việc trên 3 máy
Bài toán : Có n công việc. Mỗi công việc được thực hiện tuần tự M
1
-> M
2
- M
3
Yêu cầu: Sắp xếp công việc theo tuần tự sao cho tổng thời gian hoàn thành các
công việc là nhỏ nhất.
Ví dụ 3 :
CV TG thực hiện CV M
1

+ M
2
M
2
+ M
3
M
1
M
2
M
3
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
80
Thứ tự sắp xếp
1 2 3 4 5
PA1 B A D C E
PA2 B A C D E
13 25 39 55 74
B = 13 A = 12 C = 14 D = 16 E = 19
B = 8 A = 10 C = 12 D = 10 E = 9
B = 16 A = 14 C = 15 D = 18 E = 14
21 37 51 66 84 98
Ghi chú: Phương pháp trên chỉ thực hiện tốt khi thời gian nhỏ nhất trên máy 1 ≥
thời gian lớn nhất trên máy2, thời gian nhỏ nhất trên M
3

≥ thời gian lớn nhất trên
M
2
.
t
min1
≥ t
max2
t
min3
≥ t
max2
II. PHÂN CÔNG CÔNG VIỆC
81
Phương pháp phân công công việc được xem là một nội dung quan trọng của
chương lập lòch sản xuất và điều hành. Phân công công việc được tiến hành cho nhiều
trường hợp như: phân công công việc cho dây chuyền sản xuất, cho máy móc thiết bò, cho
người lao động, cho các đội thi công…
Ứng dụng thuật toán này phải thỏa mãn những điều kiện sau:
- Có n công việc.
- Có n lao động (hoặc n máy).
- Mỗi lao động chỉ làm một việc.
- Mỗi việc chỉ một lao động làm.
Từ những điều kiện trên, bài toán phải đạt được mục tiêu: Bố trí, phân công sao
cho tổng thời gian hao phí nhỏ nhất, hoặc tổng năng suất cao nhất, hoặc tổng chi phí bé
nhất.
Đây là một dạng đặc biệt của bài toán vận tải có tên gọi là bài toán chọn.
Các bước giải bài tóan chọn( bài toán min) :
Bước 1: Lập ma trận vuông n x n với các phân tử Cij.
Bước 2: Trên các hàng của ma trận xác đònh phân tử nhỏ nhất rồi lấy các phân tử trên

hàng trừ đi phân tử này.
Bước 3: Tương tự bước 2 thực hiện trên cột.
Bước 4: Trên các hàng của ma trận , chọn hàng có 1 số 0, đánh dấu số 0 đó rồi gạch bỏ
cột .
Bước 5: Trên các cột của ma trận chọn cột có 1 số 0 , đánh dấu số 0 này rồi gạch hàng.
Bước 6: Kiểm tra xem số 0 được đánh dấu có bằng n chưa ? Nếu bằng bài toán đã giải
xong. Nếu chưa bằng thực hiện bước thứ 7.
Bước 7: Trên các phân tử chưa bò gạch, xác đònh phân tử nhỏ nhất.
- Đối với các phân tử bò gạch 2 đường thì cộng với phân tử này.
82

- Chưa bò gạch thì trừ đi phân tử này.
- Bò gạch 1 đương thì giữ nguyên. Sau đó trở lại bước 4.
Ghi chú: 1. Khi thực hiện B5 nếu thấy xuất hiện các số 0 tạo vòng thì chọn 1 số 0 bất kỳ
trên vòng rồi gạch cả cột lẫn hàng sau đó trở lại B4.
Bài toán cực tiểu
Đây là bài toán phân công có mục tiêu tiến tới min như: thời gian hao phí nhỏ nhất,
tổng chi phí là bé nhất, đònh mức tiêu hao nguyên vật liệu là thấp nhất. Có thể minh họa
bài toán cực tiểu qua ví dụ 1 sau đây:
Ví du 4ï: Có 3 lao động được phân công làm 3 việc với thời gian hao phí ở bảng sau.
Hãy phân công sao cho tổng thời gian hao phí là nhỏ nhất.
Đơn vò: giờ
Công việc
Lao động
X Y Z
A 17 21 5
B 15 7 23
C 19 29 9
Các bước giải:


17 21 5 12 16 0
83
15 7 23 8 0 16
19 29 9 10 20 0


4 16 0* 2 14 0*
0* 0 16 θ = 2 0 0* 18
2 20 0 0* 18 0

Như vậy :
A làm công việc Z
B làm công việc Y
C làm công việc X
Và tổng thời gian sản xuất nhỏ nhất là 5 + 7 + 19 = 31 giờ.
Bài toán cực đại
Đây là bài toán phân công có mục tiêu tiến tới max như: năng suất cao nhất, lợi
nhuận cao nhất, thu nhập nhiều nhất. Ví dụ 5 sau đây minh họa bài toán cực đại.
Ví dụ 5: Có 4 công nhân làm 4 công việc với năng suất như sau:
Đơn vò: SP/ ca
Công việc X Y Z T
84
Công nhân
A 5 23 9 8
B 11 7 29 39
C 17 15 19 34
D 21 19 14 49

Hãy bố trí công việc để tổng năng suất đạt cao nhất.
Đây là bài toán cực đại nên ta thêm dấu trừ vào mỗi số hạng của ma trận.

-5 -23 -9 -8 18 0 14 15
-11 -7 -29 -39 28 32 10 0
-17 -15 -19 -34 7 19 15 0
-21 -19 -14 -49 28 30 35 0
1 0* 4 15
85
11 32 0* 0
0* 19 5 0
11 30 25 0*

Vậy phân công:
- A làm công việc Y
- C làm công việc X
- B làm công việc Z
- D làm công việc T
Tổng năng suất cao nhất là: 23 + 29 + 17 + 49 = 118 SP/ca
Bài toán có ô cấm
Bài toán này ứng dụng trong trường hợp việc phân công bò khống chế về mặt thời
gian hoàn thành, khống chế về chi phí thực hiện, khống chế về doanh thu và lợi nhuận,
hoặc là trong trường hợp có một số công việc mà một vài công nhân không thể thực hiện
được
Ví dụ : Có 3 máy được phân công làm 3 việc với thời gian hao phí như sau :
Đơn vò: giờ
CV
CN
X Y Z
A 17 21 5
86
B 15 7 23
C 19 29 9

Bảng 8.11: Thời gian hao phí của các công việc
Theo bảng trên, bố trí để tổng thời gian hao phí là nhỏ nhất. Biết rằng công nhân B
không làm được việc Y.
Đây là bài toán có ô cấm, ta gạch chéo vào ô 2.2 và giải bình thường

17 21 5 12 16 0
15 X 23 0 X 8
19 29 9 10 20 0


12 0 * 0
0* X 8
10 4 0*

Vậy phân công :
87
- A => Y
- B => X
- C => Z
Tổng thời gian là 45 giờ.
Các bước giải bài tóan chọn giúp ta phân công công việc nhanh chóng và chính
xác, tuy nhiên cần chú ý rằng điều kiện ứng dụng thuật toán này là số công việc bằng với
số lao động. Trong trường hợp số lượng công việc không bằng với số lượng lao động ta
thêm dòng giả hoặc cột giả để đảm bảo điều kiện trên và giá trò của dòng giả hoặc cột giả
này bằng 0.
III. ỨNG DỤNG SƠ ĐỒ PERT ( Program Evaluation and Review
Technique )
1/ Phương pháp lập sơ đồ PERT
Một sơ đồ PERT bao gồm các sự kiện và các công việc .
- Các sự kiện được biểu diễn bằng vòng tròn ( còn gọi là điểm nút )

- Các công việc được biểu diễn bằng các cung có mũi tên đònh
hướng.
A
Một số chú ý khi xây dựng sơ đồ PERT
+ Một dự án chỉ có một sự kiện bắt đầu và một sự kiện kết thúc.
88
A B E
C
D
+Hai công việc tiến hành đồng thời
A
B
+Hai công việc hội tụ
A
C
89
B
+Đưa thêm công việc giả ( có thời gian bằng 0 )
C
A
B D
2/ Phương pháp xác đònh đường găng
Đường găng là đường có thời gian dài nhất nối giữa sự kiện bắt đầu và
sự kiện kết thúc dự án .
Tổng thời gian của dự án chính là độ dài của đường găng , tức là đường nối
các công việc găng .
Để xác đònh đường găng , với mỗi sự kiện , ta cần xác đònh thời gian
sớm nhất và muộn nhất.
Thời gian sớm nhất của sự kiện i ( ký hiệu là ti ) là thời gian sớm nhất
kể từ khi bắt đầu dự án cho đến khi đạt tới sự kiện i

ti = Max ( tj + dji )
90
với j là đỉnh bất kỳ trước i và dji là độ dài cung j, i
Thời gian muộn nhất của sự kiện i ( ký hiệu là t’i ) là thời gian chậm
nhất phải đạt tới sự kiện i nếu như không muốn kéo dài thời gian của dự
án .
t’i = min ( t’j – dij ) với j là đỉnh bất kỳ ngay sau i
Đường găng là đường bao gồm các đỉnh có ti = t’i
Ví dụ minh họa :
Một dự án gồm 9 công việc có mối liên hệ và thời gian như sau :
Công việc Công việc trước Thời gian ( tháng )
A
B
C
D
E
F
G
H
I
Không
A
Không
Không
B, C
B,C
A
D, E, G
F, H
4

6
4
12
10
24
7
10
3
Ta có thể xây dựng sơ đồ PERT như sau :
91
Đường găng bao gồm các công việc A, B, F, I .
Thời gian thực hiện dự án là 37 tháng .
Bài tập : Đưa vào khai thác một mỏ than mới cần thiết phải thực hiện các
công việc sau :
92
1/ Xin giấy phép khai thác 32 tuần A
2/ Làm đường 24 B
3/ Lắp 2 máy dò 1 C
4/ Dựng lán trại tạm 3 E
5/ Rải nhựa đường vào mỏ 8 F
6/ Dẩn nước vào mỏ 28 G
7/ Thăm dò 16 H
8/ Tạo giếng khoan 20 I
9/ Lắp thiết bò khai thác 6 J
10/ Xây nhà cho công nhân 20 K
11/ Đường xá và bố trí dưới mỏ 44 L
12/ Xây dựng khu vực rửa quặng 28 M
Mối liên hệ giữa các công việc như sau :
+ Công việc 1 thực hiện trước 2 , cv2 trước 3,4,5,6.
+ Công việc 3 và 4 trước cv 7.

+ Công việc 5,6,7 trước 8 và 10.
+ Công việc 8,10 trước 9,11 và 12.
Yêu cầu :
- Vẽ sơ đồ PERT
- Xác đònh đường găng và thời gian hoàn thành dự án
93
Ví dụ :
Một dự án gồm 7 công việc có mối liên hệ và thời gian như sau :
Công việc Công việc
trước
Thời gian
( tháng )
Tổng chi phí
(tr.đồng)
Chi phí cho
mỗi tháng
A
B
C
D
E
F
G
Không
Không
A
B
B
C,D
E

2
3
1
3
2
2
1
10
30
3
6
20
10
8
5
10
3
2
10
5
8
94
Công việc Bắt đầu
sớm (ES)
Bắt đầu
muộn (LS)
Kết thúc
sớm (EF)
Kết thúc
muộn (LF)

Thời gian di
động(tháng)
A 0 3 2 5 3
B 0 0 3 3 0
C 2 5 3 6 3
D 3 3 6 6 0
E 3 5 5 7 2
F 6 6 8 8 0
G 5 7 6 8 2
95
Ngân sách theo thời hạn sớm nhất
Công việc Tháng
1 2 3 4 5 6 7 8
A 5 5
B 10 10 10
C 3
D 2 2 2
E 10 10
F 5 5
G 8
Chi phí mỗi
tháng
15 15 13 12 12 10 5 5
Tổng chi phí dự
án
15 30 43 55 67 77 82 87
96
Ngân sách theo thời hạn muộn nhất
Công việc Tháng
1 2 3 4 5 6 7 8

A 5 5
B 10 10 10
C 3
D 2 2 2
E 10 10
F 5 5
G 8
Chi phí mỗi
tháng
10 10 10 7 7 15 15 13
Tổng chi phí dự
án
10 20 30 37 44 59 74 87
97