ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ

NGUYÔN XUÂN MINH

NGHIÊN CứU CáC BàI TOáNLịCH BIểU Và ứNG DụNG

LUậN VĂN THạC Sĩ CÔNG NGHệ THÔNG TIN

H Ni - 2015


ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ

NGUYÔN XUÂN MINH

NGHIÊN CứU CáC BàI TOáNLịCH BIểU Và ứNG DụNG
Chuyờn ngành: Hệ thống thông tin
Mã số: 60 48 01 04

LUËN VĂN THạC Sĩ CÔNG NGHệ THÔNG TIN

Ngi hng dn khoa học: GS.TS Vũ Đức Thi

Hà Nội - 2015


LỜI CẢM ƠN

Trước hết, tôi vô cùng biết ơn GS.TS. Vũ Đức Thi, người thầy đã trực tiếp dành


MỤC LỤC
LỜI CẢM ƠN ...............................................................................................................
LỜI CAM ĐOAN ..........................................................................................................
MỤC LỤC .....................................................................................................................
DANH MỤC CÁC BẢNG ............................................................................................
DANH MỤC CÁC HÌNH VẼ, BIỂU ĐỒ ......................................................................
MỞ ĐẦU.......................................................................................................................
CHƯƠNG 1. TỔNG QUAN VỀ BÀI TOÁN LẬP LỊCH ............................................ 1
1.1. Định nghĩa bài toán lập lịch Jobshop (JSP) ....................................................... 1
1.2. Tình hình nghiên cứu thuật tốn tìm kiếm lịch biểu tối ưu................................. 2
1.2.1. Tình hình nghiên cứu trên thế giới.............................................................. 2
1.2.2. Tình hình nghiên cứu trong nước................................................................ 3
1.3. Các phương pháp tiếp cận giải bài toán lập lịch................................................. 3
1.2.3. Cách tiếp cận chính xác, thuật tốn nhánh cận ............................................ 3
1.2.4. Cách tiếp cận gần đúng .............................................................................. 4
CHƯƠNG 2. THUẬT TOÁN DI TRUYỀN .............................................................. 18
2.1. Lịch sử ra đời .................................................................................................. 18
2.2. Một số khái niệm cơ bản ................................................................................. 18
2.2.1. Cá thể, nhiễm sắc thể................................................................................ 18
2.2.2. Quần thể ................................................................................................... 18
2.2.3. Chọn lọc ................................................................................................... 18
2.2.4. Lai ghép ................................................................................................... 19
2.2.5. Đột biến ................................................................................................... 20
2.3. Lưu đồ thuật toán di truyền đơn giản ............................................................... 20
2.4. Các tham số của thuật toán di truyền ............................................................... 21
2.4.1. Kích thước quần thể ................................................................................. 21
2.4.2. Xác suất lai ghép ...................................................................................... 22
2.4.3. Xác suất đột biến ...................................................................................... 22
2.5. Khởi tạo quần thể ban đầu ............................................................................... 22

4.4. Kết quả thực nghiệm ....................................................................................... 65
KẾT LUẬN ............................................................................................................... 66


i
DANH MỤC CÁC KÝ HIỆU VÀ CHỮ VIẾT TẮT
Tiếng anh
Branch and Bound Algorithm

Viết tắt
BB

Ý nghĩa
Thuật toán nhánh cận

Crossover

Lai ghép, trao đổi chéo

Fitness

Độ thích nghi, hàm thích nghi

Genetic Algorithm

GA

Thuật tốn di truyền

Integer Linear Programming


Bài toán lập lịch Jobshop

Flowshop Scheduling Problem

FSP

Bài toán lập lịch Flow shop

Permutation Flowshop
SchedulingProblem

PFSP

Bài toán lập lịch Flow shop hoán vị


ii
DANH MỤC CÁC BẢNG
Bảng 1.1: Bài tốn JSP 3 cơng việc, 3 máy .................................................................. 1
Bảng 1.2: Bài toán lập lịch 1 máy ................................................................................ 6
Bảng 1.3: Tính tốn của G(S ) ..................................................................................... 6
Bảng 1.4: Tính tốn của ( ) .................................................................................... 7
Bảng 1.5: Tính tốn của ( ) .................................................................................... 8
Bảng 1.6: Tính tốn của ( ) .................................................................................... 8
Bảng 1.7: Tính tốn của ( ) .................................................................................... 9
Bảng 1.8: Tính tốn của ( ) .................................................................................. 10
Bảng 1.9: Tính tốn ∑

