CHUONG

VI

LAP LICH TRINH SAN XUAT
|. SAP XẾP THỨ TỰ TOI UU TRONG SAN XUAT DICH VỤ
Trong quá trình sản xuất, dịch vụ ta cần tiến hành nhiều
công việc khác nhau. Những công việc này cần được sắp xếp

thành một lich trình chặt chẽ và khoa học, nhất là khi có nhiều

công việc chồng chéo trong những thời kỳ cao điểm.
Muốn sắp xếp tối ưu các công việc ta cẩn nắm
nguyên tắc ưu tiên sau đây.

các

vững

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, khi ta chỉ có một máy hoặc một dây chuyền
Nguyên tắc ưu tiên được sử dụng rộng rãi khi lập danh mục
các công việc cẩn làm ngay, khi máy móc thiết bị đã chuẩn bị

xong.

Có 4 ngun tắc phổ biến sau đây:
1. Cơng uiệc được đặt hàng trước làm truée (First come first

served - FCFS).

9. Cơng

date - EDD).

uiệc phái

hồn

thành

trước làm trước (Earliest due

3. Cơng uiệc có thời gian thực
(Shortest Processing time - SPT).

hiện

ngắn

nhất

làm

trước

4. Cơng uiệc có thời gian thực hiện dài nhất làm trước
(Longest processing time - LPT). Đây chính là những cơng việc

thường có khối lượng lớn và rất quan trọng.
Ví dụ: Có 5 cơng việc A, B, C, D, E.


thời điểm giao hàng cho như bảng sau:

226

Thời

gian sản xuất và


Cơng việc

Thời ea Ơn xuất | Thai a6

A
B

6
2

5
5

z
5
=

8
3
9


18
15
23

ga

Để biết được nên áp dụng ngun tắc nào ta cần tính tốn
một số chỉ tiêu hiệu quả như sau:
* Theo nguyên tắc 1 - FCFS
- A phải làm mất 6 ngày. Xong A mới làm B. Vậy B phải chờ
mất 6 ngày. Thời gian thực hiện B mất 3 ngày. Vậy thời điểm

hoàn thành B là:

6 ngày chờ + 2 ngày thực hiện = ngày thứ 8
- Nhưng thời điểm hoàn thành yêu cầu đối với B là ngày thứ
6, vậy đã chậm mất:
8-6=2ngày
- Bằng cách tính như trên ta lập được bang sau:
ai
Thời điểm phải

Công | Thai gian sản | Thời gian hoàn [an thành yêu Teta

việc

.

xuất (ngày)


thành, kể cả

chờ đợi (ngày)

A

6

6

B

2

8

g

8

E

9

D

(+)

3


28

16

19

28

AAR

cẩu

(ngày

ú
thứ...)

-

trễ so với yêu

cầu (ngày)

8

0

6


2

0

18

4

15

23

"1

5

227


Tính các chỉ tiêu hiệu quả:
dịng thỏi gian
Thời gian hồn tất trung bình _ Tổng sre
=
a
i
Số cơng việc
việc (th)

sl


một cơng

Số cơng việc trung bình nằm trong __

ý

5

Ẹ

= 15,4 ngay

Tổng dịng thời gian

ˆ Tổng thời gian sản xui

hệ thdng (Nis)

Số ngày trễ hạn trung binh (PRụ, ) =e

an

= 9,9 ngày

*® Theo nguyên tắc 9 - EDD
a

cae
B


A
D
G
is
(+)

Dee ea

a | Thoi

2

8
3
8
9
28

gian hoan | Théi diém

yêu câu

cầu

2

6

0


8
11
19
28
68

ty = e- 13,6 ngày

Nw = 5g68 = 242
= 5 = 1,2 ngày

* Theo nguyên tắc 3 - SPT
228

gian cham

trễ &với yêu

đợi

Tính các chỉ tiêu:

TR

phai | Thdi

tot kế cả chờ hoàn thành heo
8
15
18

23

0
0
1
5


eee
ie

on

_

Thời gian hoàn | Thời điểm phải | Thời gian chậm

“.. Sản | hành kể cả chờ|hoàn thành theo| trễ so với yêu
:

B
D
A
a
E
(+)

đợi

2

3
6
8
9
28

yêu cầu

2
5
11
19
28
65

65
=>

ly

6
15
8
18
23

cầu

0
0

3
1
5
9

x
= 13 ngay

Đ

Nụ tb == 6558
TRuý

Ũ

= ae

5

1,8 ngay

* Theo nguyén tde 4 - LPT.

ae
is

4

; | Thdi gian hoàn | Thời


nee

i

E
c
A
D
B

9
8
6
5
2

(+)

28

điểm phải | Thời gian chậm

S80 |tnanh ké ca cho|hoan thanh theo} tr so với yêu
đợi

9
17
23
26
28


103

yêu cầu

23
18
8
15
6

cầu

0
0
15
11
12

48

ayia: totienpay
229


103 _ gigs
Ny) tb Seo)
28
TR


