Thuật toán và các bài toán lịch biểu. Luận án TS. Công nghệ thông tin
Thuật toán và các bài toán lịch biểu. Luận án TS. Công nghệ thông tin
Xem bên trong

Thuật toán và các bài toán lịch biểu. Luận án TS. Công nghệ thông tin

Luận án TS.Khoa học Máy tính — Đại học Công nghệ,. Đại học Quốc gia Hà Nội, 2013
Nghiên cứu về tổng quan của bài toán: Phân tích, đánh giá, so sánh các tiếp cận đã áp dụng cho các bài toán lập lịch job shop, trên cơ sở đó đề xuất một số hướng nghiên cứu cho bài toán này. Nghiên cứu và đề xuất một thuật toán lai mới 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 toán lập lịch job shop. Trong thuật toán đề xuất này, có một số đổi mới trong mã hóa lời giải, toán tử đột biến và toán tử trao đổi chéo. Phương pháp đề xuất này đã được thử nghiệm trên các bài toán test chuẩn và so sánh kết quả với các giải pháp trước đó để chứng tỏ tính vượt trội của nó. Song song hóa thuật toán đã đề xuất cho bài toán lập lịch job shop, thuật toán đã được cài đặt và chạy thử nghiệm cho kết quả tốt và rút ngắn được nhiều lần thời gian thực thi với cùng bộ tham số và dữ liệu vào trong thuật toán tuần tự. Chứng minh tính hội tụ của thuật toán di truyền lai mới với mã hóa tự nhiên cho bài toán lập lịch job shop đã đề xuất.
Electronic Resources

0.00

Tải về miễn phí bản đầy đủ PDF luận văn tại Link bản đầy đủ 1

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

NGUYỄN HỮU MÙI

THUẬT TOÁN VÀ CÁC BÀI
TOÁN LỊCH BIỂU

LUẬN ÁN TIẾN SĨ CÔNG NGHỆ THÔNG TIN

Hà Nội – 2013

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

NGUYỄN HỮU MÙI

THUẬT TOÁN VÀ CÁC BÀI
TOÁN LỊCH BIỂU

Chuyên ngành: Khoa học máy tính
Mã số: 62 48 01 01

LUẬN ÁN TIẾN SĨ CÔNG NGHỆ THÔNG TIN

NGƯỜI HƯỚNG DẪN KHOA HỌC:
1. PGS.TSKH Vũ Đình Hòa
2. PGS.TS Hoàng Xuân Huấn

Hà Nội – 2013

2
LỜI CẢM ƠN

Về phía cá nhân, tác giả xin bày tỏ lòng biết ơn chân thành tới PGS.
TSKH Vũ Đình Hoà, PGS. TS Hoàng Xuân Huấn đã tận tình hướng dẫn tác
giả trong quá trình hoàn thành luận án. Tác giả cũng chân thành cảm ơn TS
Phạm Thọ Hoàn, Giám đốc Trung tâm khoa học tính toán Trường Đại học Sư
phạm Hà Nội đã giúp đỡ tác giả rất nhiều trong quá trình thử nghiệm tại
Trung tâm.
Về phía tập thể, tác giả xin chân thành cảm ơn Bộ môn Khoa học máy
tính, Khoa Công nghệ thông tin, Trường Đại học Công nghệ; Bộ môn Khoa
học máy tính, Khoa Công nghệ thông tin, Trường Đại học Sư phạm Hà Nội
đã hết lòng ủng hộ và tạo điều kiện thuận lợi cho tác giả trong thời gian hoàn
thành luận án.
Cuối cùng, tác giả vô cùng biết ơn các bàn bè và người thân trong gia
đình vì sự cổ vũ to lớn của họ trong suốt thời gian hoàn thành luận án này.

Hà Nội, tháng 09 năm 2013

Nguyễn Hữu Mùi

3
LỜI CAM ĐOAN

Tôi xin cam đoan đây là công trình nghiên cứu của riêng tôi. Các kết
quả được viết chung với các tác giả khác đều được sự đồng ý của đồng tác giả
trước khi đưa vào luận án. Các kết quả nêu trong luận án là trung thực và
chưa từng được ai công bố trong các công trình nào khác.