cho 3 tuần tự cơng nghệ .................................................. 12

Bảng 4.3: Kết quả chạy thực nghiệm ......................................................................... 65


iii
DANH MỤC CÁC HÌNH VẼ, BIỂU ĐỒ
Hình 1.1: Các tiếp cận cho bài tốn lập lịch JSP .......................................................... 3
Hình 1.2: Tuần tự công nghệ

bằng cách trao đổi cặp công việc liền kề .................. 12

Hình 1.3: Tuần tự cơng nghệ

bằng cách trao đổi cặp cơng việc liền kề ................... 13

Hình 1.4: Tuần tự công nghệ S bằng cách trao đổi cặp cơng việc liền kề .................. 14
Hình 1.5: Tuần tự cơng nghệ

bằng cách trao đổi cặp công việc liền kề ................... 15

Hình 1.6: Tuần tự cơng nghệ

bằng cách trao đổi cặp cơng việc liền kề .................. 16

Hình 2.1: Cá thể cha mẹ cho phép lai ghép một điểm................................................. 19
Hình 2.2: Hai cá thể con sau khilai ghép một điểm .................................................... 19
Hình 2.3: Cá thể cha mẹ cho phép lai ghép hai điểm .................................................. 19
Hình 2.4: Hai cá thể con sau lai ghép hai điểm........................................................... 19
Hình 2.5: Cá thể cha mẹ cho phép lai ghép đồng nhất ................................................ 20
Hình 2.6: Hai cá thể con sau lai ghép đồng nhất......................................................... 20
Hình 2.7: Cá thể ban đầu trước đột biến ..................................................................... 20

Hình 3.17: Các cá thể cha tham gia lai ghép............................................................... 51
Hình 3.18: Cá thể con sau lai ghép ............................................................................. 51
Hình 4.1: Phân lớp các lịch biểu ................................................................................ 53
Hình 4.2: Lịch khơng tích cực.................................................................................... 54
Hình 4.3: Lịch biểu bán tích cực ................................................................................ 54
Hình 4.4: Lịch biểu tích cực....................................................................................... 55
Hình 4.5: Lập lịch sử dụng thuật tốn GT .................................................................. 57
Hình 4.6: Một lời giải hợp lệ cho JSP 3x3 ................................................................. 59
Hình 4.7: Cá thể cha cho phép đột biến ...................................................................... 61
Hình 4.8: Cá thể con thu được sau phép đội biến ....................................................... 61
Hình 4.9: Cá thể cha tham gia lai ghép....................................................................... 63
Hình 4.10: Cá thể con sau lai ghép ............................................................................. 63
Hình P.1: Cấu trúc dữ liệu đầu vào của bài toán MT06 .............................................. 75
Hình P.2: Giao diện chương trình .............................................................................. 76
Hình P.3: Q trình tiến hóa bài tốn MT06 .............................................................. 76


MỞ ĐẦU
Lý do chọn đề tài
Lập lịch là một chủ đề quan trọng trong lĩnh vực nghiên cứu hoạt động xuất
hiện từ đầu những năm 1950. Mục tiêu chính của lập lịch là phân phối một cách hiệu
quả tài nguyên dùng chung qua thời gian hồn thành các tác vụ.
Có rất nhiều các bài toán quan trọng trong thực tế của lập lịch như: Lập lịch sản
xuất; lập lịch xếp lớp cho giảng viên; lập lịch thực hiện công việc cho dự án; lập lịch
trực cho bác sỹ, y tá trong bệnh viện; lập lịch hàng không, lập lịch tàu hỏa…
Với nhiều ứng dụng như vậy việc nghiên cứu và đưa ra một thuật tốn có thể
thống kê một lịch biểu để thực hiện cơng việc hồn thành trong thời gian tối ưu là vô
cùng quan trọng.
Từ năm 1950 đến nay mặc dù có rất nhiều cơng trình nghiên cứu về lập lịch
được đề xuất. Nhưng có hai vấn đề cần quan tâm xung quanh bài tốn lập lịch đó là