= a.

aS

= 9,6 ngày

Trình bày các chỉ tiêu trong bảng tổng hợp sau đây:

„_ | Thời gian hoàn tất | Thời gian trễ trung | Số cơng việc trưng

Các ngun tắc| ` rungtinh (N) |

bình RẠ)

K4

1.FCFS

15,4

2,75

22

2. EDD

13,6

2,42


12

3. SPT

13

2,32

1,8

4. LPT

20,6

3,68

9,6

Qua bang trên nhận thấy:
bình
TRy

Nguyên tắc 3 - SPT có lợi nhất. Thời gian hồn thành trung
tụ

= 13 ngày

= min

và thời gian


= 2,32 ngày = min. Mặc

nằm trong hệ thống

Ny,

chậm

trễ trung bình

dù vậy số cơng việc trung bình

= 18 # min, lớn hơn nguyên tắc 3 -

EDD.

Qua kinh nghiệm thực tế nhận thấy:
1- Nguyên tắc SPT
lợi của nguyên tắc này
đưới, dễ làm mất lòng
thể gây ra những thay
hạn.

2- Nguyên

tắc

thường cho ta kết quả tốt nhất. Điểm bất
là đẩy những công việc dài hạn xuống

các khách hàng quan trọng, dẫn đến có
đổi, biến động đối với các cơng việc dài

FCFS

có

các

chỉ

tiêu

dịch

vụ

hiệu

quả

khơng

cao,

nhưng khơng phải là ngun tắc xấu nhất, vì nó làm hài lịng các
khách hàng, thể hiện tính cơng bằng, được xem là một yếu tố
quan

trọng


trong

thuyết xếp hàng).
230

các

hệ

thống

(xem

thêm

chương

lý


Do đó, sau khi tinh tốn, tùy từng trường hợp, trong các đi.

kiện cụ thể ta lựa chọn lấy nguyên tắc nào thích hợp nhất để sắp
xếp các cơng việc khi lập lịch trình.

1.2. Đánh giá mức độ hợp lý của việc bố trí các cơng việc
Để kiểm tra việc bố trí các cơng việc có hợp lý hay khơng ta

tính chỉ tiêu “mức độ hợp lý” như sau:


Mức độ hợp lý (MĐHL)=

“Thời gian cịn lại
no
Số cơng việc cịn lại tính theo thời gian

Khi don vị tính là ngày thì tính như sau:
MDHL

=

Số ngày cịn lại i
tính GEn
đến EO)
thời Glenn
điểm gag
giao Nang,
hàng
n
VU
Số cơng việc cịn lại phái làm mất bao nhiêu

ngày tính đến thời điểm giao hàng

Ví dụ:

Tại một cơng ty có 3 cơng việc được đặt hàng như bảng sau.

Giả sử thời điểm chúng ta xét là ngày 25/12.

Công việc

Thời điểm giao hàng

Cơng việc cịn lại tính

A

30-12

4

B

28-12

5

Cc

27-12

2

theo Ags

Theo céng thtic trén tinh duge MDHL nhu sau:
Công việc

A

5

Mức độ hợp lý - MĐHL

Thứ tự ưu tiên

eae
=0,6

1

+8 si

2

30-25 _ | 55
5

5

231


N

an thấy:
>

MDHL


A:

- Cơng

viée

- Cơng

việc €: MĐHL

1 chting

to sé hồn

thành

sớm

hon

kỳ hạn. Không cần phải ưu tiên - xếp ưu tiên 3
- Công việc B: MDHL < 1 chứng t6 sẽ bị chậm - cần xếp ưu
tiên 1 để tập trung chỉ đạo
= 1 chứng

tỏ sẽ hồn

thành

đúng kỳ


hạn. Xếp ưu tiên 3.

Cơng dụng của chỉ tiêu MĐHL

khi lập lịch trình:

- Quyết định vị trí của các cơng việc đặc biệt.
- Lập quan hệ ưu Liên của

các công v›ệc.

- Lập quan hệ giữa các công
việc phải thực hiện.
- Điều chỉnh

việc

được

lưu lại và

thứ tự ưu tiên để thay đổi theo yêu cầu trên cơ

sở sự tiến triển của các công việc.

- Theo đõi chặt chẽ sự tiến triển và vị trí của các cơng việc.

1.3. Nguyên tắc Johnson
Nguyên


tắc Johnson

khi ta có hai máy

dùng để sắp xếp thứ tự các cơng việc

hoặc 3 máy.

lịch trình N cơng niệc trên 2 may
Mục tiêu bố trí các công việc là phải làm sao cho đống thời
gian thực hủ ¡ các cơng uiệc đó là nhỏ nhất. Nhưng thời gian
1.3.1. Lập

thực hiện môi công việc
công việc và năng suất
thời gian thức hiện nhỏ
cho tổng thời gian ngừng
Nguyên tắc Johnson
Bước

trên mỗi
của máy
nhất ta
oiệc trên

máy là cố định (do khối lượng
qu ết định). Do đó để có tổng
phải sắp xếp các công việc sao
các máy là nhỏ nhất.


gồm 4 bước sau
1 - Liệt kê tất cả các công việc và thời gian thực

chúng trên mỗi máy

bước 9 - Chọn các cơng việc có thời gian thực hiện nhỏ nhất.
+ 232


- 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 lại nằm trên máy

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, bước 3 cho đến

việc đều đã sắp xếp hết.

khi tất cả các cơng

Ví dụ:

Co 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 mỗi máy cho
như bảng sau. Dơn vị tính tối : giờ. Hỏi nên sắp xếp thứ tự các
công việc như thế nào ?

ob

Công việc

A
5
D
E

Théi gian thực hiện các công việc (h)
1 - Máy khoan

5
3
8
10
7

2- Máy tiện

2
6
4
7
12


~ Nhìn trong tồn bảng ta thấy số 9 là nhó nhất, tương ứng
A trên máy 3.
A được bố trí cuố
lùng. Loại trừ
A vì đã bố trí xong.
VỚI Cơng V:

~ Trong bảng cịn lại thì số 3 là nhỏ nhất, ứng với công vi

B trên máy 1. Vậy B được bố trí đầu tiên. Loại trừ B.

- Tiếp đến số 4 là nhỏ nhất, ứng với cơng việc C trên máy 2.
Vay C được bố trí cuối (tức là trước A).
máy

~ Có hai so 7, xét từng số một.

1 được bó trí trước.

ố 7 ứng với công việc Et

Số 7 ưng với công việc D trên máy 2 bố
233


trí sau. Tức là E đứng trước D.

Kết quả ta có được thứ tự và thời gian sắp xếp trên các máy
như sau:


Bui

Máy 1
Máy 2

lãi): cám E

3
6

7
12

D

B

A

10
7

8
4

5
2

Trích tổng thời gian thực hiện:
Dòng thời gian được biểu diễn như sau:


Gita

8

10

20

28

Máy 1 |ạ~s

E=7

D=10

©=8

Máy 1I[/
OFT

E=8

E=12

D=7

Thới gian


5

310
a

33

z21

B
E
Tổng thởi gian hoản thành A, B, C. D = 35 giờ

Qua hình trên nhận thấy:

- Tổng thời gian thực hiện tất cả các công việc trên cả 2 máy

là 3ð giờ.
- Máy 2 được huy động sau máy

h
1 ba giờ.

- May 1 được giải phóng sau 33 giờ.
- May 2 được giải phóng sau 3ð giờ.
- Máy 2 sau công việc B phải chờ mất 1 giờ.
13.2. Lập trình N cơng uiệc cho 3 máy

Sắp xếp thứ tự N cơng việc cho 3 máy có thể sử dụng nguyên
tắc Johnson nếu có đủ hai điều kiện sau:


1. Thời gian ngắn nhất trên máy 1 phải lớn hơn hoặc bằng

thời gian dài nhất trên may 2.

234


2. Thời gian ngắn nhất trên máy 3 phải lớn hơn hoặc bằng
thời gian dài nhất trên máy 2.

Ví dụ. Có bảng sau. Hãy

chuyển

ngun tắc Johnson.
Cơng việc

D

đổi để có thể áp dụng

Thời gian (h)
Máy1

(tị)

Máy 2

(tạ)


Máy 3 (tạ)

18

5

9

5

3

7

6

4

s

Gi

2

6

Hai diéu kiện kể trên đều thỏa mãn.

đổi như sau:


Ta lập bảng chuyển

Công việc

ty + tg

lg tty

A

18

14

B

8

10

c

10

9

D

9


8

Bây giờ ta sử dụng nguyên tắc Johnson

đối với trường hợp

N/2 và sẽ nhận được thứ tự sau: BACD. Kết quả này là kết quả
gần đúng, nhưng được dùng tốt trong thực tế.
‘
1.4. Trường hợp tổng quát. Sắp xếp lịch trình cho Đ cơng
việc trên M máy

Đây là trường hợp phức tạp. Ta cần áp dụng một thuật toán
khác, tuy hơi rườm rà nhưng sẽ cho ta kết quả chính xác (tối ưu).
1.4.1. Cơ sở của thuật tốn

Thuật toán này đảm bảo cho các máy (trong M máy) đều làm

việc liên tục với các công việc khác

nhau và tổng thời gian thực

hiện tất cả các công việc trên tất cả các máy là nhỏ nhất.

Chẳng hạn xét trường hợp N = 3; M = 4. Khi thay đổi N, M,

235



thuật tốn khơng có gì thay đổi.
Lập bảng sau. Số liệu trong bảng là thời gian thực hiện các
công việc trên các máy.

Má

C việc

f=

À

ay

B

by

C

tị

IV

ill

I

Ị


y

by

nh|

by

[» |

ay

L
xy
1

ag

XM

ey

S

xz |

x?
ag

D


b,

x
Cc

e
Trong

bp
Xs

ay

X;

om

by

x;

X;

by
Ẳ

:

|


e

sơ đồ các

x, x, x” là thời gian phải chờ đợi của các
công việc khi chuyển từ máy này sang máy kia. Các x, x), x” đều

được thể hiện trên sơ đồ và trên bảng tính.
Nhìn trên sơ đồ thấy hình ABCD

Do đó:

236

là 1 hình chữ nhật.


[xy tag =b,

+x:

MLO
age
PAT Ae
[xy
+ by =e, + xy

Tuong tu:


w

Kết quả có 3 hệ phương trình bậc nhất. Trong mỗi hệ có 3
ẩn số nhưng chỉ có 2 phương trình.
Chú ý: Khi N, M thay đổi thì số lượng các hệ phương trình
cũng thay đổi (tăng hoặc giảm). Nhưng

hệ phương trình khơng có gì thay đổi.
Để giải các hệ phương trình này

cách suy luận và lập các

ta cần

trường hợp bố 0í tốt nhất thì giữa xị,xạ.xạ
một cái bằng 0. Giữa

x.x'¿

lưu ý rằng

trong

sẽ phải có ít nhất

và x'¿ cũng phải có ít nhất một cái

bằng 0. Đối với x',x's và x"s cũng như vậy.
Ngay từ đầu ta chưa biết x nào bằng khơng. Giá thiết một x
nào đó bằng 0 sẽ giải ra các x khác. Chú ý rằng x chỉ có thể > 0

vì đây là thời gian chờ đợi, khơng

thê nào âm. Do đó trong q

trình giải nếu xuất hiện x < 0, chang han x = -3 < 0

thì ta cộng

thêm 3 để biến chúng bằng 0. (xem ví dụ).
Kết quả tính được tất cả các x >0. Từ đó xác định được T là
tổng thời gian thực hiện các công việc trên tất cả các máy đã xét
đến các khoảng thời gian chờ đợi
như trong bang la A, B, C.

Thay

hợp

lý, tương

ứng với thứ tự

đổi thứ tự đó ta sẽ được một T khác.

phương án thứ tự ta sẽ nhận

xác định được Tụ„

Có bao nhiêu


được bấy nhiêu giá trị T. Từ đó ta

ứng với phương án thứ tự tối ưu.

Số lượng các phương án khả năng bằng N! Tinh phức tạp của
vấn để chính là ở chỗ N thường khá lớn nên ta phải thực hiện

rất nhiều phép tính mới có thể chọn

được phương án tối ưu.
237


Nhưng về thuật tốn khơng có gì thay đổi. Số lượng phương án

khơng phụ thuộc vào M vì ta chỉ cần xếp thứ tự các công việc chứ
không phải thứ tự của các máy
1.4.2. Thuật toán
Thuật toán cụ thể được trình bày qua ví dụ sau đây:
Ví dụ: Xét trường hợp có các số liệu cho như trong bảng sau.

Thời gian tính bằng giờ.

(đu

ue

\

ul

II

B

2

c

3

bal
ee

ul
IE: =0

Iv
E=-

4

a2

2

-

4

5


a

3

`