Tác giả

Nguyễn Hữu Mùi

4
MỤC LỤC

LỜI CẢM ƠN ……………………………………………………………………………………… 2
LỜI CAM ĐOAN ………………………………………………………………………………… 3
MỤC LỤC …………………………………………………………………………………………… 4
DANH MỤC CÁC KÝ HIỆU VÀ TỪ VIẾT TẮT …………………………………… 8
DANH MỤC CÁC BẢNG…………………………………………………………………….. 9
DANH MỤC CÁC HÌNH VẼ ……………………………………………………………… 10
MỞ ĐẦU …………………………………………………………………………………………… 12
CHƯƠNG 1. TỔNG QUAN VỀ THUẬT TOÁN DI TRUYỀN VÀ BÀI
TOÁN LẬP LỊCH JOB SHOP …………………………………………………………….. 19
1.1. Thuật toán di truyền cổ điển ………………………………………………………. 19
1.1.1. Cấu trúc của thuật toán di truyền cổ điển ………………………………. 20
1.1.2. Một thủ tục đơn giản cho thuật toán di truyền cổ điển …………….. 24
1.2. Các lớp bài toán P, NP, NPC và NP-hard …………………………………….. 25
1.2.1. Các lớp bài toán P và NP …………………………………………………….. 25
1.2.2. Các lớp bài toán NPC và NP-hard ………………………………………… 25
1.3. Tổng quan về bài toán lập lịch job shop ………………………………………. 26
1.3.1. Bài toán lập lịch job shop …………………………………………………….. 26
1.3.2. Các tiếp cận chính xác ………………………………………………………… 29
1.3.3. Các tiếp cận gần đúng …………………………………………………………. 32
1.3.4. Tổng kết đánh giá chung về các tiếp cận cho JSP …………………… 50

5
1.3.5. Một số tồn tại và các đề xuất ………………………………………………… 52
CHƯƠNG 2. HAI BÀI TOÁN CON CỦA BÀI TOÁN LẬP LỊCH JOB
SHOP ………………………………………………………………………………………………… 55
2.1. Bài toán lập lịch flow shop hoán vị ……………………………………………… 55
2.1.1. Mô tả bài toán …………………………………………………………………….. 55
2.1.2. Cách tính thời gian hoàn thành trong một lịch biểu hoán vị ……… 57
2.1.3. Thuật toán Johnson cho PFSP 2 máy và PFSP 3 máy ……………… 60
2.1.4. Một thuật toán di truyền mã hóa tự nhiên cho bài toán lập lịch flow
shop hoán vị tổng quát …………………………………………………………………. 67
2.1.5. Các kết quả thử nghiệm ……………………………………………………….. 73
2.2. Bài toán lập lịch flow shop…………………………………………………………. 74
2.2.1. Mô tả bài toán …………………………………………………………………….. 74
2.2.2. Một thuật toán di truyền mã hóa tự nhiên cho bài toán lập lịch flow
shop tổng quát …………………………………………………………………………….. 75
2.2.3. Các kết quả thử nghiệm ……………………………………………………….. 80
2.3. Kết luận …………………………………………………………………………………… 81
CHƯƠNG 3. MỘT THUẬT TOÁN DI TRUYỀN LAI MỚI CHO BÀI
TOÁN LẬP LỊCH JOB SHOP …………………………………………………………….. 82
3.1. Các lịch biểu tích cực và bán tích cực………………………………………….. 82
3.2. Thuật toán GT ………………………………………………………………………….. 85
3.3. Một thuật toán di truyền lai mới cho bài toán lập lịch job shop ………. 88
3.3.1. Mã hoá lời giải …………………………………………………………………… 89
3.3.2. Khởi tạo tập lời giải cho thế hệ ban đầu ………………………………… 90