những bài tốn được nghiên cứu nhiều nhất và là một mơ hình phát triển tốt về lý
thuyết lập lịch. Ngồi ra, một động lực khác giúp JSP được thúc đẩy mạnh mẽ là các
ứng dụng của nó trong thực tế và cuộc sống sản xuất. Vì vậy em mạnh dạn chọn đề tài
luận văn thạc sĩ “Nghiên cứu các bài toán lịch biểu và ứng dụng”.
Bố cục của luận văn
Nội dung của luận văn bao gồm 4 chương:
Chương 1. Tổng quan về bài tốn lập lịch
Chương này trình bày tổng quan về bài tốn JSP, tình hình nghiên cứu, các
hướng tiếp cận giải quyết bài toán JSP.
Chương 2. Thuật toán di truyền
Chương này trình bày một số khái niệm cơ bản trong thuật toán di truyền, các
tham số đầu vào của thuật di truyền, các toán tử của thuật toán di truyền và thuật toán
di truyền.
Chương 3. Hai bài toán con của bài tốn lập lịch JSP
Chương này trình bày các khái niệm cơ bản liên quan đến hai bài toán con của
JSP đó là bài tốn lập lịch Flowshop hốn vị (PFSP) và Flow shop (FSP) và thuật toán
Johnson cho bài toán Flowshop hoán vị 2 máy và 3 máy có hạn chế điều kiện. Cuối
cùng, trình bày thuật tốn di truyền mã hóa số tự nhiên cho hai bài toán này.
Chương 4. Một thuật toán di truyền lai cho bài tốn lập lịch job shop
Chương này trình bày một thuật toán di truyền lai là kết hợp thuật toán di
truyền với các kỹ thuật tìm kiếm khác cho bài tốn JSP và xây dựng chương trình
minh họa cho thuật toán di truyền lai.


1
CHƯƠNG 1. TỔNG QUAN VỀ BÀI TOÁN LẬP LỊCH
1.1. Định nghĩa bài toán lập lịch Jobshop (JSP)
Bài toán lập lịch job shop tổng quát được phát biểu như sau:
công việc { }


(từ khi bắt

đầu xử lý cho tới khi kết thúc xử lý không bị ngắt);
e) Thời gian bắt đầu và thời gian hoàn thành xử lý thao tác
lượt là

và

. Thời gian xử lý thao tác

được ký hiệu là

được ký hiệu lần

;

f) Thời gian hoàn thành việc xử lý tất cả các công việc được gọi mà makespan
và được ký hiệu là

.

Việc giải bài toán lập lịch job shop là xác định một lịch biểu (thứ tự xử lý các
công việc ở trên m máy) sao cho makespan là nhỏ nhất.
Để minh họa cho bài tốn, một ví dụ về bài tốn JSP 3x3 được cho trong Bảng
1.1. Dữ liệu vào bao gồm một tuần tự công nghệ của các máy cho mỗi công việc và
thời gian xử lý của mỗi công việc ở trên mỗi máy (trong dấu ngặc đơn).
Máy (thời gian xử lý)

Cơng việc
1


; tức là, cơng việc 1 ban đầu được xử lý trên máy 1 với thời gian xử lý là 3,

và tiếp theo, được xử lý trên máy 2 với thời gian xử lý là 3, và tiếp theo được xử lý
trên máy 3 với thời gian xử lý là 3; các thao tác
tự:

→
→

→
.

các thao tác

được xử lý trên các máy theo trình

được xử lý trên các máy theo trình tự:

→


2
Bài tốn này khơng chỉ là NP - khó (NP-hard) mà cịn nổi tiếng là một trong
những bài tốn tối ưu tổ hợp khó tính tốn nhất cho đến nay. Độ phức tạp của bài toán
này là một trong những lý do tại sao bài toán này được nghiên cứu một cách rộng rãi.
Cho đến ngày nay vẫn chưa có một phương pháp nào giải quyết bài toán JSP
một cách chính xác và thời gian nhanh.
1.2. Tình hình nghiên cứu thuật tốn tìm kiếm lịch biểu tối ưu
1.2.1. Tình hình nghiên cứu trên thế giới