2

- Số lượng các phương án khả năng
NI=8!=6

Cụ thể các phương án thứ tự sau đây:

ABC, BAC, ACB, BCA, CAB, CBA

- Xét phương án ABC. Chính là bảng trên
Tinh các x
Từ sơ đồ tính tốn ta có cách lập các hệ phương trình như
đã nói ở trên. Suy ra cách lập các hệ phương trình ứử bảng tính
như sau:
Xị +aa =bị +Xxạ—>

xị + số liệu bên phải = 2+xạ

238

(số liệu bên trái + xạ)



(hang 1)

(hang 2)

Tương tự:

TH

xị+4=4+xz

Xa+td=3+xs
Cho

xị =0

xu+2=B+xg

=> x =0;x3=1

Giả thiết xị =0= xạ =0;

xạ =-8. Vì các x' khơng có quyển

âm nên ta cộng chúng thêm 38. Có:
xị=3;

x¿=3;

xa =0


Tính các x”
x1+3=2+x1s

oe

=3+x"3

Gia thiét x") =0
=> x"y=1;

x"3 =2; cdc x"20

Bây giờ ta đi từ ô A.I đến ô C.IV bằng bất cứ con đường nao

cũng sẽ nhận được T' giống nhau.

Chẳng hạn theo hàng trên cùng và cột cuối cùng:
T=2+0+2+3+4+0+3+4+2=20giờ

