sản xuất

1

MỤC LỤC
MỤC LỤC 1
DANH SÁCH CÁC HÌNH VẼ 3
DANH SÁCH CÁC BẢNG 4
BẢNG TỪ VIẾT TẮT 5
TỪ KHÓA 6
MỞ ĐẦU 7
CHƢƠNG 1 : TỐI ƢU HÓA ĐÀN KIẾN VÀ ỨNG DỤNG 9
10
n TSP 10
1.1.2 13
1.2 Phƣơ ƣ 16
16
17
21
22
1.3 ƣ 24
1.3.1 ng 24
1.3.2 25
ƣơng 26
a s 26
1.3.5 S ng c viên 28
29
CHƢƠNG 2 : BÀI TOÁN LẬP LỊCH SẢN XUẤT VÀ CÁC PHƢƠNG
PHÁP GIẢI CHÍNH 30
2.1 Giới thiệu bài toán lập lịch sản xuất (Job shop scheduling - JSS) 30
2.2 Các cách tiếp cận truyền thống 32

3

DANH SÁCH CÁC HÌNH VẼ
Hình 1 : Lƣợc đồ thuật toán ACO 18
Hình 2: Lƣơc đồ của thuật toán nhánh cận 35
Hình 3: Lƣợc đồ thuật toán di truyền 37
Hình 4: Ma trận thể hiện trình tự và thời gian xử lý 41
Hình 5: Đồ thị cấu trúc cho bài toán lập lịch sản xuất 2 công việc thực hiện
trên 3 máy 41
Hình 6: Một hành trình của kiến trên đồ thị cấu trúc 42
Hình 7: Lƣợc đồ thuật toán ACO giải bài toán lập lịch sản xuất 47
sản xuất

4

DANH SÁCH CÁC BẢNG
Bảng 1: Bài toán lập lịch sản xuất 3 công việc thực hiện trên 3 máy 31
Bảng 2: Bài toán lập lịch sản xuất 10 công việc thực hiện trên 10 máy 31
Bảng 3: Bài toán gia công trên 2 máy 32
Bảng 4: Bài toán lập lịch sản xuất gồm 2 công việc thực hiện trên 3 máy 41
Bảng 5: Độ phức tạp của các thuật toán MMAS, SMMAS, MLAS 48
Bảng 6: Các tham số sử dụng cho các thuật toán ACO 50
Bảng 7: Kết quả thực nghiệm MMAS với 4 bộ dữ liệu Orb1 đến Orb4 50
Bảng 8: Kết quả thực nghiệm MMAS cho các bộ dữ liệu chuẩn 51
Bảng 9: So sánh kết quả tốt nhất sau 10 lần chạy của MMAS, SMMAS và
MLAS 52
Bảng 10: So sánh kết quả trung bình sau 10 lần chạy của MMAS, SMMAS
và MLAS 53
sản xuất


(Hệ kiến đa mức MLAS)
7
Opt
Optimization
8
Avg
Average
9
TSP
Travelling Salesman Problem
(Bài toán ngƣời chào hàng)
10
JSS
Job shop scheduling
(Bài toán lập lịch sản xuất)
11
g-best
global-best
12
i-best
iteration-best

sản xuất

6

TỪ KHÓA
Ant colony optimization algorithm, ACO convergence, Job shop scheduling
problem, Ant System, Max Min Ant System, Ant Colony System


. Ƣu điểm của phƣơng pháp đề xuất kiểm kết
quả trên các bộ dữ liệu chuẩn (benchmark data) của
sản xuất

8

sản xuất. Các kết quả nghiên cứu đƣợc công bố trong hai báo cáo khoa học ở hội
nghị quốc tế IEEE RIVF 2006 và PRIMA 2008 (xem [17], [4]).
Ngoài phần kết luận, luận văn đƣợc trình bày nhƣ sau :
Chƣơng 1 :
Giới thiệu : lịch sử phát triển,
ACO, và .
Chƣơng 2 : B sản xuất và các phƣơng pháp giải chính
Trong chƣơng này, chúng tôi sản xuất
chính gi .
Chƣơng 3 : sản xuất
T chung để lập lịch
sản xuất. (Đồng thời trong chƣơng này chúng tôi trình bày các cải tiến cụ thể
trong áp dụng tối ƣu hóa đàn kiến với bài toán lập lịch)
Chƣơng 4
lập lịch sản xuất nghiệm và đánh giá. sản xuất