3
Search)bởi Dell’Amico và Trubian (1993), Taillard (1994), Barnes và Chambers
(1995), Nowicki và Smutnicki (1996) và Thomsen (1997), Thuật toán di truyền
(Genetic Algorithms)bởi Storer (1992), Yamada và Nakano (1992), Pesch (1993) và
Dorndorf và Pesch (1995), vàkỹ thuật Tìm kiếm địa phương có chỉ dẫn (Guided Local
Search)đề xuất bởiBalas và Vazacopoulos (1998)[5].
Các tiếp cận đã được đề xuất để giải bài toán JSP được trình bày trong Hình 1.1.
Các phương
pháp gần đúng

Các phương
pháp chính xác

Các luật ưu
tiên nhanh

Dịch chuyển
nút cổ chai

Các kỹ thuật
nhánh cận

Cơng thức
tốn học

Trí tuệ
nhân tạo
Tìm kiếm


4
để giải quyết các bài toán rời rạc và tổ hợp. Mơ hình được sử dụng để tìm kiếm là mơ
hình cây phân cấp. Tư tưởng cơ bản của phương pháp là trong quá trình tìm kiếm
lời giải, sẽ phân hoạch tập các phương án của bài toán thành hai hay nhiều tập con
biểu diễn như một nút của cây tìm kiếm và cố gắng bằng phép đánh giá cận),
tìm cách loại bỏ các nhánh cây (những tập con các phương án của bài tốn) mà ta
biết chắc chắn khơng phải là phương án tối ưu. Mặc dù trong trường hợp xấu nhấtthuật
tốn sẽ duyệt tồn bộ, nhưng những trường hợp cụ thể nó rút ngắn đáng kể
thời gian tìm kiếm.
Hiệu quả của thuật toán nhánh cận phụ thuộc cách thức phân nhánh và đánh giá
cận. Việc phân nhánh sai sẽ không làm giảm việc bỏ bớt các phương án khơng tốt hoặc
thậm chí cũng khơng thể thu gọn các miền khả thi xuống. Đánh giá cận sai sẽ tạo ra
các nhánh khơng chính xác làm ảnh hưởng đến số lượng các phương án hoặc các tập
con có thể lược bỏ được. Như vậy thì một chiến lược nhánh cận không tốt sẽ làm giảm
việc xác định các phương án khả thi và lúc này thuật toán sẽ liệt kê tồn bộ các cấu
hình có thể cho dù bài tốn khơng thực sự lớn. Chính vì thế những quy tắc khác nhau
được áp dụng với mục đích làm sao để phân nhánh và đánh giá cận đúng là vấn đề
quan trọng trong việc xây dựng thuật toán.
Với bài toán lập lịch, thì lịch biểu các cơng việc được mơ tả bằng một đồ thịnối
rời (disjunctive graph). Tất cả các công đoạn cùng một công việc được nốithành một
chuỗi các cung nối liền và các cung nối rời giữ các công đoạn thực hiệntrên cùng một
máy. Việc lập lịch sẽ trở thành việc sắp thứ tự các công việc trên từngmáy, nghĩa là
làm cố định mối liên hệ trước sau giữa các công đoạn trên cùng mộtmáy bằng cách
thay đổi hướng các cung nối rời theo một hướng cố định ta sẽ cómột lời giải khả thi,
mỗi lời giải khả thi này ta tính được hàm mục tiêu
chiềudài lớn nhất đi từ nút
nguồn đến nút đích.
Một vấn đề gặp phải của phương pháp nhánh cận là thời gian tính tốn lớn.
1.2.4. Cách tiếp cận gần đúng