"Theo cột đầu tiên va hàng dưới cùng:
T=2+2+3+l+ð+0+3+2+2=20giờ

Chú ý trên đường đi nếu gặp các x, x, x” dương thì ta phải
nhớ cộng cả chúng vào.
Kết quả:

Tape) =20 git
Bây giờ ta thay đổi thứ tự va tinh lại sẽ có các kết quả sau
đây (đề nghị các bạn tự tính):


TgAc, =18 giờ

Ttacp =20 giờ
239


TgcA, =2l giờ

TcAn, =22 giờ
TtcpA, =21 giờ
Thịn = TyAc, =18 giờ
Thứ tự BAC là thứ tự tối uu.
Tónh lại trình tự giải bài toán này như sau:

1. Xác định số lượng các phương án khả năng.
9. Tính tổng thời gian hoàn thành ngắn nhất
phương án T, bằng cách:

của

từng

- Lập bảng tính.
- Tính các x, x), x”.. đề biết thời gian chờ đợi của các công
việc khi chuyển từ máy này sang máy kia. Trong các x phải có

tối thiểu một x nào đó bằng 0 để đảm bảo T là nhỏ nhất của
phương án đang xét. Đối với các x', x”.. cũng như vậy.
- Xác định T bằng cách đi từ ô trái trên cùng xuống ô phải
dưới cùng theo đường nào cũng được.

