1
Ch
ươ
ng 7
LẬP LỊCH TRÌ NH SẢN XUẤT
Ch
ươ
ng 7
LẬP LỊCH TRÌ NH SẢN XUẤT
Mọi thứ đều
ưu tiên số 1
I . KHÁI QUÁT VỀ CÔNG TÁC
LẬP LỊCH TRÌ NH SẢN XUẤT
n Lập lịch trình sản xuất làtoàn bộ các hoạt động xây
dựng lịch trình sản xuất, điều phối, phân giao các
công việc cho từng người, nhóm người, từng máy và
sắp xếp thứ tự các công việc ở từng nơi làm việc
nhằm đảm bảo hoàn thành đúng tiến độ đã xác định
trong lịch trình sản xuất trên cơ sở sử dụng cóhiệu
quả khả năng sản xuất hiện cócủa doanh nghiệp.
n 2 bài toán cơ bản:
 Bài toán s
ắ
p x
ế
p th
ứ
t
ự
t
ố

c
Có4 nguyên tắc ưu tiên thường áp dụng gồm:
-Nguyên t
ắ
c 1: Đến trước -phục vụ trước
(First come first served –FCFS)
-Nguyên t
ắ
c 2: Bố trítheo thời hạn hoàn thành sớm nhất
(Earliest due date –EDD)
-Nguyên t
ắ
c 3: Bố trítheo thời gian gia công ngắn nhất
(Shortest processing time –SPT)
-Nguyên t
ắ
c 4: Bố trítheo thời gian gia công dài nhất
(Longest processing time –LPT)
2.1. Trường hợp 1 máy -N công việc
2.1.1. Các nguyên tắc ưu tiên đối với những công
việc cần làm trước
Thời gian hoàn tất trung
bình một công việc (T
tb
)
Tổng thời gian hoàn thành của tất cả các công việc
Số công việc
∑ (Số c/việc trong hệ thống trong thời gian sản
xuất t x thời gian sản xuất t)
Tổng thời gian sản xuất

c
Víd
ụ
:Vào đầu tháng 1
năm N, công ty cơ khí
PX cónhận được 5 hợp
đồng với thứ tự đặt
hàng làA, B, C, D, E.
Thời gian sản xuất và
thời hạn hoàn thành
của từng công việc cho
trong bảng sau:
239
E
153D
188C
62B
86A
Thời hạn
hoàn
thành
(ngày
thứ...)
Thời gian
sản xuất
(ngày)
Công
việc
Theo nguyên tắc 1: FCFS
28Tæng

1 9 2 3 3 8 4 2 5 6
4,15
77
t
tb
==
==
×+×+×+×+×
=
==
6
8
16
19
28
77
0
2
0
4
5
11
2
Theo nguyªn t¾c 2: EDD
28Tæng
239E
188
C
153
D

tb
==
==
==
2
8
11
19
28
68
0
0
0
1
5
6
Theo nguyên tắc 3: SPT
96528Tæng
523289E
118198
C
38116A
01553D
0622B
Thời gian
trễ hẹn
(ngày)
Thời hạn
hoàn thành
(ngày thứ...)

158236A
018178
C
02399E
Thời gian
trễ hẹn
(ngày)
Thời hạn
hoàn thành
(ngày thứ...)
Thời gian hoàn
thành kể cả chờ
đợi (ngày)
Thời gian sản
xuất (ngày)
Công
việc
ngµyTR
viÖc c«ngN
ngµy
tb
tb
6,9
5
48
68,3
28
103
6,20
5

2.1. Trường hợp 1 máy -N công việc
2.1.2. Nguyên t
ắ
c dùng t
ỉ
s
ố
t
ớ
i h
ạ
n ( CR -
Critical Ratio)
i
i
N
T
CR =
Trong
đ
ó: T
i
: làthời gian còn lại tính đến thời hạn hoàn thành
của công việc i
N
i
: làthời gian cần thiết để hoàn thành phần công việc i
còn lại, hay làphần công việc i còn lại phải làm mất bao nhiêu thời
gian tính đến thời hạn hoàn thành.
* Ý ngh

528/12
B
430/12
A
Sèngµy cÇn thiÕt
cho c«ng viÖc
cßn l¹i
Thêi h¹n
hoµn
thµnh
C«ng
viÖc
Víd
ụ
:Vào ngày 25/ 12/ N, tại một công ty có3 công việc được
đặt hàng như sau:
1
2
2
CR
6,0
5
3
CR
25,1
4
5
CR
C
B

kia.
2. 2. Lập lịch trình N công việc trên 2 máy
-nguyên tắc Johnson
B
ướ
c 1 : Liệt kê tất cả các công việc vàthời gian
thực hiện chúng trên mỗi máy.
B
ướ
c 2 : Chọn công việc cóthời gian thực hiện
nhỏ nhất.
+ Nếu công việc này nằm trên máy 1 thì
được sắp xếp trước.
+ Nếu công việc này nằm trên máy 2 thì
được sắp xếp cuối cùng.
B
ướ
c 3 : Khi một công việc đã được sắp xếp rồi
thìta loại trừ nó đi, chỉ xét những công việc còn
lại.
B
ướ
c 4 : Trở lại bước 2 và 3 cho đến khi tất cả
các công việc đều đã sắp xếp xong.
2. 2. Lập lịch trình N công việc trên 2 máy
-nguyên tắc Johnson
Víd
ụ
:Có5 công việc được sản xuất bằng 2 máy: máy
khoan vàmáy tiện. Thời gian thực hiện mỗi công việc trên

