Bài 1: Hãy dùng nguyên tắc Johnson để xác định thứ tự gia công tối ưu cho các công việc
làm trên 2 máy sau đây, thời gian gia công được tính bằng giờ:
Công việc Thời gian thực hiện các công việc
Máy I Máy II
A 6 12
B 3 7
C 17 8
D 15 14
E 18 8
F 8 16
Giải
Bước 1: Sắp xếp các công việc theo thứ tự thời gian min tăng dần:
Công việc Máy I Máy II
B 3 7
A 6 12
F 8 16
C 17 8
E 18 8
D 15 14
Bước 2: Bố trí các công việc theo nguyên tắc Johnson. Theo thứ tự sắp xếp ở bước 1 lần
lượt bố trí như sau:
 Chọn công việc có thời gian nhỏ nhất xếp trước.
 Công việc nao có thời gian min nằm ở máy I, bố trí bên trái( ở đầu).
 Công việc nào có thời gian min nằm ở máy II, bố trí bên phải( ở cuối).
Kết quả như sau:
PA 1 B A F D E C
PA 2 B A F D C E
Bước 3: vẽ biểu đồ tính tổng thời gian thực hiện các công việc:
PA 1 B A F D E C
10
0
75
6052
3822
10
1. t1 min >= t2 max
2. t3 min >= t2 max
t1 min = 6
t2 max = 5
t3 min = 5
Bước 2: lập ma trận mới bằng cách lấy t1 + t2 và t2 + t3.(phương pháp gần đúng)
Công việc t1 + t2 t2 + t3
A 17 14
B 12 9
C 12 10
D 10 11
E 10 12
F 16 11
Bước 3: sắp xếp thứ tự công việc theo thời gian min tăng dần:
Công việc t1 + t2 t2 + t3
B 12 9
D 10 11
C 12 10
E 10 12
F 16 11
A 17 14
Bước 4: sắp xếp thứ tự công việc theo nguyên tắc Johnson
PA 1 D E A F C B
PA 2 E D A F C B