3. Chọn

trong các T' của các phương án giá trị Tạ.

Phương

án thứ tự tương ứng sẽ là phương án tối ưu.
Ghi chú:

Phương án tối ưu có thể có nhiều, nhưng giá trị Tụ,

thì chỉ

có một, tức là T' của các phương án tối ưu đều phải bằng nhau và

bang Trin -

Chẳng hạn ta xem lại ví dụ N⁄3 tại điểm 1-3-2. Két qua da
tìm được theo nguyên tắc Johnson, thứ tự tối ưu là BACD. Nhưng
theo thuật tốn nói trong điểm này sẽ tìm được một phương án

khác, cũng tối ưu, đó là thứ tự BCAD. Kết quả tính tốn như sau:
Phương án theo Johnson:

240


B

A


|

|

oe

3

z

18

ao

5

9

xị=14

at

Cc

6

D
Cho


§

xạ=

7

4

uO]

2

xị =0. Có:

0+3=
x;13
= xy +
=-10
-10+5=6+x
=> x3 = y-11
~l1l1+4=7+xạ

= xạ =—14

Cong tat ca cde x với 14 được:
x, =14
Xp

1


Cho xị=0.

Có:

0+7=5+x'9 xy

=2

24+9=4+x'y > x'y=7
74+5=24+x', x"; =10
T=5+13+64+7+0+2+10+6=49 gis
Di theo các con đường khác cũng có kết quả tương tự.