6
3.3.3. Xây dựng hàm thích nghi …………………………………………………….. 90
3.3.4. Các toán tử di truyền …………………………………………………………… 91
3.3.5. Thuật toán tiến hóa ……………………………………………………………… 95
3.3.6. Tính đúng đắn của thuật toán được đề nghị ……………………………. 96
3.4. Song song hóa thuật toán di truyền lai mới cho bài toán lập lịch job
shop ………………………………………………………………………………………………. 97
3.4.1. Mô tả thuật toán …………………………………………………………………. 97
3.4.2. Thủ tục di truyền song song cho JSP …………………………………….. 99
3.4.3. Cài đặt thuật toán ……………………………………………………………… 100
3.5. Kết quả thử nghiệm …………………………………………………………………. 101
3.5.1. Kết quả thử nghiệm thuật toán tuần tự …………………………………. 101
3.5.2. Kết quả thử nghiệm thuật toán song song …………………………….. 104
3.6. Kết luận …………………………………………………………………………………. 107
CHƯƠNG 4. PHÂN TÍCH TÍNH HỘI TỤ CỦA THUẬT TOÁN DI
TRUYỀN LAI MỚI CHO BÀI TOÁN LẬP LỊCH JOB SHOP ……………… 109
4.1. Lý thuyết Xích Markov ……………………………………………………………. 109
4.1.1. Khái niệm xích Markov …………………………………………………….. 110
4.1.2. Các tính chất của Xích Markov………………………………………….. 112
4.2. Xích Markov Ergodic ……………………………………………………………… 113
4.3. Phân tích tính hội tụ của thuật toán di truyền lai tuần tự cho bài toán
lập lịch job shop ……………………………………………………………………………. 114
4.3.1. Phân tích tính hội tụ của thuật toán di truyền truyền thống …….. 114

7
4.3.2. Phân tích tính hội tụ của thuật toán di truyền với cá thể tinh hoa và
toán tử sao chép …………………………………………………………………………. 122
4.4. Kết luận …………………………………………………………………………………. 126
KẾT LUẬN ……………………………………………………………………………………… 127
HƯỚNG NGHIÊN CỨU TIẾP THEO ………………………………………………… 128
DANH MỤC CÔNG TRÌNH KHOA HỌC CỦA TÁC GIẢ LIÊN QUAN
ĐẾN LUẬN ÁN ……………………………………………………………………………….. 129
TÀI LIỆU THAM KHẢO ………………………………………………………………….. 131
PHỤ LỤC ………………………………………………………………………………………… 141

8
DANH MỤC CÁC KÝ HIỆU VÀ TỪ VIẾT TẮT

1 ACO Ant Colony Optimization
2 AI Artificial Intelligence
3 AS Ant System
4 BB Branch and Bound
5 CPU Central Processing Unit
6 FSP Flow shop Scheduling Problem
7 GA Genetic Algorithms
8 GLS Genetic Local Search
9 GT Giffler and Thompson
10 HTT Hyper Threading Technology
11 IM Iterative Improvement
12 JSP Job shop Scheduling Problem
13 MIP Mixed Integer linear Programming
14 MPP Massively Parallel Processor
15 PFSP Permutation Flow shop Scheduling Problem
16 RISC Reduced Instructions Set Computer
17 SA Simulated Annealing
18 SB Shifting Bottleneck
19 TA Threshold Acceptance
20 TS Tabu Search