9

CHƢƠNG 1
TỐI ƢU HÓA ĐÀN KIẾN VÀ ỨNG DỤNG
Tối ƣu hóa đàn kiến (Ant Colony Optimization - ACO) là cách tiếp cận meta-

[8], [23]).
1.1.1
1.1.1.1

)
),( EVG
V
E
),( ji
Vji,
ji
d
,
(
ji
d
,
ijji
dd
,,
).
Nhƣ vậy, với đồ thị không đối xứng sẽ có
)!1(n
đƣờng đi chấp nhận đƣợc và
2
)!1(n
với đồ thị đối xứng. Với n lớn thì ta không thể tìm hết các đƣờng đi và chỉ
có thể tìm đƣợc một lời giải đủ tốt bằng các phƣơng pháp tìm kiếm địa phƣơng,
tìm kiếm heuristic, tính toán tiến hóa h
.

(1.1)

,
ij
ij
ij
d
1
0
0
),
k
i
N
.

k
i
Nj sản xuất

12

Cập nhật mùi
)1,0(
:
Nc
[7].

:
.
(reinforcement learning sản xuất

13

.
Nhƣ
.
1.1.2
[10]
.
1.1.2.1 (Ant Colony System)
(xem [14], [12], [8]
.
:

s
sau :

j
t
s
ijij

*
:

)()1(
1
tL
gl
ijij
(1.6)

)(tL
gl
*
(t).
(xem
[8]).
.
1.1.2.2 (Max-Min Ant System)
. MMAS (xem [22]
g -
i -
(stagnation
sản xuất

15

(
max
(
min


16

min
min
.
1.2
(ACO metaheuristic
(ACO Algorithms .

:
Xét bài toán cực tiểu hóa
),,( fS
trong đó S là tập hợp hữu hạn trạng thái, f
là hàm mục tiêu xác định trên S còn là các ràng buộc để xác định S qua các
thành phần của tập hữu hạn C và các liên kết của tập này. Các tập S, C, và có
các đặc tính sau :
C = {c
1
, c
2
, …, c
n
} là tập hữu hạn gồm n thành phần. Ta ký hiệu X là tập các
dãy trong C có độ dài không quá h :
X={<u
0
, …, u
k
> | u

kk
uux , ,
1
là mở rộng đƣợc thì tồn tại từ xác định đƣợc tập con
J(x
k
) của C sao cho với mọi u
k+1
J(x
k
) thì
1101
, ,,
kk
uuux
là mở rộng đƣợc
và
*
Xx
k
khi J(x
k
) là rỗng.
Với mọi
00
Cu
, thủ tục mở rộng nêu trên xây dựng đƣợc mọi phần tử của X
*
.
Không giảm tổng quả ta giả thiết rằng có tƣơng ứng giữa các phần tử trong X

thành phần mở rộng là j khi thành phần cuối cùng của x
k
là i theo thủ tục nêu trên
(h
i,j
>0 (i,j)). Đàn kiến m con sẽ xây dựng lời giải trên đồ thị đầy đủ có trọng số
G = (V, E, H, ) trong đó V là tập đỉnh tƣơng ứng với tập thành phần C ở trên, E
là tập các cạnh, H là vector các trọng số heuristic của cạnh tƣơng ứng còn là
vector vết mùi tích lũy đƣợc ban đầu với khởi tạo bằng
0
. Đồ thị G đƣợc gọi là
đồ thị cấu trúc của bài toán.
Với điều kiện dừng đã chọn (giả sử nhƣ là với số lần lặp N
c
xác định trƣớc)
các thuật toán đƣợc mô tả hình thức nhƣ sau :
sản xuất

18 Procedure
Begin

while ) do
begin

)

end;

,
),|(
k
xJj
ju
ju
yu
yu
k
h
h
xyP
(1.9)

Quá trình này tiếp tục cho tới khi mỗi con kiến l đều tìm đƣợc lời giải chấp
nhận đƣợc x(l) X
*
và do đó
Slxls ))(()(
. Để tiện trình bày, về sau ta sẽ xem
x(l) và s(l) nhƣ nhau đều là thể hiện của lời giải chấp nhận đƣợc và không phân
biệt X
*
với S. Ký hiệu w(t) là trạng thái tốt nhất các con kiến tìm đƣợc cho tới lúc
0
)(
k
xJy

ngƣợc lại

, khi đó ở mỗi bƣớc lặp cƣờng độ vết mùi sẽ thay đổi
theo một trong hai quy tắc thƣờng dùng sau đây, đƣợc gọi là các quy tắc cập nhật
mùi hai mức.
Quy tắc ACS : Quy tắc này phỏng theo quy tắc cập nhật mùi của thuật toán
hệ đàn kiến ACS bao gồm cả cập nhật địa phƣơng và cập nhật toàn cục.
Cập nhật mùi địa phương : nếu con kiến l thăm cạnh (i, j), tức là (i, j) s(l) thì
cạnh này sẽ thay đổi mùi theo công thức :

1
)1(
ijij
(1.10.1)

Cập nhật mùi toàn cục : Cập nhật mùi toàn cục chỉ áp dụng cho các cạnh
thuộc w(t) nhƣ sau :

))(()1( twg
ijij

)(),( twji
(1.10.2)

Quy tắc MMAS : Quy tắc này thực hiện theo cách cập nhật mùi của thuật
toán MMAS, sau khi mỗi con kiến đề xây dựng xong lời giải ở mỗi bƣớc lặp, vết
mùi đƣợc thay đổi theo công thức sau : ijijij
)1(
(1.11)

(xem [16]) :
(i, :

1
)1(
ijij
(1.13.1)

- -
:

2
)1(
ijij
(1.13.2) (i,j) w(t)
)(),( twji

)(),(: lsjil

ngƣợc lại
sản xuất

21

ij
0
1

:
Định lý 1.2.3.1 ([15]) :
Nếu cƣờng độ các vệt mùi nằm trong khoảng [
maxmin
,
] thì với xác suất 1 lời
giải tốt nhất w(t) luôn hội tụ đến lời giải tối ƣu.
Các thuật toán ACO hiện nay (hay theo hai cách cập nhật mùi nói trên) đều
thỏa mãn tính chất này. Nhƣng về mặt thực tế, các bài toán tối ƣu không thể tìm
ra đƣợc lời giải tối ƣu nên định lý không có ý nghĩa thực tế.

))1(())(( twgtwg
)1()( twtw
sản xuất

22

0
t
0
),( tttw
ji,
.
Định lý 1.2.3.2 (xem [15])
Giả sử cạnh (i, j) thuộc vào lời giải chấp nhận đƣợc s nào đó và tồn tại T sao
cho
Tttwji ),(),(
thì các khẳng định sau đây là đúng :
)(
,


.

min0
1
10
,
.
sản xuất

23

min
min
.
)(
min1
2
ji,
min
))((,,
21
twg
.
1
2
1
2
, và theo cách
cập nhật mùi này thì không cần quá trình bay hơi nữa vì trong mỗi vòng lặp hai

là đánh giá xem khả năng thành phố i và thành phố j có nằm
trong một hành trình hay nó là độ thích hợp vị trí.
) các kết quả đạt đƣợc là tốt hơn
với vệt mùi
ij
là độ thích hợp khi sắp công việc j vào vị trí i. Đó là do vai trò
khác nhau của các hoán vị kết quả trong hai bài toán đó. Trong bài toán TSP, các
hoán vị là tuần hoàn và chỉ có duy nhất thứ tự quan hệ giữa các thành phần mới là
quan trọng và chú ý rằng hoán vị (1 2 … n) và hoán vị
'
-
(cũng nhƣ
các bài toán lập lịch khác), và
'
biểu diễn hai lời giải khác nhau với những chi
sản xuất

25

phí khác nhau hoàn toàn. Tuy nhiên cần chú ý rằng, trong lý thuyết cả hai lựa
chọn đều là có thể bởi vì bất kỳ lời giải nào trong không gian tìm kiếm với hai
cách thể hiện này.
Công việc định nghĩa các vệt mùi rất quan trọng và một sự lựa chọn tồi tại
một bƣớc sẽ có thể dẫn đến giảm hiệu quả của thuật toán. May mắn là vời nhiều
bài toán, lựa chọn theo trực giác đồng thời
(supersequence) .
1.3.2 tin heuristic
Việc sử dụng các thông tin heuristic để xây dựng lời giải của các con kiến
trực tiếp theo xác suất là quan trọng vì nó tận dụng các tri thức xác định của bài
toán. Các tri thức này thƣờng là những yếu tố có sẵn tĩnh hoặc động. Trong các