Phương án khác
Xét

5

Ì

thứ tự B Ở A Ð tá tính được

như sau:

6

ig

|



B

5

4

Cc

6

5

A

13

9

D

7

6

A

Cho xị =0. Có:
0+3=6+xạ = x¿=-3
-8+4=13+

xạ = xạ =-12

-124+5=7+x4 > x4 =-14
Cong 14 vào tất cả các x có:

xị =14

Xj =2

Xq =11

Xạ=

Cho xị =0. Có:
0+7=4+x¿ạ=x›¿=3

384+5=5+x'3 >x'3 =3
3+09=2+x¿=x'+=10
T=5+6+13+7+0+2+10+6=49giờ

Đi theo các con đường khác cũng có kết quả tương tự.
Như vậy cả hai phương án nói trên đều có T = 49 giờ.
Nói một cách khác nguyên tắc Johnson là một trường hợp
riêng của thuật toán tổng quái.

242


II. PHUONG PHAP PHAN CONG CÔNG VIỆC CHO CAC MAY
Trong trường hợp ta có:

- N cong viéc. N may

- Các máy đều có tính năng thay thế lẫn nhau. Do
đó
- Mỗi cơng việc chỉ cần bố trí trên 1 máy

Một máy chỉ phụ trách một cơng việc

- Chi phí các máy

làm các cơng việc là khác nhau vì khối

lượng các công việc khác nhau và đơn giá 1 ca máy

của các máy

cũng khơng giống nhau.
Ta cần bố trí mỗi cơng việc trên mỗi máy sao cho tổng
chỉ
phí thực hiện tất cả các công việc trên tất cả các máy là
nhỏ
nhất.
Mục