1.2.4.2. Thuật tốn mơ phỏng luyện kim (Simulated Annealing)
Đây là quá trình tìm kiếm bắt nguồn trong khoa học vật liệu. Nó lần đầu tiên
được phát triển cho mơ phỏng các q trình luyện kim. Trong lý thuyết lập lịch, nó
được áp dụng như một cơng cụ tìm kiếm địa phương để cải thiện lịch biểu ban đầu.
Thuật toán dưới đây chỉ rõ các bước cho việc tạo một lịch cho bài toán một máy[10].
Thuật toán
Chúng ta hãy gọi,
: Lịch ứng cử viên (Tuần tự công nghệ ứng cử viên)
: Lịch biểu tốt nhất được tìm thấy đến nay (Tuần tự công nghệ tốt nhất)
: Lịch được xây dựng tại vòng lặp thứ k (k - Biến đếm vịng lặp)
( ): Tiêu chí mong muốn (giá trị tốt nhất của lịch biểu)
( ): Giá trị của lịch biểu tại vòng lặp thứ k
( ): Giá trị của lịch biểu ứng cử viên
( , ): Xác suất di truyển từ lịch biểu đến lịch biểu tại vòng lặp thứ k
( ,
trị

) = exp (

(

)

(

)

)

Trong đó,

Cho thể hiện 1|| ∑
, giải bài toán được cho trong Bảng 1.2 sử dụng
phương pháp mô phỏng luyện kim, áp dụng với số bước lặp

≤ 5.

Cơng việc
3

6

2

5

4

7

13

9

3

1

2

4

6

2

5

4

7

13

9

3

9

11

16

0

2

0

7


:

Cơng việc
6

3

2

5

7

4

13

9

6

9

11

16

0

5

Thì

)

( ) = 43. Bây giờ ta hãy kiểm tra điều kiện
( ) < ( ) < ( ) thì = GOTO Bước 3.
( ) < ( ) thì
= & =
GOTO Bước 3.
( ) > ( ) (điều kiện này đúng)
Sinh

Tìm ( ,

∈ [0,1]. Cho giá trị
) = exp (

(

)

(

Các điều kiện sai

= 0.8

)

)=


4

13

7

9


8
3

5

11

16

0

0

4

7

3

2

GOTO Bước 3.
( ) > ( ) (điều kiện này đúng)
Sinh

Tìm ( ,

∈ [0,1]. Cho giá trị
) = exp (

(

)

(

Các điều kiện sai

= 0.01

)

)=

.

= 0.085

Nếu
≤ ( , ) →Yes
Bởi vậy, gán = ; = { , , , }

2

5

11

16

0

1

4

7

2

3

1

4

0

3

4


)

)=

.

Các điều kiện sai

= 0.0105

Nếu ≤ ( , ) →No
Bởi vậy, gán = ; = { , , , }
GOTO Bước 3.
Bước 3. Chọn = ( ) = 0.6561
= 4; = 5
Nếu ≤ thì GOTO Bước 2, Ngược lại thì dừng.
Bước 2. Vòng lặp 4
Chọn một lịch tuần tự ứng cử viên từ lân cận của
={ , , , }
={ , , , }
Tìm ∑
cho tuần tự cơng nghệ :
Cơng việc

∑

3

2


2

4

1

0

0

4

9