9
DANH MỤC CÁC BẢNG
Bảng 1.1 – JSP 3 công việc, 3 máy ………………………………………………………… 28
Bảng 2.1 – PFSP 5 công việc 4 máy ………………………………………………………. 56
Bảng 2.2 – PFSP 4 công việc 2 máy ………………………………………………………. 62
Bảng 2.3 – Các công việc chưa được lập lịch …………………………………………. 63
Bảng 2.4 – Các công việc chưa được lập lịch …………………………………………. 63
Bảng 2.5 – Các công việc chưa được lập lịch …………………………………………. 64
Bảng 2.6 – PFSP 5 công việc 3 máy ………………………………………………………. 66
Bảng 2.7 – Thời gian xử lý các công việc trên 2 máy G và H …………………… 66
Bảng 2.8 – Mã hóa lời giải theo số tự nhiên ……………………………………………. 67
Bảng 2.9 – Kết quả chạy thử nghiệm …………………………………………………….. 73
Bảng 2.10 – FSP 4 máy 2 công việc ………………………………………………………. 75
Bảng 2.11 – Mã hóa lời giải theo số tự nhiên ………………………………………….. 76
Bảng 2.12 – Kết quả chạy thử nghiệm …………………………………………………… 80
Bảng 3.1 – JSP 3 công việc, 3 máy ………………………………………………………… 83
Bảng 3.2 – Mã hoá các thao tác bằng số tự nhiên của JSP 3  3 ……………….. 89
Bảng 3.3 – Nhiệm vụ của Master và Slave ……………………………………………… 98
Bảng 3.4 – Kết quả chạy thử nghiệm trên các bài toán test của Lawrence … 101
Bảng 3.5 – So sánh kết quả chạy thử nghiệm ………………………………………… 104
Bảng 3.6 – Kết quả chạy thử nghiệm NHGA và PHGA trên các bài toán test
do Muth & Thompson đề nghị ……………………………………………………………. 105
Bảng 3.7 – So sánh thời gian chạy thử nghiệm NHGA và PHGA ……………. 105

10
DANH MỤC CÁC HÌNH VẼ
Hình 1.1 – Một lời giải được mã hóa nhị phân ………………………………………… 20
Hình 1.2 – Hai cá thể cha cho phép trao đổi chéo ……………………………………. 21
Hình 1.3 – Hai cá thể con sau phép trao đổi chéo ……………………………………. 21
Hình 1.4 – Hai cá thể con sau phép trao đổi chéo 2 điểm …………………………. 22
Hình 1.5 – Cá thể con sau phép trao đổi chéo đồng nhất ………………………….. 22
Hình 1.6 – Cá thể cha và cá thể con sau phép đột biến …………………………….. 23
Hình 1.7 – Các tiếp cận chủ yếu giải quyết JSP ………………………………………. 51
Hình 2.1 – Biểu đồ Grant biểu diễn một lời giải của PFSP 5 công việc 4 máy
…………………………………………………………………………………………………………. 57
Hình 2.2 – Đồ thị không liên thông biểu diễn một lời giải của PFSP …………. 58
Hình 2.3 – Cách tính thời gian hoàn thành trong đồ thị không liên thông …… 58
Hình 2.4 – Các cạnh tới hạn của đồ thị không liên thông …………………………. 59
Hình 2.5 – Đồ thị cạnh tới hạn ………………………………………………………………. 59
Hình 2.6 – Đồ thị đường tới hạn ……………………………………………………………. 60
Hình 2.7 – Makespan của PFSP 2 máy …………………………………………………… 61
Hình 2.8 – Biểu đồ Grant của lịch biểu tối ưu bài toán 2 máy …………………… 64
Hình 2.9 – Biểu đồ Grant của lịch biểu tối ưu bài toán 3 máy …………………… 66
Hình 2.10 – Một lời giải hợp lệ cho PFSP 4 công việc 5 máy …………………… 68
Hình 2.11 – Cá thể cha …………………………………………………………………………. 70
Hình 2.12 – Cá thể con sau phép đột biến ………………………………………………. 71
Hình 2.13 – Các cá thể cha tham gia trao đổi chéo ………………………………….. 72