này giải

quyết bài tốn

nói trên.


Đây

là một

loại bài

tốn của Quy hoạch tuyến tính có tên gọi là bai todn chọn. Có
thể áp dụng bài tốn này khi cần phân cơng cơng việc cho các

.

máy, phân chia các hợp đồng cho từng bộ phận, phân
bán hàng ở các cửa hàng...

cơng người

Thuật tốn giải được trình bay qua ví dụ sau:
Ví dụ: Có 3 cơng việc R-34, 9-66, T-50 và có 3 may A,
B, C.

Chi phí có cơng việc thực hiện trên các máy cho như bảng sau.

Tìm phương án bố trí các cơng việc trên các máy sao cho tổng chỉ

phí là nhỏ nhất.

Đơn vị tính USD
Máy

A


B

R-34

11

14

8-66

6

8

T-50

10

11

9

12

7

Cơng việc

Cc


243


Giai

Bước 1. Chọn trong mỗi
hàng trừ đi số min đó.

Cơng việc

Máy

hàng
^

R-34
S-66
T-50

lấy các số trong

1 số min,
B

Cc

9
2


5

3
0

A

B

&

6

Bước 2. Chọn trong mỗi cột 1 số min, lấy các số trong cột trừ
đi số min đó.

Máy|

(Cơng việc
R-34

0
3

0
2

S-86
T-50


Cc

0

Bước 3. Chọn hàng nào có 1 số 0, khoanh

đường thẳng xuyên suốt cột.
cột nào

- Chọn

có

1 số 0 khoanh

trịn

trịn số 0 đó, kẻ

số 0 đó,

kể

đường

thẳng xun suốt hàng.

Nếu số số 0 khoanh tròn = Số đáp án cần tìm thì bài tốn

đã giải xong.


Nếu số số 0 khoanh tròn chưa bằng số đáp an can tim ta
phải thực hiện tiếp bước 4.

Máy
Công việc

R-34
S-66
T-50


Trong ví dụ này sau khi thực hiện bước 3 ta mới có 2 số 0
khoanh trịn chưa bằng số đáp án cần tim do dé ta phai làm bước 4.
Bước 4. Ta tạo thêm sốÖ bằng cách:
Chọn trong các số không nằm trên các đường thẳng 1 số min
lấy các số không nằm trên các đường thắng trừ đi số min đó.
Lấy số min đó cộng vào các số nằm
đường

thẳng.

Sau

trên giao điểm của các

đó ta lại bố trí cơng việc như đã trình bày ở

bước 3 cứ tiếp tục như vậy cho đến khi nào số 0 khoanh


bằng số đáp án cần tìm thì bài tốn mới giải xong.

trịn

Các cơng việc sẽ được bố trí vào các ư có số 0 khoanh trịn.
Như vậy chúng ta sẽ có tổng thời gian thực hiện hoặc tổng chỉ
phí thực hiện các cơng việc là tối thiểu.
Máy
Cong viéc

A

R-34
S-66
T-50

Trong ví dụ này sau khi thực hiện bước 4 ta bố trí các cơng
việc như đã trình bày ở bước ä.

Cơng việc lt34 sẽ bố trí vào máy € với chỉ phí: 6 USD
Cơng việc 8-66 sẽ bố trí vào máy B với chỉ phí: 10 USD
Cơng việc T-õ0 sẽ bố trí vào máy A với chỉ phí: 9 USD

"Tổng chỉ phí thực hiện các cơng việc: 6 + 10 +
là tối thiểu.
Bài tốn phân công công việc trên các máy

9 = 25 USD

đã nêu lên được


đặt ra với mục tiêu giảm tối thiểu tống chỉ phí hoặc giảm tối
thiểu tổng thời gian thực hiện các cơng việc.
- Nếu

cùng

đặt ra vdi 2 muc

bài tốn phân

công công oiệc trên các máy

được

tiéu:

246