13
Bảng 1.7: Tính tốn của (

Do ( ) = 13. Bây giờ ta hãy kiểm tra điều kiện
Nếu ( ) < ( ) (điều kiện này đúng)
thì
Giá trị mới của
và là:
=
= { , , , }; ( ) = 13
=
= { , , , }; ( ) = 13
GOTO Bước 3.
Bước 3. Chọn = ( ) = 0.6561
= 5; = 5
Nếu ≤ thì GOTO Bước 2, Ngược lại thì dừng.

9

13

7

3

8

10

16

0

0

0

9

3

4

2

1


Thuật tốn mơ phỏng luyện kim có thuận lợi là có thể thoát khỏi cực tiểu địa
phương. Tuy nhiên bất lợi nhất của phương pháp là khả năng quay lại lời giải đã xét.
Do đó, việc lặp lại cơng việc tại một cực tiểu địa phương là hồn tồn có thể xẩy ra
và điều này dẫn đến mất nhiều thời gian tính tốn trên một phần nhỏ của khơng gian
lời giải.
1.2.4.3. Thuật tốn tìm kiếm Tabu(Taboo Search)
Thuật tốn tìm kiếm Tabu là một thủ tục tìm kiếm địa phương như mơ phỏng
luyện kim. Tuy nhiên việc lựa chọn một lịch biểu lân cận được quyết định một cách
xác định trái ngược với mơ phỏng luyện kim, ở đó xác suất gần đúng được sinh ra.
Một bản ghi của Tabu được di chuyển và được lưu trữ trong danh sách Tabu để tránh
sự trùng lặp của các thao tác trao đổi trong danh sách.


11
Danh sách Tabu (Taboo List) là thành phần chính của thuật tốn tìm kiếm Tabu.
Nó là một cấu trúc bộ nhớ lưu dấu viết của sự tiến hóa của việc tìm kiếm và chiến lược
cho việc sử dụng các thơng tin bộ nhớ một cách tốt nhất có thể. Cấu trúc bộ nhớ cơ
bản này được gọi là danh sách Tabu. Nó sẽ lưu trữ các thuộc tính, giải pháp đặc trưng
mà không cần xem xét lại trong một khoảng thời gian nhất định. Thường thì chiến
lược vào trước ra trước (FIFO-first in first out) được áp dụng cho danh sách. Các
thuộc tính cũ được xóa đi khỏi danh sách và các thuộc tính mới được chèn vào danh
sách.Thuật tốn Tabu bao gồm các bước sau:
Bước 1. Khởi tạo
Gán k = 1; bắt đầu một tuần tự công nghệ bằng một heutistic bất kỳ; gọi là
thì (

=

Để cho



=

Nếu

≤

+1
thì GOTO Bước 2 Ngược lại, dừng thuật tốn.

Ví dụ:
Giải bài tốn trong Mục 1.4.3.2 sử dụng thuật tốn tìm kiếm Tabu. Áp dụng kỹ
thuật FIVE vòng lặp, làm cho chiều dài của danh sách bằng 2 (tức là các cặp công việc
đã được thay đổi cho nhau trong quá trình di chuyển cuối cùng khơng thể được thay
đổi cho nhau thêm một lần nữa). Dữ liệu được cho trong Bảng 1.2.
Cơng việc

1
3

2
6

3
2

4
5

4

={ , , , }


12
(

) = ( ) = 30

Lân cận của lịch được định nghĩa như là tất cả các lịch có thể thu được bằng
cách trao đổi khôn ngoan cặp công việc liền kề nhau
= 30

={ , , , }

= 43
= 28
= 32

{ , , , }

{ , , , }

{ , , , }

Tuần tự cơng nghệ
tốt nhất hiện thời

Hình 1.2: Tuần tự cơng nghệ
Tính tốn ∑



4

13

9

4

13

7

9

4

7

9

13

6

9

11

16


7

0

2

5

3

1

3

2

4

3

2

1

4

3

1


43

32

Bảng 1.9: Tính tốn ∑

28

cho 3 tuần tự công nghệ

Để cho

tuần tự công nghệ tốt nhất hiện thời thì từ ba tuần tự cơng nghệ từ ,
tuần tự công nghệ tốt nhất hiện thời { , , , }. Bởi vậy
= { , , , }. Giá trị
của là: ( ) = 28. Từ đó, ( ) < ( ), =
và giá trị mới ( ) = 28.
Từ đó, tuần tự cơng nghệ tốt nhất
và 4 trong tuần tự cơng nghệ
Đặt

=

;

và đi đến vịng lặp kết tiếp.

được tạo nên bởi trao đổi các công việc 3
= {(3,4)} và

{4,3}
{ , , , }
Bảng 1.10: Sinh tất cả tuần tự công nghệ từ bằng trao đổi cặp công việc liền kề

= 28

={ , , , }

= 41

= 31
= (1,2)

Tuần tự công nghệ
tốt nhất hiện thời

= (2,4)

{ , , , }

Hình 1.3: Tuần tự cơng nghệ
Tính tốn ∑
hiện trong Bảng 1.11
()

∑

{ , , , }

{ , , , }


4

9

7

13

6

9

14

16

3

8

14

16

0

5

5


20

6

0

0

7

6

41
Bảng 1.11: Tính tốn ∑

13
cho 2 tuần tự công nghệ