11
Hình 2.14 – Cá thể con sau phép trao đổi chéo ……………………………………….. 72
Hình 2.15 – Một lời giải hợp lệ cho FSP 3 máy  5 công việc ………………….. 76
Hình 2.16 – Cá thể cha cho phép đột biến ………………………………………………. 78
Hình 2.17 – Cá thể con sau phép đột biến ………………………………………………. 79
Hình 2.18 – Các cá thể cha tham gia trao đổi chéo ………………………………….. 79
Hình 2.19 – Cá thể con sau phép trao đổi chéo ……………………………………….. 80
Hình 3.1 – Các lớp lịch biểu …………………………………………………………………. 83
Hình 3.2 – Lịch biểu không tích cực ……………………………………………………… 84
Hình 3.3 – Một lịch biểu bán tích cực ……………………………………………………. 84
Hình 3.4 – Một lịch biểu tích cực ………………………………………………………….. 85
Hình 3.5 – Một lời giải hợp lệ cho JSP 3  3 ………………………………………….. 90
Hình 3.6 – Cá thể cha cho phép đột biến ………………………………………………… 92
Hình 3.7 – Cá thể con thu được sau phép đột biến …………………………………… 92
Hình 3.8 – Trao đổi chéo dùng GT và thực hiện trên 3 cá thể cha ……………… 94
Hình 3.9 – Các cha tham gia đổi chéo và cá thể con sau đổi chéo ……………… 94
Hình 3.10 – Thời gian chạy máy của NHGA và PHGA đối với bài toán mt06
……………………………………………………………………………………………………….. 106
Hình 3.11 – Thời gian chạy máy của NHGA và PHGA đối với bài toán mt10
……………………………………………………………………………………………………….. 107
Hình 3.12 – Thời gian chạy máy của NHGA và PHGA đối với bài toán mt20
……………………………………………………………………………………………………….. 107
Hình 4.1 – Gen ở vị trí thứ 2 trạng thái i của quần thể ……………………………. 117

12
MỞ ĐẦU

 Lý do chọn đề tài
Lập lịch là một trong những chủ đề quan trọng thuộc lĩnh vực vận trù
học 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 tài nguyên dùng chung một cách hiệu quả nhất cho các tác vụ đồng thời
trong toàn bộ thời gian xử lý. Các bài toán lập lịch rất đa dạng, chúng xuất
hiện trong các lĩnh vực khác nhau như: Sản xuất, chăm sóc sức khỏe, giáo dục
đào tạo, xử lý tính toán, vận tải,… Trong lĩnh vực sản xuất, các tác vụ thường
được xem như là các công việc, các tài nguyên là các máy. Trong bệnh viện,
các tác vụ là các bệnh nhân và các tài nguyên là các y tá, các giường bệnh,
các trang thiết bị y tế được yêu cầu để điều trị các bệnh nhân. Trong giáo dục
đào tạo, các tác vụ là các lớp học và các tài nguyên là các giáo viên, các
phòng học, các sinh viên,… Các ví dụ khác về lập lịch bao gồm các bài toán
vận chuyển (chẳng hạn như bài toán người du lịch, lập lịch hàng không, lập
lịch tầu hỏa,…), các bài toán lập lịch tính toán (chẳng hạn như lập lịch CPU,
lập lịch phân công,…).
Trong những năm qua, rất nhiều các công trình nghiên cứu về lập lịch
với các giải pháp khác nhau đã được đề xuất, từ các tiếp cận chính xác đến
các tiếp cận gần đúng và gần đây là các tiếp cận lai kết hợp đồng thời nhiều
kỹ thuật với nhau. Các nhà nghiên cứu về lập lịch cũng rất đa dạng, họ hoạt
động trong nhiều lĩnh vực rất khác nhau như: Các nhà nghiên cứu khoa học,
các nhà khoa học quản lý và thậm chí cả các công nhân trực tiếp sản xuất.
Trong những năm qua, nhiều nhà nghiên cứu thuộc các lĩnh vực tưởng chừng
như không liên quan gì tới lập lịch như: Sinh học, di truyền học, thần kinh
học,… cũng đã có rất nhiều đóng góp cho lý thuyết lập lịch, đặc biệt là sự