bằng thời gian dài nhất trên máy 2.
Nếu bài toán thoả mãn một trong hai điều kiện trên, ta tiến
hành giải bài toán theo trình tự sau:
- Đối với mỗi công việc, ta lấy
t1+ t2 vàlấy t2+ t3 để đưa về
trường hợp lập lịch trình cho N công việc trên 2 máy.
-Áp dụng nguyên t ắc Johnson để sắp xếp thứ tự tối ưu cho các
công việc
-Dùng lịch trình đã lập vàbảng thời gian gốc (gồm đủ 3 máy)
để vẽ dòng thời gian.
2.3. Lập lịch trình N công việc trên 3 máy
Víd
ụ
: Có4 công việc được thực hiện lần lượt trên 3 máy như sau. Hãy
chuyển đổi để cóthể áp dụng nguyên tắc Johnson.
16
11
20
15
(Ngắn nhất = 11)
9
3
2
4
(Dài nhất = 9)
18
12
10
1
(Ngắn nhất = 1)

t
2
+ t
3
t
1
+ t
2
Công việc
Da theo nguyờn tc Johnson, ta iu cỏc cụng vic theo
th t
D C A B.
2.4. Sp xp lch trỡnh N cụng vic trờn M mỏy
- B

c 1 : Xỏc nh s lng cỏc phng ỏn sp xp.
Nu cúN cụng vic thỡcúN ! cỏch sp xp
Vớd

: Xột trng hp N = 3; M = 4; 3 cụng vic lA, B, C v4
mỏy lmỏy I, II, III, IV. Khi ta thay i M, N thỡthut toỏn
khụng cúgỡ thay i. Vi N = 3 ta cús phng ỏn sp xp l
3! = 6 cỏch sp xp.
2.4. Sp xp lch trỡnh N cụng vic trờn M mỏy
- B

c 2: Tớnh tng thi gian hon thnh ca tng phng ỏn T v
chn Tmin theo trỡnh t sau :
+ Lp bng tớnh :
-Xột phng ỏn trỡnh t sn xut lA-B-C ta s lp c

2

!
"
!

#
!

$
"
$

#
$

%

%

#
%
x3 x3 x3
c1 c2 c3 c4
b1 b2 b3 b4
x2 x2 x2
a1 a2 a3 a4
x1 x1

x1

4242
B
3422
A
IVIIIIII
Máy
Công việc
2.4. Sp xp lch trỡnh N cụng vic trờn M mỏy
Vớd

: Cú3 cụng vic c b trớtrờn 4 mỏy. Thi gian tin hnh vthi
gian ch i cho bng sau:
B

c 1: S lng cỏc phng ỏn = 3! = 6
C th cúcỏc phng ỏn sau: ABC, ACB, BAC, BCA, CAB, CBA.
B

c 2: Tớnh T. Xột phng ỏn ABC

!
&'( "
!
&'%
#
!
&'(

$
&'(

x''1 + 3= 2 + x''2
x''2 + 4= 3 + x''3
T
(BAC)
= 18 giờ
T
(ACB)
= 20 giờ
T
(BCA)
= 21 giờ Vậy T
min
= 18 giờ
T
(CAB)
= 22 giờ
T
(CBA)
= 21 giờ
2.4. Sp xp lch trỡnh N cụng vic trờn M mỏy
! "#$%&'("#)"("#*&(+,&'(
+,&'(- .+(+#/(+)+(0)1(
3.1. Bài toán cực tiểu
Trong trường hợp có:
-N máy, N công việc
-Các máy đều có tính năng thay thế nhau. Do đó
mỗi công việc chỉcần bốtrí trên 1 máy.
-Chi phí các máy làm các công việc khác nhau là
khác nhau.
Ta cần bốtrí mỗi công việc trên mỗi máy sao cho

Máy
Công việc
3.1. Bài toán cực tiểu
Lập ma trận vàtính toán các bước nhưsau:
Bước 1: Bước 2 và3:
5 8 0 5 6 0
0 2 3 0 0 3
2 5 0 2 3 0
Sốphương án là3 nhưng các số0 được khoanh tr"n chỉcó 2. Ta phải đi tiếp
bước 4.
3 4 0
0 0 5
0 1 0
Kết quảta bốtrí nhưsau:
Công việc A: bốtrí trên máy III với chi phí = 6
Công việc B: bốtrí trên máy II với chi phí = 10
Công việc C: bốtrí trên máy I với chi phí = 9
Tổng chi phí: 6 + 10 + 9 = 25