13
đóng góp của họ vào các phương pháp luận mới đầy triển vọng như mạng nơ
và tính toán tiến hóa. Chẳng hạn như thuật toán di truyền phỏng theo học
thuyết tiến hóa của Darwin được áp dụng khá rộng rãi cho các bài toán lập
lịch.
Trong lĩnh vực lập lịch, một mô hình tổng quát nhất về lập lịch đó là
bài toán lập lịch job shop (Job shop Scheduling Problem – JSP), bài toán này
thuộc lớp NP-hard (NP là lớp các bài toán giải được bởi một thuật toán
không đơn định trong thời gian đa thức) và nổi tiếng là một trong những bài
toán tối ưu tổ hợp khó tính toán nhất cho tới nay. JSP cũng là một trong
những bài toá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. Ngoài ra, một động lực khác thúc đẩy mạnh mẽ việc
nghiên cứu JSP đó là tính ứng dụng của nó trong thực tiễn cuộc sống và sản
xuất.
Ban đầu JSP được giải quyết bởi các tiếp cận tìm ra lời giải chính xác
như: Các tiếp cận hiệu suất cao, các mô hình toán học, các kỹ thuật nhánh
cận. Các tiếp cận này đưa ra các lời giải tối ưu thực sự cho bài toán. Về mặt lý
thuyết, các tiếp cận chính xác đóng vai trò quan trọng và đã được áp dụng
thành công cho một số bài toán lập lịch có kích cỡ nhỏ. Tuy nhiên, các tiếp
cận này đòi hỏi khá nhiều thời gian thực thi ngay cả với các bài toán cỡ trung
bình. Thậm chí, để tìm ra một lời giải thỏa mãn hoàn toàn các ràng buộc của
bài toán có thể yêu cầu thời gian tính toán tăng theo hàm mũ trong khi cỡ bài
toán chỉ tăng theo tuyến tính.
Trong thực tế, chúng ta thường phải giải quyết các bài toán lập lịch có
kích cỡ lớn trong một khoảng thời gian khả thi với các kết quả chấp nhận
được (các kết quả này không nhất thiết là phải tối ưu thực sự). Các giải pháp
cho JSP đáp ứng đòi hỏi này còn được gọi là các tiếp cận gần đúng. Các tiếp

14
cận này thường dựa trên các tiến trình tự nhiên như: Vật lý thống kê, sự tiến
hóa sinh học hay dựa trên khung cảnh trí tuệ nhân tạo. Bốn tiếp cận gần đúng
đã được nghiên cứu và áp dụng phổ biến nhất cho tới nay đó là: Các luật ưu
tiên nhanh, các giải thuật heuristic dựa trên nút cổ chai, trí tuệ nhân tạo, các
phương pháp tìm kiếm cục bộ và meta-heuristic. Đánh giá tổng quan về các
tiếp cận cho JSP sẽ được trình bày chi tiết trong chương 1 của luận án này.
Tuy nhiên, cho tới nay chưa có một tiếp cận nào đã được đề xuất có thể
giải quyết triệt để bài toán lập lịch job shop tổng quát, nhất là đối với JSP có
nhiều máy và nhiều công việc. Một số vấn đề chính liên quan tới việc giải
quyết bài toán này còn tồn tại như sau:
1. Các chuẩn thiết kế thử nghiệm để đánh giá thuật toán mới được đề
nghị.
2. Tính hội tụ của các thuật toán mới được đề xuất chưa được chứng minh
dựa trên cơ sở toán học.
3. Phương pháp luận cho việc kết hợp các kỹ thuật tìm kiếm khác nhau để
tạo ra một giải pháp mạnh cho JSP còn chưa được nghiên cứu một cách
đầy đủ.

Ở nước ta, việc nghiên cứu về bài toán lập lịch job shop vẫn chưa phát
triển. Trong các trường đại học, đại đa số các sinh viên, học viên cao học về
công nghệ thông tin vẫn chưa biết tới bài toán này. Trong những năm gần đây
đã xuất hiện một số báo cáo khoa học đề cập tới bài toán này. Tuy nhiên, kết
quả đạt được còn rất khiêm tốn, chưa tương xứng với tầm quan trọng của bài
toán.

Tác giả

Nguyễn Hữu Mùi

Nhà xuất bản

Đại học Công nghệ,

Năm xuất bản

2013

Người hướng dẫn

Vũ Đình Hòa, Hoàng Xuân Huấn

Định danh

00050002598

Kiểu

text

Định dạng

text/pdf

Nhà xuất bản

Khoa công nghệ thông tin,

Trường đại học Công nghệ

Các đánh giá

Hiện chưa có đánh giá cho sản phẩm.

Hãy là người đầu tiên đánh giá “Thuật toán và các bài toán lịch biểu. Luận án TS. Công nghệ thông tin”

Email của bạn sẽ không được hiển thị công khai. Các trường bắt buộc được đánh dấu *