Luận án Tiến sĩ Toán học: Một số phương pháp gần đúng giải bài toán lập lịch với tài nguyên giới hạn

fơơn vị BỘ GIÁO DỤC VÀ ĐÀO TẠO

BỘ QUỐC PHÒNG

VIỆN KHOA HỌC VÀ CÔNG NGHỆ QUÂN SỰ

ĐẶNG QUỐC HỮU

MỘT SỐ PHƯƠNG PHÁP GẦN ĐÚNG

GIẢI BÀI TOÁN LẬP LỊCH VỚI TÀI NGUYÊN GIỚI HẠN

LUẬN ÁN TIẾN SĨ TOÁN HỌC

Hà Nội - 2021

BỘ GIÁO DỤC VÀ ĐÀO TẠO BỘ QUỐC PHÒNG

VIỆN KHOA HỌC VÀ CÔNG NGHỆ QUÂN SỰ

ĐẶNG QUỐC HỮU

MỘT SỐ PHƯƠNG PHÁP GẦN ĐÚNG

GIẢI BÀI TOÁN LẬP LỊCH VỚI TÀI NGUYÊN GIỚI HẠN

Chuyên ngành: Cơ sở toán học cho tin học

Mã số: 9 46 01 10

LUẬN ÁN TIẾN SĨ TOÁN HỌC

NGƯỜI HƯỚNG DẪN KHOA HỌC:

1. TS. Nguyễn Thế Lộc 2. TS. Nguyễn Doãn Cường

Hà Nội - 2021

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 số liệu,

kết quả nghiên cứu được trình bày trong luận án là hoàn toàn trung thực và chưa

từng được ai công bố trong bất kỳ công trình nào khác, các dữ liệu tham khảo

được trích dẫn đầy đủ.

Hà Nội, ngày tháng 08 năm 2021

Nghiên cứu sinh

Đặng Quốc Hữu

LỜI CẢM ƠN

Luận án này được hoàn thành tại Viện Công nghệ thông tin - Viện Khoa

học và Công nghệ quân sự và Trường Đại học Thương mại.

Lời đầu tiên, nghiên cứu sinh bày tỏ lòng biết ơn sâu sắc tới tập thể giáo

viên hướng dẫn: TS. Nguyễn Thế Lộc và TS. Nguyễn Doãn Cường đã trực tiếp

giảng dạy và tận tình hướng dẫn, định hướng cho nghiên cứu sinh trong suốt

quá trình thực hiện luận án này.

Nghiên cứu sinh trân trọng gửi lời cảm ơn tới Thủ trưởng Viện Khoa học

và Công nghệ quân sự, Phòng Đào tạo - Viện Khoa học và Công nghệ quân sự,

Viện Công nghệ thông tin đã giúp đỡ tôi trong suốt thời gian học tập, nghiên

cứu, thực hiện luận án. Cảm ơn các thầy cô tại Viện Khoa học và Công nghệ

quân sự, Đại học Quốc gia Hà Nội, Đại học Sư phạm Hà Nội,... đã nhiệt tình

hướng dẫn, giúp đỡ tôi hoàn thành các nội dung của chương trình tiến sĩ và

đóng góp cho tôi những ý kiến quý báu về mặt nội dung khoa học và bố cục

của luận án.

Tôi xin trân trọng cảm ơn các thầy cô, các nhà khoa học, đồng nghiệp

trong và ngoài Viện đã đọc, nhận xét luận án, đóng góp những ý kiến quý báu

để nghiên cứu sinh hoàn thiện luận án này.

Trân trọng cảm ơn Ban Giám hiệu trường Đại học Thương mại, các đồng

nghiệp và gia đình đã động viên, chia sẻ và tạo điều kiện cho tôi trong suốt thời

gian làm nghiên cứu sinh.

Nghiên cứu sinh

Đặng Quốc Hữu

iii

DANH MỤC CÁC KÝ HIỆU, CHỮ VIẾT TẮT ....................................................... v

DANH MỤC CÁC BẢNG ....................................................................................... vii

DANH MỤC CÁC HÌNH VẼ....................................................................................ix

MỞ ĐẦU ..................................................................................................................... 1

CHƯƠNG 1: TỔNG QUAN VỀ BÀI TOÁN MS-RCPSP ........................................ 8

1.1. Bài toán MS-RCPSP ......................................................................................... 9 1.1.1. Mô tả bài toán ................................................................................................... 9 1.1.2. Một số ứng dụng thực tế của bài toán MS-RCPSP ......................................... 15 1.1.3. Những nghiên cứu liên quan ........................................................................... 19 1.2. Một số thuật toán metaheuristic tìm nghiệm gần đúng ................................... 24 1.2.1. Thuật toán PSO ............................................................................................... 25 1.2.2. Thuật toán PSO kết hợp với tìm kiếm lân cận ................................................ 27 1.2.3. Thuật toán DE ................................................................................................. 31 1.2.4. Thuật toán Cuckoo Search .............................................................................. 33

Kết luận chương 1 ..................................................................................................... 42

CHƯƠNG 2: GIẢI BÀI TOÁN MS-RCPSP BẰNG PHƯƠNG PHÁP TỐI ƯU BẦY ĐÀN VÀ PHƯƠNG PHÁP TIẾN HÓA VI PHÂN ........................................ 43

2.1. Phương pháp biểu diễn cá thể ......................................................................... 44 2.2. Thang đo độ chênh của cá thể ......................................................................... 45 2.3. Đề xuất thuật toán M-PSO .............................................................................. 50 2.3.1. Kỹ thuật Di cư ................................................................................................. 51 2.3.2. Thuật toán M-PSO .......................................................................................... 54 2.3.3. Thực nghiệm ................................................................................................... 56 2.3.4. Đánh giá chất lượng lời giải của thuật toán .................................................... 61 2.3.5. Hình ảnh so sánh M-PSO và GA-M ............................................................... 63 2.4. Đề xuất thuật toán DEM ................................................................................. 64 2.4.1. Phương pháp tái thiết lập tài nguyên thực hiện .............................................. 64 2.4.2. Thuật toán ....................................................................................................... 70 2.4.3. Kết quả thực nghiệm ....................................................................................... 70 2.4.4. Đánh giá chất lượng lời giải của thuật toán .................................................... 74 2.4.5. Hình ảnh so sánh DEM với thuật toán GA-M ................................................ 77

Kết luận chương 2 ..................................................................................................... 79

CHƯƠNG 3: BÀI TOÁN REAL-RCPSP ................................................................ 80

3.1. Bài toán Real-RCPSP ..................................................................................... 80

MỤC LỤC

3.1.1. Phát biểu bài toán ............................................................................................ 81 3.1.2. Những ứng dụng thực tế của bài toán Real-RCPSP ....................................... 82 3.2. Xếp loại bài toán Real-RCPSP thông qua phân loại Graham ......................... 83

Kết luận chương 3 ..................................................................................................... 88

CHƯƠNG 4: GIẢI BÀI TOÁN REAL-RCPSP BẰNG PHƯƠNG PHÁP TIẾN HÓA VI PHÂN VÀ PHƯƠNG PHÁP CUCKOO SEARCH .................................. 89

4.1. Phương pháp biểu diễn cá thể ......................................................................... 90 4.2. Đề xuất thuật toán A-DEM ............................................................................. 92 4.2.1. Phương pháp thích nghi .................................................................................. 93 4.2.2. Thuật toán A-DEM ......................................................................................... 97 4.2.3. Thực nghiệm ................................................................................................... 99 4.2.4. Đánh giá chất lượng lời giải của thuật toán .................................................. 104 4.2.5. Hình ảnh so sánh A-DEM và GA-M ............................................................ 105 4.3. Đề xuất thuật toán R-CSM ............................................................................ 106 4.3.1. Thuật toán ..................................................................................................... 107 4.3.2. Kết quả thực nghiệm ..................................................................................... 109 4.3.3. Đánh giá chất lượng lời giải của thuật toán .................................................. 110 4.3.4. Hình ảnh so sánh R-CSM với thuật toán GA-M ........................................... 111 4.4. Đề xuất thuật toán RR-CSM ......................................................................... 112 4.4.1. Phương pháp Rotate ...................................................................................... 113 4.4.2. Thuật toán ..................................................................................................... 117 4.4.3. Kết quả thực nghiệm ..................................................................................... 119 4.4.4. Đánh giá chất lượng lời giải của thuật toán .................................................. 120 4.4.5. Hình ảnh so sánh RR-CSM với thuật toán GA-M ........................................ 122

Kết luận chương 4 ................................................................................................... 124

KẾT LUẬN ............................................................................................................. 125

DANH MỤC CÁC CÔNG TRÌNH KHOA HỌC ĐÃ CÔNG BỐ ........................ 127

TÀI LIỆU THAM KHẢO ....................................................................................... 129

DANH MỤC CÁC KÝ HIỆU, CHỮ VIẾT TẮT

Tập tác vụ (task) cần thực hiện trước tác vụ i Ci

Tập các tài nguyên; L

Li Tập tài nguyên có thể thực hiện tác vụ i, Li L

Tài nguyên thứ i Li

Một lịch biểu khả thi của bài toán; P

Tập tất cả các lịch biểu Pall

Tập tất các các kỹ năng của các tài nguyên; S

Si Tập các kỹ năng của tài nguyên i, Si S

Tập các tác vụ của dự án W

Wi Tập các tác vụ có thể thực hiện bởi tài nguyên i, Wi W

Tác vụ thứ i Wi

Algorithm Thuật toán, mô tả bằng mã giả của một thuật toán

A-DEM Thuật toán mới A-DEM (Adaptive DEM)

Giá trị trung bình (Average) AVG

Giá trị tốt nhất (BEST) BEST

Xác suất lai ghép (Crossover Probability ) CR

Thuật toán Cuckoo Search (Cuckoo Search) CS

Thuật toán CS áp dụng giải bài toán MS-RCPSP (CS for CSM

MS-RCPSP)

Thuật toán tiến hóa vi phân (Differential Evolution) DE

Thuật toán đề xuất DEM áp dụng giải bài toán MS-RCPSP DEM

(DE for MS-RCPSP)

Fitness Giá trị tốt nhất của một cá thể trong quần thể từ thế hệ đầu

tiên cho đến thế hệ hiện tại.

GA Thuật toán di truyền (Genetic Algorithms)

GRASP Thuật toán lai giữa Greedy và Adative(Greedy Randomized

Adaptive Search Procedure)

GreedyDO Thuật toán tham lam nhằm tối ưu thời gian thực hiện

(Greedy algorithm for Duration Optimization)

GS Kỹ thuật tìm kiếm toàn cục (Global Search)

HAntCO Thuật toán tối ưu đàn kiến lai (Hybrid Ant Colony

Optimization)

iMOPSE Bộ dữ liệu chuẩn iMOPSE (iMOPSE dataset)

LS Kỹ thuật tìm kiếm cục bộ (Local Search)

Makespan Thời gian tối thiểu để hoàn thành dự án

M-PSO Thuật toán đề xuất M-PSO (Migration PSO)

MS-RCPSP Bài toán lập lịch với tài nguyên giới hạn và đa kỹ năng

(Multi skill - RCPSP)

PSO Thuật toán tối ưu bầy đàn (Particle Swarm Optimization)

RCPSP Bài toán lập lịch thực hiện dự án với tài nguyên giới hạn -

sau này viết gọn là: bài toán lập lịch với tài nguyên giới hạn

(Resource-Constrained Project Scheduling Problem)

Real-RCPSP Bài toán mới Real-RCPSP (Real-RCPSP Problem)

R-CSM Thuật toán đề xuất R-CSM (Reallocate CSM)

RR-CSM Thuật toán đề xuất RR-CSM (Rotate and Reallocate CSM)

STD Độ lệch chuẩn (Standard Deviation)

TNG Công ty cổ phần đầu tư và thương mại TNG

vii

Trang

DANH MỤC CÁC BẢNG

Bảng 1.1: Thông tin đầu vào của dự án .......................................................... 11

Bảng 1.2: Dữ liệu về tác vụ và yêu cầu thực hiện .......................................... 18

Bảng 1.3: Tổng hợp các nghiên cứu về bài toán MS-RCPSP ........................ 24

Bảng 2.1: Thời gian thực hiện các tác vụ ........................................................ 44

Bảng 2.2: Thang đo tài nguyên thực hiện tác vụ ............................................ 46

Bảng 2.3: Tài nguyên có thể thực hiện tác vụ ................................................. 48

Bảng 2.4: Giá trị vector thang đo .................................................................... 48

Bảng 2.5: Tài nguyên thực hiện tác vụ của cá thể S1, S2 ................................. 48

Bảng 2.6: Giá trị của vector độ chênh d .......................................................... 48

Bảng 2.7: Kết quả cộng hai cá thể .................................................................. 50

Bảng 2.8: Năng lực của các tài nguyên ........................................................... 53

Bảng 2.9: Lịch biểu khả thi của dự án trong ví dụ 2.2 .................................... 53

Bảng 2.10: Lịch biểu mới sau khi di cư .......................................................... 53

Bảng 2.11: Bộ dữ liệu iMOPSE cho bài toán MS-RCPSP ............................. 56

Bảng 2.12: Kết quả thực nghiệm M-PSO ....................................................... 59

Bảng 2.13: So sánh kết quả thực nghiệm M-PSO với các thuật toán khác .... 61

Bảng 2.14: Thời gian thực hiện các tác vụ ...................................................... 68

Bảng 2.15: Năng lực các tài nguyên ............................................................... 68

Bảng 2.16: Tài nguyên thực hiện tác vụ ......................................................... 69

Bảng 2.17: Kết quả thực nghiệm DEM với bộ dữ liệu iMOPSE.................... 71

Bảng 2.18: So sánh kết quả thực nghiệm DEM với các thuật toán ................ 73

Bảng 2.19: So sánh kết quả thực nghiệm DEM với M-PSO .......................... 73

Bảng 4.1: Thời gian chuẩn thực hiện các tác vụ ............................................. 90

Bảng 4.2: Năng lực tài nguyên của dự án ....................................................... 90

Bảng 4.3: Yêu cầu tài nguyên thực hiện tác vụ và thời gian thực hiện .......... 91

Bảng 4.4: Thời gian thực hiện các tác vụ ........................................................ 92

Bảng 4.5: Các hợp đồng may công nghiệp ................................................... 102

Bảng 4.6: Dữ liệu chuyền may của TNG ...................................................... 102

viii

Bảng 4.7: Kết quả thực nghiệm A-DEM trên bộ dữ liệu iMOPSE .............. 102

Bảng 4.8: Kết quả thực nghiệm A-DEM với bộ dữ liệu TNG ...................... 103

Bảng 4.9: Kết quả thực nghiệm R-CSM với bộ dữ liệu iMOPSE ................ 109

Bảng 4.10: Kết quả thực nghiệm R-CSM với bộ dữ liệu TNG .................... 110

Bảng 4.11: Thời gian thực hiện các tác vụ .................................................... 113

Bảng 4.12: Kết quả thực nghiệm RR-CSM với bộ dữ liệu iMOPSE ........... 119

Bảng 4.13: Kết quả thực nghiệm RR-CSM với bộ dữ liệu TNG.................. 120

Trang

DANH MỤC CÁC HÌNH VẼ

Hình 1.1. Đồ thị ưu tiên thực hiện các tác vụ. ................................................ 11

Hình 1.2. Biểu đồ Gantt về thực hiện các tác vụ theo thời gian ..................... 12

Hình 1.3. Ma trận quan hệ giữa tác vụ và kỹ năng của tài nguyên ................. 15

Hình 1.4. Biểu đồ Gantt mô tả một phương án lịch biểu. ............................... 18

Hình 1.5. Sơ đồ bay của 2 chiếc UAV ............................................................ 19

Hình 1.6. Sơ đồ di chuyển của một cá thể i trong PSO .................................. 26

Hình 1.7. Kiểu lân cận Ring (a) và Von Neumann (b) ................................... 28

Hình 1.8. Hàm RotateRight (a) và hàm Exchange (b) .................................... 30

Hình 1.9. Chuyển động Brown của 5 hạt phấn hoa ........................................ 35

Hình 1.10. Chuyển động Brown của 3 hạt keo ............................................... 35

Hình 1.11. Đồ thị hàm mật độ xác suất của phân phối Lévy .......................... 37

Hình 1.12. 1000 bước dịch chuyển Lévy flight và chuyển động Brown ........ 38

Hình 2.1. Đồ thị ưu tiên các tác vụ trong dự án .............................................. 44

Hình 2.2. Tài nguyên thực hiện tác vụ theo thời gian ..................................... 45

Hình 2.3. Biểu diễn giá trị trên thang đo ......................................................... 47

Hình 2.4. Thay đổi tài nguyên thực hiện tác vụ .............................................. 52

Hình 2.5. So sánh giá trị BEST giữa M-PSO và GA-M ................................ 63

Hình 2.6. So sánh giá trị STD giữa M-PSO và GA-M .................................. 63

Hình 2.7. Sơ đồ khối thực hiện di chuyển tác vụ sang tài nguyên khác ......... 67

Hình 2.8. Thứ tự ưu tiên của các tác vụ .......................................................... 68

Hình 2.9. Biểu đồ Gantt của lịch biểu 2.15 ..................................................... 69

Hình 2.10. Biểu đồ Gantt của lịch biểu mới ................................................... 69

Hình 2.11. Minh họa phương pháp tái thiết lập tài nguyên ............................ 69

Hình 2.12. So sánh giá trị BEST giữa DEM với GA-M ................................ 77

Hình 2.13. So sánh giá trị STD giữa DEM với GA-M ................................... 77

Hình 2.14. So sánh giá trị AVG giữa DEM với GA-M .................................. 78

Hình 3.1. Các kiểu thứ tự thực hiện tác vụ ..................................................... 86

Hình 4.1. Biểu đồ Gantt của lịch biểu trong ví dụ 4.1 .................................... 92

Hình 4.2. Kiến trúc hình sao ........................................................................... 93

Hình 4.3. Tìm các cá thể lân cận ..................................................................... 94

Hình 4.4. So sánh giá trị BEST giữa A-DEM với GA-M trên iMOPSE ...... 105

Hình 4.5. So sánh giá trị STD giữa A-DEM với GA-M trên iMOPSE ........ 105

Hình 4.6. So sánh giá trị BEST giữa A-DEM và GA-M và TNG ................ 106

Hình 4.7. So sánh giá trị STD giữa A-DEM với GA-M trên bộ dữ liệu

TNG ................................................................................................ 106

Hình 4.8. So sánh giá trị BEST giữa R-CSM với GA-M trên iMOPSE ...... 111

Hình 4.9. So sánh giá trị STD giữa R-CSM với GA-M trên iMOPSE ......... 111

Hình 4.10. So sánh giá trị BEST giữa R-CSM, GA-M và TNG trên .......... 112

Hình 4.11. So sánh giá trị STD giữa R-CSM với GA-M.............................. 112

Hình 4.12. Đồ thị ưu tiên của dự án 1 ........................................................... 113

Hình 4.13. Đồ thị ưu tiên của dự án 2 ........................................................... 113

Hình 4.14. Các tài nguyên sử dụng liên tục (a) và có thời gian trống (b) .... 114

Hình 4.15. Biểu đồ Gantt khi áp dụng phương pháp Rotate ......................... 116

Hình 4.16. So sánh giá trị BEST giữa R-CSM, RR-CSM, GA-M ............... 122

Hình 4.17. So sánh giá trị STD giữa R-CSM, RR-CSM, GA-M trên

iMOPSE .......................................................................................... 122

Hình 4.18. So sánh giá trị BEST giữa R-CSM, RR-CSM và TNG ............. 123

Hình 4.19. So sánh giá trị STD giữa RR-CSM với R-CSM ......................... 123

MỞ ĐẦU

1. Tính cấp thiết của đề tài luận án

Cách mạng công nghiệp 4.0 đang diễn ra mạnh mẽ trên toàn thế giới với

nền tảng là các hệ thống điều khiển và tự động hóa thông minh cho phép các

thiết bị giao tiếp với nhau và với con người. Internet vạn vật (IoT) mang lại khả

năng kết nối nhiều thiết bị tạo thành hệ thống thông minh đồng thời làm bùng

nổ lượng dữ liệu trên các mạng truyền thông, trong khi đó các tài nguyên phục

vụ kết nối, truyền thông lại là hữu hạn. Do vậy, cần có các phương án lập lịch

phân phối, cấp phát tài nguyên cũng như quản lý các dự án công việc sao cho

hiệu quả.

Trong thực tế, việc lập lịch trong các dự án hoặc các dây chuyền sản xuất

luôn bị ràng buộc bởi những điều kiện như thời gian hoàn thành dự án, tài

nguyên cần thiết để thực hiện dự án... nên cần có các phương án lập lịch điều

phối một cách hiệu quả, gắn liền với thực tế.

Bài toán RCPSP (Resource-Constrained Project Scheduling Problem) là bài

toán giải quyết các vấn đề về lập lịch dự án với tài nguyên giới hạn bởi một số

ràng buộc hoặc điều kiện nhất định. MS-RCPSP (Multi Skill - RCPSP) là bài

toán mở rộng từ bài toán gốc RCPSP sau khi được bổ sung thêm ràng buộc về

yếu tố đa kỹ năng của các tài nguyên. Trong bài toán MS-RCPSP, mỗi tài

nguyên sẽ có thể có nhiều kỹ năng khác nhau, mỗi kỹ năng có thể có nhiều bậc

(mức) kỹ năng khác, mỗi tác vụ cũng yêu cầu tài nguyên thực hiện cần đáp ứng

đúng loại kỹ năng và phải đạt một mức nhất định mới có thể thực hiện được.

Với sự mở rộng này bài toán MS-RCPSP có nhiều khả năng ứng dụng hơn

trong thực tế. Hiện nay nhiều nhà khoa học đã đưa ra các phương pháp giải bài

toán MS-RCPSP dựa trên giải thuật heuristic và metaheuristic, tuy nhiên các

phương pháp này thường dựa trên các kỹ thuật khá truyền thống nên đạt hiệu

quả chưa thực sự tốt. Do vậy, hướng nghiên cứu thứ nhất của luận án là

nghiên cứu đề xuất các phương pháp giải mới, hiệu quả hơn cho bài toán MS-

RCPSP.

Với bài toán MS-RCPSP, tài nguyên thực hiện tác vụ cần có kỹ năng phù

hợp và bậc kỹ năng lớn hơn hoặc bằng bậc (mức) kỹ năng yêu cầu, thời gian

thực hiện tác vụ là như nhau với bất kỳ tài nguyên thực hiện nào. Tuy nhiên,

khi quan sát dữ liệu thực tế, tác giả nhận thấy tài nguyên có bậc kỹ năng cao

hơn thường sẽ hoàn thành tác vụ nhanh hơn, chẳng hạn như thợ bậc 7 sẽ hoàn

thành công việc trong thời gian ngắn hơn so với thợ bậc 3. Do vậy, luận án đề

xuất bài toán mới Real-RCPSP, bài toán này bổ sung ràng buộc về thời gian

thực hiện thay đổi theo bậc kỹ năng của tài nguyên thực hiện, đây là hướng

nghiên cứu thứ hai của luận án. Tiếp theo, luận án nghiên cứu và đề xuất các

thuật toán giải bài toán Real-RCPSP, đây là hướng nghiên cứu thứ ba của

luận án.

Bài toán MS-RCPSP và bài toán Real-RCPSP có thể ứng dụng trong nhiều

lĩnh vực của khoa học và cuộc sống như lập lịch điều phối tài nguyên trong hệ

điều hành, các hệ thống phân tán, lập lịch biểu cho các dây chuyền sản

xuất,...Việc nghiên cứu giải hai bài toán trên có ý nghĩa quan trọng, giúp nâng

cao hiệu suất của nhiều lĩnh vực nhất là trong điều kiện cách mạng công nghiệp

4.0 đang diễn ra trên mọi lĩnh vực.

Nhiều trường hợp riêng của bài toán lập lịch đã được chứng minh là thuộc

lớp NP-Khó, nên không thể tìm được lời giải tối ưu trong thời gian đa thức.

Thay vì đó, một số phương pháp cận tối ưu được đề xuất để giải các bài toán

này. Một số cách tiếp cận theo Heuristic truyền thống như Min-min, Max-

min,... hoặc với các thuật toán truyền thống như GA[1],[52],

Ant[12],[39],[41],[55],… thường cho chất lượng lời giải không tốt. Do vậy,

việc nghiên cứu đề xuất các thuật toán mới là cần thiết để nâng cao chất lượng

lời giải.

2. Mục tiêu nghiên cứu

Trên cơ sở phân tích các vấn đề còn tồn tại của các nghiên cứu liên quan và

xác định ba hướng nghiên cứu, mục tiêu của luận án là:

- Nghiên cứu, đề xuất các phương pháp gần đúng để giải bài toán MS-RCPSP

nhằm cực tiểu hóa thời gian thực hiện dự án.

- Đề xuất bài toán mới Real-RCPSP, là bài toán có khả năng ứng dụng cao

trong việc lập kế hoạch điều phối sản xuất đặc biệt là các dây chuyền sản

xuất sản phẩm.

- Nghiên cứu và đề xuất thuật toán gần đúng để giải bài toán Real-RCPSP.

3. Đối tượng và phạm vi nghiên cứu

Đối tượng nghiên cứu

- Bài toán lập lịch thực hiện dự án với tài nguyên giới hạn và khả năng áp

dụng của bài toán này trong việc lập kế hoạch sản xuất, lập lịch điều phối

luồng công việc, phân công thực hiện các tác vụ dựa trên các tập tài nguyên

cho trước.

- Các phương pháp Metaheuristic như thuật toán tối ưu bầy đàn PSO (Particle

Swarm Optimization) [12],[23],[33],[56],[59], thuật toán di truyền GA

(Genetic Algorithm) [1],[24], thuật toán tiến hóa vi phân DE (Differential

Evolution) [8],[26], thuật toán tiến hóa CS (Cuckoo Search)

[20],[25],[34],[36],[60],[61].

Phạm vi nghiên cứu của luận án là các phương pháp cận tối ưu và các thuật

toán tiến hóa để giải bài toán MS-RCPSP và bài toán mới Real-RCPSP.

4. Nội dung nghiên cứu

Luận án này tập trung vào nghiên cứu giải quyết hai bài toán: bài toán MS-

RCPSP (đã có từ trước) và bài toán mới Real-RCPSP (do nghiên cứu sinh đề

xuất, dựa trên bài toán RS-RCPSP) theo hướng tiếp cận Metaheuristic. Dựa

trên các giải thuật tiến hóa bao gồm Tối ưu bầy đàn PSO, Tiến hóa vi phân DE

và CS, luận án đề xuất các thuật toán tiến hóa mới:

- M-PSO và DEM để giải bài toán MS-RCPSP

- A-DEM, R-CSM và RR-CSM để giải bài toán Real-RCPSP.

Để kiểm chứng, cuối mỗi phần đều trình bày quá trình cài đặt các thuật toán đề

xuất, thu thập, so sánh, phân tích và đánh giá kết quả thực nghiệm.

5. Phương pháp nghiên cứu

Nghiên cứu được tiến hành dựa trên các phương pháp sau:

- Phương pháp nghiên cứu tài liệu, phân tích và tổng hợp (Giai đoạn tìm hiểu

bài toán);

- Phương pháp phân tích và tổng hợp (Giai đoạn xây dựng mô hình lý thuyết

và đề xuất giải pháp);

- Phương pháp thực nghiệm (Giai đoạn kiểm chứng).

Kết quả thực nghiệm trên các bộ dữ liệu được xử lý bằng những phương pháp

- Phân tích phương sai;

- So sánh giá trị trung bình;

- Phân tích tương quan.

6. Ý nghĩa khoa học và thực tiễn

Về mặt lý thuyết khoa học, hiện nay có nhiều công trình nghiên cứu và đề

xuất phương pháp giải cho bài toán MS-RCPSP, các phương pháp dựa trên các

kỹ thuật truyền thống như Greedy, GA, Ant,... Luận án đề xuất các phương

pháp hiệu quả hơn dựa trên các kỹ thuật tiến hóa như PSO, DE và CS. Luận án

giới thiệu bài toán mới lần đầu được đề xuất là bài toán Real-RCPSP với khả

năng ứng dụng thực tế cao hơn bài toán MS-RCPSP đã có, đặc biệt là khi được

áp dụng trong các dây chuyền sản xuất hay các dự án tiến hành theo kiểu luồng

công việc (workflow). Bài toán hướng tới việc lập kế hoạch sản xuất tự động

nhằm tối thiểu hóa thời gian thực hiện (makespan).

Về thực tiễn, kết quả nghiên cứu của luận án là cơ sở khoa học để thực thi

các thuật toán lập lịch điều phối thực hiện dự án với tài nguyên giới hạn trong

thực tế. Luận án cũng nghiên cứu và đề xuất phương pháp số hóa dữ liệu thực

tế để áp dụng cho mô hình bài toán lập lịch, điều này giúp ích trong việc chuyển

đổi số và ứng dụng công nghệ thông tin trong tự động hóa sản xuất của doanh

nghiệp.

7. Bố cục của luận án

Luận án gồm các phần: Mở đầu, bốn chương chính, Kết luận và hướng phát

triển, Danh mục các công trình khoa học đã công bố, Tài liệu tham khảo. Phần

Mở đầu trình bày tính cấp thiết của đề tài luận án, những khái quát chung về

mục tiêu, đối tượng, nội dung, phương pháp nghiên cứu, ý nghĩa khoa học và

thực tiễn của luận án. Tóm tắt nội dung những phần còn lại như sau:

Chương 1. Tổng quan về bài toán MS-RCPSP

MS-RCPSP là bài toán lập lịch thực hiện dự án với tài nguyên giới hạn và

đa kỹ năng, đã được chứng minh là bài toán NP-Khó. So với bài toán RCPSP

tổng quát, bài toán MS-RCPSP là một trường hợp riêng có tính ứng dụng cao

hơn trong một số lĩnh vực thực tế đặc thù do được bổ sung yếu tố kỹ năng và

mức kỹ năng của tài nguyên thực hiện các tác vụ. Chương này trình bày tổng

quan về bài toán MS-RCPSP, các ứng dụng của các bài toán này và ba trong số

những thuật toán thuật toán metaheuristic mạnh nhất được các nhóm nghiên

cứu trước đó áp dụng để giải bài toán MS-RCPSP nói riêng cũng như các bài

toán NP-Khó nói chung là PSO, DE và CS. Ba thuật toán này cũng là cơ sở để

luận án đề xuất các thuật toán mới trong các chương tiếp theo.

Chương 2. Giải bài toán MS-RCPSP bằng phương pháp Tối ưu bầy đàn

và phương pháp Tiến hóa vi phân.

Chương này trình bày về phương pháp biểu diễn cá thể của bài toán MS-

RCPSP và đề xuất thang đo độ chênh lệch giữa các cá thể. Thang đo là thành

phần quan trọng để phục vụ cho quá trình tính toán tiến hóa của các cá thể. Để

phục vụ cho việc thực nghiệm, kiểm chứng thuật toán, chương này cũng giới

thiệu về bộ dữ liệu iMOPSE, bộ dữ liệu chuẩn được Myszkowski [42],[45] và

các cộng sự phát triển riêng cho bài toán MS-RCPSP. Trên cơ sở đó, luận án

đề xuất hai thuật toán mới đề giải bài toán MS-RCPSP:

- Thuật toán M-PSO được phát triển từ thuật toán tối ưu bầy đàn PSO

- Thuật toán DEM được xây dựng trên cơ sở thuật toán tiến hóa vi phân DE

Để kiểm chứng các thuật toán đề xuất, luận án tiến hành thực nghiệm, tổng

hợp kết quả thực nghiệm, phân tích và đánh giá tính hiệu quả.

Chương 3. Bài toán Real-RCPSP

Chương 3 trình bày về bài toán mới đề xuất Real-RCPSP, bao gồm các nội

dung như phát biểu toán học của bài toán, giới thiệu ứng dụng thực tế của bài

toán và xếp loại bài toán.

Chương 4. Giải bài toán Real-RCPSP bằng phương pháp Tiến hóa vi

phân và phương pháp Cuckoo Search

Trong chương 4, luận án trình bày các vấn đề để giải bài toán Real-RCPSP

gồm: mã hóa cá thể, xây dựng bộ dữ liệu thực tế và ba thuật toán mới để giải

bài toán Real-RCPSP.

- Thuật toán A-DEM, được xây dựng trên cơ sở thuật toán tiến hóa vi phân

DE để ứng dụng tìm lời giải cho bài toán mới

- Thuật toán R-CSM, thuật toán mới này được đề xuất trên cơ sở của thuật

toán tiến hóa Cuckoo Search (CS)

- Thuật toán RR-CSM, thuật toán mới này được cải tiến dựa trên thuật toán

R-CSM

Các thuật toán này mang lại kết quả tốt với bài toán Real-RCPSP. Các thực

nghiệm được tiến hành trên bộ dữ liệu iMOPSE và bộ dữ liệu TNG do nghiên

cứu sinh tự thu thập và xây dựng. Kết quả thực nghiệm được thu thập, tổng

hợp, phân tích và đánh giá tính hiệu quả.

CHƯƠNG 1

TỔNG QUAN VỀ BÀI TOÁN MS-RCPSP

Các bài toán lập lịch đã được đề xuất, nghiên cứu từ năm 1950 [37], nhiệm

vụ chính của việc lập lịch là tìm ra một lịch biểu để thiết lập các tài nguyên sẵn

có trong việc thực hiện các công việc/tác vụ (task) và thỏa mãn tập ràng buộc

cho trước nhằm đạt được một mục tiêu cụ thể, thường là tối thiểu hóa chi phí

và/hoặc thời gian thực hiện của toàn dự án hoặc một quy trình sản xuất. Bài

toán lập lịch được ứng dụng trong nhiều lĩnh vực khác nhau như lập lịch điều

phối tài nguyên trong hệ điều hành [39], lập lịch cho dây chuyền sản xuất,...

hoặc ứng dụng trong lĩnh vực kinh tế, tài chính [11],[62],[CT4], quân sự

[17],[18],[28],[CT4], … Nhiều bài toán lập lịch tổng quát đã được chứng minh

là thuộc lớp NP-Khó [2],[22],[46].

Ngày nay, rất nhiều ứng dụng trong nghiên cứu khoa học và thực tiễn có sử

dụng đến dữ liệu dạng luồng công việc, đặc trưng của các ứng dụng này là phải

xử lý nhiều tác vụ với dữ liệu vào/ra giữa các tác vụ là rất lớn. Tìm ra một lịch

biểu tốt để gán các tài nguyên thực hiện từng tác vụ trong một chuỗi công việc

một cách hiệu quả là rất cần thiết và thu hút sự tập trung của nhiều nhà khoa

học.

RCPSP (Resource-Constrained Project Scheduling Problem) [2],[46],

[CT4] là bài toán lập lịch dự án với tài nguyên giới hạn, đã được chứng minh

là bài toán thuộc lớp NP-Khó. Mục tiêu là tìm ra lịch biểu thực hiện dự án với

thời gian tối thiểu trong điều kiện hạn chế về tài nguyên thực hiện. Hiện nay,

bài toán này được nghiên cứu và ứng dụng trong nhiều lĩnh vực. Luận án tập

trung tìm hiểu một trường hợp mở rộng của bài toán RCPSP, được đặt tên là

MS-RCPSP.

Chương này gồm các nội dung chính sau:

Phần 1.1: Trình bày về bài toán lập lịch thực hiện dự án với tài nguyên giới

hạn và đa kỹ năng (MS-RCPSP), các ứng dụng của bài toán này.

Phần 1.2: Trình bày 03 thuật toán metaheuristic để tìm nghiệm gần đúng áp

dụng cho các bài toán thuộc lớp NP-Khó, gồm: PSO, DE, CS.

1.1. Bài toán MS-RCPSP

1.1.1. Mô tả bài toán

1.1.1.1. Đặt vấn đề

Mục tiêu của bài toán RCPSP là tìm phương án lịch biểu tốt nhất để thực

hiện các tác vụ (task) của dự án trong điều kiện bị giới hạn về tài nguyên và các

tác vụ có ràng buộc về thứ tự thực hiện. Hàm mục tiêu của bài toán RCPSP

được đánh giá dựa trên một trong hai đại lượng là thời gian thực thi (makespan)

hoặc chi phí thực thi (cost) hoặc kết hợp cả hai đại lượng này (đa mục tiêu).

Trong RCPSP, nhiều tác vụ được đưa ra để thực hiện, mỗi tác vụ được mô

tả theo thời gian bắt đầu và kết thúc. Một tác vụ bất kỳ khi đã bắt đầu thì không

thể dừng lại cho đến khi kết thúc. Các tác vụ liên quan đến nhau bằng các mối

quan hệ ưu tiên về trình tự thực hiện. Theo thứ tự ưu tiên, tác vụ cần phải hoàn

thành trước thời gian bắt đầu của tác vụ khác được gọi là những tác vụ tiền

nhiệm. Các tài nguyên được cung cấp hữu hạn và được sử dụng để thực hiện

các tác vụ. Khi tác vụ cần, một số tài nguyên sẽ được sử dụng, số tài nguyên

được cấp không được vượt quá số sẵn có. Một tác vụ có thể sử dụng nhiều tài

nguyên, một đơn vị tài nguyên chỉ dùng cho một tác vụ tại một thời điểm.

Bài toán RCPSP: RCPSP [2], [CT4] là bài toán tối ưu tổ hợp, thuộc lớp

NP-Khó, gồm các thành phần (V,t,C,L,S,s), trong đó:

• V ={W0,...,Wn+1}: tập hợp các tác vụ cần thực hiện.

trong đó:

- W1,..., Wn là các tác vụ cần thực hiện

- W0, Wn+1 là 2 tác vụ giả định, được bổ sung để phục vụ việc xác định thời

điểm bắt đầu và thời điểm kết thúc của dự án.

• W = {W1,...,Wn} tập các tác vụ (thật) cần thực hiện.

• t = {t0,t1,...,tn+1} thời gian thực hiện của các tác vụ.

• ti: thời gian thực hiện của Wi. Các giá trị đặc biệt: t0 = tn+1 = 0.

• P: lịch biểu để thực hiện

• Bi: thời gian bắt đầu của tác vụ i

• Ei: thời gian hoàn thành tác vụ i, dễ nhận thấy: Ei = Bi + ti

• Vq = {Wi ∈ W | Bi ≤ q < Bi +ti} tập các tác vụ (thật) đang thực hiện tại thời

điểm q.

• C: tập các ưu tiên, (Wi, Wj) ∈ C, nghĩa là tác vụ Wi thực hiện trước tác vụ Wj

• L: tập hợp các tài nguyên, L = {L1, L2,..., Lk }, giả thiết chúng có thể được

tái sử dụng.

• S = {S1,..., Sk } tập hợp chứa thông tin về dung lượng tài nguyên, Sk thể hiện

dung lượng của Lk.

• sik: số lượng tài nguyên Lk được huy động để thực hiện Wi.

giả sử P0 = 0, một lời giải là khả thi nếu thỏa mãn các ràng buộc sau đây:

(1.1) Bj – Bi ≥ ti  (Wi, Wj)  C

𝑊𝑖𝑉𝑞

∑ (1.2) 𝑠𝑖𝑘 ≤ 𝑆𝑘 ∀𝐿𝑘 ∈ 𝐿, ∀𝑞 ≥ 0

Cụ thể:

 Ràng buộc (1.1): thể hiện ràng buộc ưu tiên giữa hai tác vụ i và j. Tác vụ

cha (task i) phải kết thúc trước thời điểm tác vụ con (task j) bắt đầu, tác

vụ con có thể không thực hiện ngay sau khi tác vụ cha kết thúc.

 Ràng buộc (1.2): số lượng tài nguyên k sử dụng để thực hiện tác vụ i tại

thời điểm q tối đa bằng dung lượng của tài nguyên k.

Makespan của lịch biểu P = Bn+1 là thời điểm bắt đầu của tác vụ cuối cùng.

Định nghĩa 1.1[2]: RCPSP là bài toán tìm kiếm lịch biểu P sao cho

makespan của P là tối thiểu theo các ràng buộc (1.1), (1.2).

Ký hiệu:

 X: tập các lời giải rời rạc, Pall: là tập các lời giải khả thi, Pall ⊆ X

 Hàm mục tiêu: f: Pall → ℝ

cần tìm lời giải khả thi P ∈ Pall, thể hiện bởi hàm f(P) là min hoặc max.

Ví dụ 1.1[2]:

Trong bảng 1.1 dưới đây, RCPSP khởi tạo 10 tác vụ, sử dụng 2 tài nguyên

với S1 = 7 và S2 = 4.

2 1 2 2 2 0 1 3 1 0 0 0 4 1 1 3 1 2 6 3 0 5 2 1 3 1 1 6 2 1 1 1 0 Bảng 1.1: Thông tin đầu vào của dự án Wi W0 W1 W2 W3 W4 W5 W6 W7 W8 W9 W10 W11 0 ti si1 0 si2 0

Quan hệ ràng buộc về thứ tự ưu tiên của các tác vụ được thể hiện dưới dạng

W10

W11

đồ thị như trong Hình 1.1.

Hình 1.1. Đồ thị ưu tiên thực hiện các tác vụ.

Lịch biểu với makespan tối thiểu Bn+1=12 được thể hiện dưới dạng lược đồ

Gantt dạng mảng 2 chiều như trong hình 1.2, trong đó trục x thể hiện thời gian,

Hình 1.2. Biểu đồ Gantt về thực hiện các tác vụ theo thời gian

trục y thể hiện yêu cầu tài nguyên sử dụng.

1.1.1.2. Phát biểu bài toán MS-RCPSP

MS-RCPSP [4],[6],[22],[31],[CT4] là bài toán lập lịch thực hiện dự án với

tài nguyên giới hạn và đa kỹ năng, được mở rộng từ bài toán RCPSP. MS-

RCPSP được bổ sung thêm yếu tố đa kỹ năng của tài nguyên, theo đó, mỗi tài

nguyên có các kỹ năng (skill) khác nhau và mỗi kỹ năng có một mức/bậc (level)

nhất định. Mỗi tác vụ sẽ yêu cầu tài nguyên đáp ứng kỹ năng và mức kỹ năng

cụ thể để thực hiện. Do bổ sung ràng buộc mới, bài toán MS-RCPSP gần với

các dự án thực tế có liên quan đến yếu tố kỹ năng và mức kỹ năng hơn.

Phát biểu toán học của bài toán MS-RCPSP

Các ký hiệu:

 Ci: tập tác vụ (task) cần thực hiện trước tác vụ i

 S: tập tất các các kỹ năng của các tài nguyên; Si: Tập các kỹ năng của tài

nguyên i, Si  S;

 Si: kỹ năng thứ i;

 tj: thời gian thực hiện tác vụ j

 L: tập các tài nguyên;

 Lk: tập tài nguyên có thể thực hiện tác vụ k; Lk  L

 Li: tài nguyên thứ i

 W: tập các tác vụ của dự án;

 Wk: tập các tác vụ có thể thực hiện bởi tài nguyên k, Wk  W

 Wi: tác vụ thứ i

 ri: tập các kỹ năng được yêu cầu để thực hiện tác vụ i. Một tài nguyên có

thể thực hiện được tác vụ i nếu có kỹ năng giống với kỹ năng yêu cầu của

tác vụ i và có mức kỹ năng lớn hơn hoặc bằng mức kỹ năng yêu cầu.

t: biến xác định tài nguyên v có đang thực hiện tác vụ u tại thời điểm t

 Bk, Ek: thời gian bắt đầu và thời gian kết thúc thực hiện tác vụ k

 Au,v

hay không; 1: có, 0: không;

 hi: mức kỹ năng của kỹ năng (skill) i;

 gi: loại kỹ năng i;

 m: makespan của lịch biểu

 P: một lịch biểu khả thi của bài toán;

 Pall: tập tất cả các lịch biểu

 f(P): hàm mục tiêu, để tính makespan của P

 n: số tác vụ, z: số tài nguyên

Mục tiêu của bài toán MS-RCPSP là tìm lịch biểu P sao cho:

f(P)  min

Lịch biểu tìm được cần thỏa mãn các ràng buộc sau:

(1.3)  Sk    Lk L

(1.4)  tj  0  Wj W

(1.5)  Ej  0  WjW

(1.6)

(1.7)

𝑞  ∀ 𝐿𝑘 ∈ 𝐿, ∀𝑞 ∈ 𝑚 ∶ ∑ 𝐴𝑖,𝑘

(1.8) ≤ 1  Ei  Ej - tj WjW, j1, Wi Cj  ∀ W𝑖 ∈ 𝑊𝑘 ∃ 𝑆𝑞 ∈ 𝑆𝑘 ∶ 𝑔𝑆𝑞 = 𝑔𝑟𝑖 và ℎ𝑆𝑞 ≥ ℎ𝑟𝑖 𝑛 𝑖=1

𝑞 ∈ {0; 1}

𝑞 = 1; với 𝐴𝑗,𝑘

(1.9)  ∀ 𝑊𝑗 ∈ 𝑊 ∃! 𝑞 ∈ [0, 𝑚], ! 𝐿𝑘 ∈ 𝐿: 𝐴𝑗,𝑘

Cụ thể:

 Ràng buộc (1.3): mỗi tài nguyên phải có tối thiểu một kỹ năng nào đó

 Ràng buộc (1.4, 1.5): thời gian thực hiện của tác vụ bất kỳ tối thiểu phải

bằng 0 (thực tế thì mọi tác vụ thật, có thời gian thực hiện tối thiểu luôn >

0, trường hợp bằng 0 để minh họa cho 2 tác vụ giả thể hiện thời điểm bắt

đầu và kết thúc của dự án)

 Ràng buộc (1.6): tác vụ cha (task i) phải kết thúc trước thời điểm tác vụ

con (task j) bắt đầu. Thời điểm tác vụ i kết thúc ký hiệu là Ei, thời điểm

tác vụ con j bắt đầu là Ej - tj (thời điểm kết thúc trừ đi thời gian thực hiện).

 Ràng buộc (1.7) nghĩa là: với mọi tác vụ i  Wk (tập các tác vụ mà tài

nguyên k thực hiện được), luôn tồn tại kỹ năng S  Sk (tập skill của tài

nguyên k) sao cho 𝑔𝑆 = 𝑔𝑆𝑖: loại skill của r trùng với loại kỹ năng của Li mà tác vụ i yêu cầu. ℎ𝑆𝑞 ≥ ℎ𝑟𝑖 : mức kỹ năng của tài nguyên thực hiện cao hơn hoặc bằng mức kỹ năng yêu cầu.

𝑞 =

 Ràng buộc (1.8): tại mỗi thời điểm (q), mỗi tài nguyên chỉ được thực hiện

𝑛 𝑖=1

0 thì tài nguyên k không được gán cho

𝑛 𝑖=1

=1 thì tài nguyên k được gán cho một tác vụ duy

tối đa một tác vụ. Nếu ∑ 𝐴𝑖,𝑘 𝑞 tác vụ nào, nếu ∑ 𝐴𝑖,𝑘 nhất.

 Ràng buộc (1.9): mỗi tác vụ chỉ được gán cho một tài nguyên duy nhất và

chỉ được thực hiện bởi một tài nguyên duy nhất.

Trong bài toán MS-RCPSP, mỗi tác vụ có thêm các yêu cầu về kỹ năng

(skill) của tài nguyên cần để thực hiện, mỗi tài nguyên cũng được chia làm

nhiều mức kỹ năng khác nhau. Các ràng buộc về kỹ năng của tài nguyên được

yêu cầu để thực hiện một tác vụ được mô tả dưới dạng một ma trận như ví dụ

được minh họa trong hình 1.3 dưới đây:

 Có thể thiết lập  Không thể thiết lập Tác vụ S2.2 S3.1

S2.2 S1.1 W1 W2 W3 W4

Tài nguyên

                S1.3, S2.2 S2.1, S3.2 S1.2, S2.1 S2.2, S3.3 L1 L2 L3 L4

Hình 1.3. Ma trận quan hệ giữa tác vụ và kỹ năng của tài nguyên

Trong hình 1.3, ký hiệu: Si.j nghĩa là kỹ năng Si và mức kỹ năng j. Tác vụ

yêu cầu tài nguyên thực hiện phải đáp ứng loại kỹ năng và mức kỹ năng cụ thể.

Tài nguyên thực hiện cần có cùng loại kỹ năng và mức kỹ năng lớn hơn hoặc

bằng mức kỹ năng yêu cầu.

Cụ thể:

Tác vụ W1, yêu cầu tài nguyên có loại kỹ năng S2 và mức kỹ năng lớn hơn

hoặc bằng 2. Đối chiếu với bảng tài nguyên, ta thấy tài nguyên L1 có loại kỹ

năng S2 và mức kỹ năng của S2 là 2, do vậy L1 có thể thực hiện W1.

1.1.2. Một số ứng dụng thực tế của bài toán MS-RCPSP

1.1.2.1. Ứng dụng trong Fog Computing và Edge Computing

Fog Computing [32] được thiết kế để khắc phục những hạn chế của điện

toán đám mây (Cloud Computing) bằng cách cung cấp một kiến trúc phân tán

trong đó một số dữ liệu sẽ được phân loại để xử lý ngay bởi các thiết bị ở gần

nơi phát sinh dữ liệu thay vì phải gửi về trung tâm đám mây, như vậy vừa tiết

kiệm được chi phí truyền thông, giảm khả năng bị mất mát hoặc rò rỉ (do vấn

đề bảo mật) trên đường truyền lại vừa tránh được nghẽn đường truyền mạng.

Những kiến trúc này được thiết kế và xây dựng theo các mô hình của Edge

Computing (Điện toán biên).

Nhiệm vụ chính của Fog Computing là tìm phương án bố trí các nguồn tài

nguyên tính toán bao gồm máy chủ, router, các thiết bị lưu trữ, database sao

cho tối đa hóa việc truy xuất và xử lý cục bộ. Nói cách khác, cần tìm cách sắp

xếp sao cho chỉ những tác vụ đặc thù (chẳng hạn yêu cầu nhiều tài nguyên) mới

phải gán cho các tài nguyên ở đám mây trung tâm (vốn ở rất xa khách hàng),

còn những tác vụ có thể giải quyết tại chỗ thì đều được gán cho những nguồn

tài nguyên ngay tại nơi phát sinh yêu cầu (chẳng hạn các máy chủ có sẵn trong

mạng LAN của khách hàng). Làm như vậy vừa giảm bớt được chi phí thực thi

(có lợi cho khách hàng), bao gồm chi phí truyền thông tin và chi phí xử lý dữ

liệu, vừa giảm bớt được tình trạng tắc nghẽn đường truyền trong những giờ cao

điểm (có lợi cho nhà cung cấp dịch vụ), lại có thể rút ngắn thời gian xử lý để

đáp ứng yêu cầu về thời gian thực của một số ứng dụng. Các giải pháp lập lịch

dựa trên bài toán RCPSP có thể được áp dụng trong trường hợp này [CT4].

Việc lập lịch trong môi trường Fog Computing được chia làm 3 nhóm:

- Lập lịch cấp phát tài nguyên (resource scheduling)

- Lập lịch quản lý luồng công việc (workflow scheduling)

- Lập lịch quản lý các tác vụ (task scheduling)

1.1.2.2. Ứng dụng trong các ngành kinh tế

Vấn đề "giá tùy chọn" (Option Pricing Problem)

Mô hình định giá tùy chọn [11], [62] là mô hình toán học sử dụng các biến

nhất định để tính toán giá trị lý thuyết của một tùy chọn. Một tùy chọn hiểu là

một hợp đồng hai bên trong việc thực hiện một giao dịch. Có hai loại tùy chọn

chính:

- Call: là hợp đồng tùy chọn cung cấp cho bạn quyền nhưng không phải

là nghĩa vụ mua tài sản ở mức giá đã xác định trước hoặc vào ngày hết

hạn.

- Put: là hợp đồng tùy chọn cung cấp cho bạn quyền nhưng không phải là

nghĩa vụ bán tài sản ở mức giá đã xác định trước ngày hết hạn.

Giá tùy chọn là nội dung cốt lõi của tài chính hiện đại, được áp dụng trong

thị trường chứng khoán hoặc trong thị trường tài chính nói chung.

Vấn đề thị trường chứng khoán (Stock Problem)

Black and Scholes đã đề xuất mô hình Black-Scholes[11] áp dụng trong thị

trường chứng khoán, sau đó mô hình tính toán này được sử dụng để tính toán

trong lĩnh vực tài chính khác. Ngày nay mô hình này trở thành một công cụ

không thể thiếu trong thị trường chứng khoán và thị trường tài chính.

Vấn đề vị trí thiết lập kho (Facility Location Problem)

Mục tiêu là tìm kiếm vị trí đặt các kho hàng (chi nhánh) trong mạng (chuỗi)

sao cho tối thiểu hóa chi phí vận chuyển đồng thời xem xét đến các yếu tố ràng

buộc như: đối thủ cạnh tranh, không đặt gần các vị có thể gây nguy hiểm như

cháy nổ. Bài toán này đã được Y Gao[62] đề xuất dựa trên lý thuyết không chắc

chắn.

1.1.2.3. Ứng dụng trong lĩnh vực quân sự

Một bài toán con của RCPSP, ký hiệu là SRCPSP (Stochastic Resource-

constrained Project Scheduling) [17], được áp dụng trong quân sự ở ba trường

hợp cụ thể sau.

Lập kế hoạch nhiệm vụ (Mission Planning)

Một nhiệm vụ quân sự có thể được mô hình hóa như một dự án bao gồm

một hệ thống phân cấp công việc khác nhau. Các tài nguyên bao gồm: nhân

lực, tài liệu, thiết bị cần thiết để hoàn thành nhiệm vụ. SRCPSP đã được áp

dụng thành công để lập lịch thực hiện các tác vụ trên tàu hải quân [18].

Bảng 1.2: Dữ liệu về tác vụ và yêu cầu thực hiện

Thứ tự thực hiện

Tác vụ J1 J2 J3 J4 J5 J6 J7 J8 J9 J10 Thời gian thực hiện (giờ) 13 6 7 9 13 11 8 12 13 15 Kỹ năng cần thiết [0,1,0,0] [0,0,1,0] [1,0,0,0] [0,0,0,1] [0,1,0,0] [0,0,1,0] [1,0,0,0] [1,1,0,0] [0,0,1,0] [0,0,1,0] - - - Thời hạn (giờ) 15 40 20 30 50 60 50 60 40 50

Bảng 1.2 thể hiện rằng trên tàu hải quân có 10 công việc(Job) cần thực hiện,

từ J1 đến J10, mỗi tác vụ có thời gian xử lý và yêu cầu kỹ năng nhất định đối với

thủy thủ. Biểu diễn thể hiện công việc 9 chỉ bắt đầu sau khi công

việc 1 bắt đầu được 14 giờ, các thủy thủ có thể có một hoặc nhiều kỹ năng trong

tập {K1, K2, K3, K4}, Áp dụng thuật toán xếp lịch, với 4 thủy thủ, kết quả

được thể hiện trong sơ đồ Gantt như hình 1.4 dưới đây.

Hình 1.4. Biểu đồ Gantt mô tả một phương án lịch biểu.

Lập kế hoạch dẫn đường

Bài toán Lập kế hoạch dẫn đường (Shortest Path Problem - SPP) nhằm tìm

đường đi ngắn nhất từ nguồn tới đích với chi phí thực hiện thấp nhất [28]. SPP

được áp dụng trong việc dẫn đường cho thiết bị bay không người lái (UAV -

Unmanned Aerial Vehicle) đến một đích cụ thể thông qua một tuyến đường

ngắn nhất và khả năng thành công bay đến đích cao nhất, chẳng hạn đảm bảo 2

UAV không va chạm nhau trên lịch trình. Hành trình của UAV cần đảm bảo

thỏa mãn các ràng buộc về khả năng sống sót, các ràng buộc vật lý, cảm biến

và các hoạt động khác. SPP chính là một nhánh của bài toán RCPSP.

Hình 1.5 mô tả tuyến đường và khả năng tính toán thông qua cảm biến của

hai UAV nhằm đảm bảo không va chạm trong quá trình thực hiện chuyến bay

[28].

Hình 1.5. Sơ đồ bay của 2 chiếc UAV

Thiết lập mạng vận chuyển hậu cần (Configuring Logistics Networks)

Năm 2005, Bộ Quốc phòng Mỹ xác định xây dựng chuỗi cung ứng vật tư

quân trang trong quân đội là 1 trong 25 nhiệm vụ trọng điểm của quân đội [13].

Với yêu cầu đó, quân đội Mỹ đã xây dựng mạng vận chuyển hậu cần quân sự

nhằm giảm thiểu thời gian cấp phát trang thiết bị đến các vị trí đóng quân tại

các vị trí khác nhau đồng thời kiểm soát lượng vật tư còn tồn trong kho. Bài

toán RCPSP [2],[46] được nghiên cứu ứng dụng trong việc lên kế hoạch vận

chuyển trong mạng hậu cần quân sự theo mô hình trên.

1.1.3. Những nghiên cứu liên quan

Như phần trước đã giới thiệu, bài toán lập lịch với tài nguyên giới hạn và

đa kỹ năng MS-RCPSP có nhiều ứng dụng trong khoa học và thực tiễn nên đã

được nghiên cứu rộng rãi bởi nhiều nhà khoa học và đã có nhiều công bố khoa

học liên quan đến bài toán này. MS-RCPSP đã được chứng minh là bài toán

thuộc lớp NP-Khó [2],[22],[46] nên các nhóm tác giả đều sử dụng các phương

pháp tìm lời giải gần đúng.

Myszkowski và cộng sự [42],[45] là nhóm nghiên cứu tập trung vào bài

toán MS-RCPSP trong nhiều năm, họ công bố sớm và nhiều kết quả về bài toán

này. Ban đầu nhóm của Myszkowski giải quyết MS-RCPSP bằng các heuristic

[31],[43],[44], chẳng hạn như bố trí thứ tự thực thi các tác vụ dựa trên thời

lượng của chúng. Các tác vụ được sắp xếp theo thời lượng tăng dần, sau đó tài

nguyên được gán cho chúng theo thứ tự đó. Nếu có nhiều tài nguyên phù hợp

với một tác vụ thì tài nguyên rẻ nhất sẽ được chọn.

Sau đó, theo xu hướng chung, Myszkowski và cộng sự nhận ra rằng các

heuristic thiếu ổn định và có phạm vi ứng dụng hẹp so với các metaheuristic

nên đã chuyển sang nghiên cứu các thuật toán tiến hóa. Họ đã công bố các công

trình giải quyết bài toán MS-RCPSP trong đó sử dụng:

- Thuật toán Tabu Search [31];

- Thuật toán Đàn kiến [44];

- Thuật toán GA [43];

- Một số thuật toán khác

So với các thuật toán đã công bố, đóng góp lớn nhất của Myszkowski và

cộng sự là đã xây dựng và công bố bộ dữ liệu chuẩn iMOPSE [42]. Trong khi

các nhóm nghiên cứu trước đó, chẳng hạn [51], thường sử dụng bộ dữ liệu

PSPLIB [47] khi giải quyết bài toán RCPSP tổng quát, Myszkowski chỉ ra rằng

bộ dữ liệu này thiếu trường thông tin về chi phí thực hiện tác vụ, do đó không

hoàn toàn thích hợp với bài toán MS-RCPSP. Nhóm của Myszkowski đã tự xây

dựng và công bố bộ dữ liệu chuẩn iMOPSE [42], sau này được công nhận rộng

rãi và được nhiều nhóm nghiên cứu cũng như chính luận án này sử dụng.

Qua các công trình công bố, có thể thấy, trong các nghiên cứu của mình,

nhóm tác giả Myszkowski sử dụng các thuật toán truyền thống như GA,

Greedy, Ant,... Luận án đặt mục tiêu tìm ra các thuật toán Metaheuristic mới để

giải bài toán MS-RCPSP và các thực nghiệm được thực hiện trên bộ dữ liệu

iMOPSE.

Một nhóm nghiên cứu bài toán MS-RCPSP lâu năm khác là nhóm của

Hosseinian [4],[5],[6],[7]. Năm 2018, Hosseinian và Baradaran công bố kết quả

nghiên cứu [4] về bài toán Multi-mode Multi-skilled Resource-Constrained

Project Scheduling Problem (MMSRCPSP), một biến thể của bài toán MS-

RCPSP trong đó bổ sung thêm ràng buộc rằng mỗi tác vụ chỉ có thể được thực

thi ở một vài chế độ (mode) định trước và không thể thay đổi mode một khi quá

trình thực thi đã được bắt đầu. Để giải quyết bài toán, Hosseinian và cộng sự

đã sử dụng thuật toán GA cổ điển kết hợp với phương pháp ra quyết định dựa

trên độ đo thông tin Shanon-entropy để lựa chọn cá thể cho thế hệ kế tiếp. Thực

nghiệm được tiến hành trên bộ dữ liệu sinh ngẫu nhiên bởi phần mềm ProGen.

Tiếp tục hướng nghiên cứu đó, năm 2019 nhóm tác giả này công bố bài báo [5]

trong đó sử dụng thuật toán Dandelion Algorithm để giải quyết bài toán MS-

RCPSP. Dandelion [53] là thuật toán tiến hóa mới được công bố năm 2017, lấy

ý tưởng từ khả năng tự thay đổi bán kính và hướng gieo hạt của cây Bồ công

anh. Trong bài này nhóm tác giả lựa chọn thực nghiệm trên iMOPSE [42], bộ

dữ liệu chuẩn được công nhận rộng rãi, đa dạng và phù hợp hơn với bài toán

MS-RCPSP. Năm 2020, nhóm tác giả này tiếp tục công bố bài báo [6] giải

quyết bài toán MS-RCPSP đa mục tiêu với hai hàm mục tiêu là thời gian và chi

phí thực hiện dự án. Nhóm tác giả sử dụng thuật toán Pareto-based Grey Wolf

Optimizer và tiếp tục kiểm chứng các kết quả trên bộ dữ liệu chuẩn iMOPSE

[42].

Qua phân tích tổng quan trên có thể thấy cách tiếp cận của Hosseinian và

Baradaran có nhiều điểm tương đồng với luận án này về bài toán (MS-RCPSP),

về cách lựa chọn giải pháp (là những thuật toán tiến hóa mới thay vì những

thuật toán “truyền thống” như GA, PSO) và về việc lựa chọn bộ dữ liệu thực

nghiệm (iMOPSE). Tuy nhiên những bài toán của Hosseinian và Baradaran

mới chỉ dừng ở mô hình lý thuyết, chưa được gắn với thực tế cũng như chưa

được thực nghiệm trên một bộ dữ liệu thực tế. Trong luận án này, ngoài thực

nghiệm với bộ dữ liệu iMOPSE, các thuật toán mới còn được kiểm chứng bằng

việc triển khai thực nghiệm trên các bộ dữ liệu thực tế.

Ngoài các nhóm nghiên cứu dài hạn với những chuỗi bài báo, nhiều tác giả

đã công bố những công trình đơn lẻ, đại đa số dựa trên các thuật toán tiến hóa.

Năm 2017, Javanmard và cộng sự sử dụng 2 thuật toán tiến hóa truyền

thống là GA và PSO để lên phương án lịch biểu cho các tài nguyên đa kỹ năng

(trên thực tế là các công nhân và kỹ sư) thực hiện một dự án trong ngành hóa

chất với mục tiêu tối thiểu hóa tổng chi phí của dự án [51]. Hai thuật toán đề

xuất được kiểm chứng trên bộ dữ liệu PSPLIB [47], vốn không hoàn toàn thích

hợp với những bài toán lập lịch có mục tiêu là tối thiểu hóa chi phí. Hơn nữa ở

khâu thực nghiệm các tác giả không so sánh được các thuật toán truyền thống

của mình với những thuật toán mới hơn mà chỉ so sánh với nhau.

Cũng nghiên cứu các bài toán đa mục tiêu như nhóm của Hosseinian, H.

Davari-Ardakani [21] đề xuất một biến thể đa mục tiêu của bài toán MS-

RCPSP nhằm tối thiểu hóa hai đại lượng là thời gian và chi phí thực hiện của

dự án. Bài toán đề xuất, được tác giả ký hiệu là MSPSP [21], chỉ giới hạn trong

những dự án có 2 đặc điểm (có thể nói là không quá phổ biến) sau đây:

- Thời điểm thực hiện là tùy ý, chẳng hạn dự án có thể được thực hiện

vào các buổi tối hoặc ngày nghỉ cuối tuần

- Chi phí về năng lượng là rất cao, có thể so sánh được với tiền lương

trả cho nhân viên.

Dừng lại ở việc phát biểu bài toán, H. Davari-Ardakani và đồng nghiệp [21]

chưa đề xuất được giải pháp mới mà chỉ tiến hành thực nghiệm với những giải

pháp đã có như Max-min, vì vậy bài toán có thể coi là vẫn còn để mở.

Để giải quyết bài toán MS-RCPSP, H. Dai [15] sử dụng thuật toán Memetic,

là phiên bản cải tiến của thuật toán GA nhờ bổ sung thêm thao tác tìm kiếm lân

cận (local search). Cách tiếp cận H. Dai khá tương đồng với luận án này ở các

điểm sau:

- Lựa chọn iMOPSE làm bộ dữ liệu thực nghiệm;

- Lựa chọn các thuật toán của nhóm Myszkowski làm đối tượng so

sánh do tính hiệu quả của chúng.

Tuy nhiên công trình của H. Dai có một số hạn chế sau:

- Lựa chọn những thuật không phải là hiệu quả nhất của nhóm

Myszkowski làm đối tượng so sánh, chẳng hạn thuật toán GRASP;

- Thuật toán đề xuất (memetic) là một trong những thuật toán truyền

thống, đã được sử dụng từ lâu nên không còn nhiều tính đột phá.

Nemati-Lafmejani [48] đã phát triển một mô hình tối ưu hóa tích hợp hai

mục tiêu để giải quyết bài toán MS-RCPSP, mục tiêu của mô hình đề xuất là

giảm thiểu chi phí và thời gian thực hiện dự án. Younis và cộng sự [38] đã đề

xuất một thuật toán metaheuristic kết hợp các phương pháp tiếp cận tối ưu hóa

đàn kiến và tìm kiếm lân cận để lập lịch trong điện toán lưới.

Một số nghiên cứu tập trung giải quyết các lớp bài toán con khác của MS-

RCPSP. Zhu và cộng sự [29] đã đề xuất một thuật toán tiến hóa dựa trên kỹ

thuật multi-verse kết hợp với một số thuật toán heuristic khác.

Một số tác giả cũng đã nghiên cứu để áp dụng bài toán MS-RCPSP cho

nhiều lĩnh vực khoa học và tài chính. O.P. Mejia [40] đã phát triển một thuật

toán lập lịch để quản lý các hoạt động của phòng thí nghiệm hạt nhân. Để giải

quyết vấn đề của các cảm biến dày đặc trong mạng cảm biến không dây, R.

Wan [49] đề xuất một thuật toán lập lịch tiết kiệm năng lượng, sắp xếp một số

cảm biến dự phòng vào chế độ nghỉ để giảm xung đột truyền dữ liệu và tiêu

hao năng lượng. W. Guo [56] đã phát triển một thuật toán dựa trên PSO có

được hiệu suất tốt hơn so với các phương pháp tiếp cận trước đây về sử dụng

năng lượng. H. Cheng [14] và cộng sự đã xây dựng một thuật toán dựa trên

PSO khác có tên là DPSO-CA dựa trên PSO rời rạc nhằm mục đích giảm thiểu

nhiễu đồng kênh trong mạng. MS-RCPSP cũng được nghiên cứu và áp dụng

trong lĩnh vực tài chính ngân hàng bởi Black and Scholes [11] và Chen[58].

Bảng 1.3 dưới đây tổng hợp lại các nghiên cứu chính liên quan đến bài toán

MS-RCPSP.

Bảng 1.3: Tổng hợp các nghiên cứu về bài toán MS-RCPSP

TT Năm Nhóm tác giả Thuật toán Bộ dữ liệu

2017 Javanmard [47],[51] GA, PSO PS-LIB 1

iMOPSE 2 2013- 2019 Myszkowski và cộng sự [31],[42],[43],[44],[45] GA, Ant, Greedy,...

2018 Hosseinian [4],[5],[6],[7] GA, PSO 3 ProGen, iMOPSE

2019 H. Davari-Ardakani [21] Min-Max iMOPSE 4

2019 Huafeng Dai [15] Memetic iMOPSE 5

Luận án tập trung giải quyết bài toán MS-RCPSP bằng các thuật toán

Metaheuristic mới, các thuật toán được kiểm chứng qua việc thực nghiệm với

bộ dữ liệu iMOPSE. Đồng thời, để gắn với thực tế, luận án cũng đề xuất bài

toán mới Real-RCPSP, các thuật toán giải bài toán này và triển khai thực

nghiệm với các bộ dữ liệu thực tế để kiểm chứng.

1.2. Một số thuật toán metaheuristic tìm nghiệm gần đúng

Để tìm nghiệm gần đúng có rất nhiều thuật toán đã được đề xuất và sử dụng

như Thuật toán nhánh cận [CT3], Tabu Search [CT6], PSO, DE, Cuckoo

Search,... Luận này sử dụng các thuật toán PSO, DE, Cuckoo Search.

1.2.1. Thuật toán PSO

k) + c2.rand2().(gbest – xi

k+1 = 𝜔.vi

k+1

(1.10) Tối ưu bầy đàn (Particle Swarm Optimization - PSO) [23],[33],[56],[59], [CT2] là một thuật toán tiến hóa. Tương tự như các thuật toán tiến hóa khác, PSO sẽ tiến hành tìm kiếm dựa trên quần thể, ban đầu quần thể được khởi tạo một cách ngẫu nhiên với số cá thể xác định. Tuy nhiên PSO khác với các thuật toán tiến hóa khác là mỗi cá thể trong quần thể được xác định bởi hai tham số cơ bản là vector vị trí (đại diện cho kinh nghiệm của cá thể qua các thế hệ) và vector vận tốc (vector dịch chuyển - đại diện cho kinh nghiệm của quần thể qua các thế hệ). Mỗi cá thể sẽ dịch chuyển trong không gian tìm kiếm với một vận tốc riêng, sau mỗi thế hệ các cá thể sẽ dịch chuyển theo hướng về vị trí tốt nhất của chính cá thể đó trong quá khứ và vị trí tốt nhất của quần thể và sau mỗi thế hệ các cá thể sẽ hướng tới các vùng tìm kiếm tốt hơn trong không gian tìm kiếm. Trong quá trình tìm kiếm các cá thể sẽ cập nhật vector dịch chuyển và vector vị trí theo giá trị tốt nhất của chính cá thể đó trong quá khứ và vị trí tốt nhất của quần thể theo công thức sau: k+c1.rand1().(pbesti – xi vi

k+1 = xi

k + vi

(1.11) xi

k+1: là vector dịch chuyển của cá thể i ở thế hệ k+1;

Trong đó:

k: là vector dịch chuyển của cá thể i ở thế hệ k;

- vi

k+1: là vector vị trí của các thể i ở thế hệ k+1;

- vi

k: là vector vị trí của cá thể i ở thể hệ k;

- xi

- pbesti: là vector vị trí tốt nhất của cá thể i tính tới thời điểm hiện tại;

- gbest: là vector vị trí tốt nhất của quần thể tính tới thời điểm hiện tại.

- Các hệ số trong công thức PSO với ý nghĩa như sau:

o : hệ số quán tính; o c1, c2: là các hệ số gia tốc thể hiện cho đặc trưng về mặt kinh nghiệm

của các thể và kinh nghiệm của quần thể.

𝑘)

𝑐1 × 𝑟1 × (𝑔𝑏𝑒𝑠𝑡 − 𝑥𝑖

𝑘)

𝑐1 × 𝑟1 × (𝑝𝑏𝑒𝑠𝑡𝑖 − 𝑥𝑖

𝑘 𝑤 × 𝑣𝑖

𝑘+1 𝑥𝑖

𝑔𝑏𝑒𝑠𝑡

𝑘

𝑘 𝑥𝑖

𝑔𝑏𝑒𝑠𝑡 − 𝑥𝑖

𝑘

𝑝𝑏𝑒𝑠𝑡𝑖

𝑝𝑏𝑒𝑠𝑡𝑖 − 𝑥𝑖

rand1, rand2: là các hệ số ngẫu nhiên trong đoạn [0,1]

Hình 1.6. Sơ đồ di chuyển của một cá thể i trong PSO

Begin Pall = Load dữ liệu iMOPSE và khởi tạo quần thể ban đầu t = 0

Chi tiết thuật toán PSO được thể hiện như trong Algorithm 1.1 dưới đây.

Algorithm 1.1. PSO Input: tmax: số thế hệ Output phương án tốt nhất gbest 1 2 3 4 while ( t < tmax ) 5 t = t + 1 6 for i=1 to size(Pall) do 7 tính giá trị hàm mục tiêu f(Pi) 8 end for 9 for i = 1 to size(Pall) do 10 if f(Pi) < f(fitnessi) then 11 pbesti = Pi 12 f(pbesti) = f(Pi) 13 end if 14 end for 15 for i=1 to size(Pall) do 16 gbest = Pi 17 f(gbest) = f(Pi) 18 end for 19 for i=1 to size(Pall) do 20 cập nhật vector dịch chuyển theo (1.3) 21 Cập nhật vector vị trí theo (1.4) 22 end for 23 end while 24 return gbest 25 end Trong đó: - f: objective function

- fitnessi: Giá trị tốt nhất của cá thể thứ i trong quần thể

từ thế hệ đầu tiên cho đến thế hệ hiện tại.

1.2.2. Thuật toán PSO kết hợp với tìm kiếm lân cận

Phương pháp Tìm kiếm lân cận [16] (hay còn gọi là Tìm kiếm cục bộ, Local

Search) là phương pháp heuristic thường được áp dụng để tìm phương án tối

ưu hoặc cận tối ưu trong một không gian tìm kiếm mà khoảng cách giữa hai

phương án bất kỳ đã được định nghĩa, tức là đã có một phép đo khoảng cách

giữa hai phương án. Dựa trên đại lượng khoảng cách đó, khái niệm vùng lân

cận sẽ được xác định. Ý tưởng chung của phương pháp Tìm kiếm lân cận là

thực hiện vòng lặp gồm các bước sau:

1. Khởi tạo phương án ban đầu (theo kiểu ngẫu nhiên hoặc bằng một kỹ

thuật nào đó).

2. Áp dụng một phép biến đổi cho phương án hiện có để thu được một tập

phương án lân cận, đây là những phương án có khoảng cách (được xác

định theo một độ đo xác định trước) tới phương án ban đầu nhỏ hơn hoặc

3. Lựa chọn phương án tốt nhất trong tập phương án lân cận, gán giá trị này

bằng một ngưỡng quy định.

cho phương án hiện có rồi quay trở lại đầu vòng lặp (bước 2).

Vòng lặp trên được thực hiện cho tới khi tìm được phương án đủ tốt để thỏa

mãn điều kiện dừng.

Phương pháp Tìm kiếm lân cận đã được các nhóm nghiên cứu tích hợp vào

PSO để cải thiện chất lượng của cá thể tại mỗi vòng đời [3],[19]. Trong không

gian tìm kiếm, các phương án không hoàn toàn độc lập mà thường có mối quan

hệ, mối quan hệ đó chi phối nhiều đặc tính của chúng. Chẳng hạn như trong bài

toán Scheduling thì hai lịch biểu càng có nhiều thành phần trùng nhau thì giá

trị makespan của chúng càng có khả năng gần nhau. Dựa vào quy luật tự nhiên

này, các nhà nghiên cứu đã đề xuất nhiều kiểu lân cận (topology) khác nhau

như kiểu Ring, kiểu Von Neuman. Mỗi topology đó mô tả một cách xác định

thứ tự giữa các phương án trong tập lân cận. Hình sau là một số kiểu lân cận

m+1

m-1

k-1

k+1

k-1

k+1

...

n+1

n-1

k+1

k-1

được mô tả trong [3].

(b)

(a)

Hình 1.7. Kiểu lân cận Ring (a) và Von Neumann (b)

k+1 ở vòng đời tiếp theo sẽ được xác định là:

Sau khi đã xác định được thứ tự giữa các phương án lân cận, phương án

(1.12)

k+1 = xi

k + vi

k+1 = ×vi

k + c1 rand1× (pbesti - xi

k) + c2rand2× (lbesti - xi

với vector dịch chuyển được định nghĩa bằng công thức:

Công thức này tương tự như công thức gốc của PSO được xây dựng bởi

Kennedy và Eberhart, chỉ thay phương án tốt nhất của quần thể gbesti bằng

phương án tốt nhất lbesti trong tập lân cận của phương án đang xét xi

Trong bài báo [CT2] đã xây dựng thuật toán L-PSO áp dụng phương pháp

Tìm kiếm lân cận, tuy nhiên bài toán đặt ra trong [CT2] không phải là đối tượng

nghiên cứu của luận án này, vì vậy phần phát biểu bài toán và phần thực nghiệm

không được giới thiệu ở đây, mà chỉ trình bày việc tích hợp phương pháp lân

cận tích hợp trong thuật toán PSO. Trong [CT2], áp dụng phương pháp lân cận

Ring với vùng lân cận có phạm vi k = 2, nghĩa là phương án đang xét xi sẽ có

tập lân cận bao gồm 2 phần tử là left (xi) và right (xi). Thuật toán đề xuất L-

PSO được mô tả trong [CT2] như sau:

Algorithm LPSO()

Input: T,S,dữ liệu công việc W[1×M],P[1×N],B[N×N],D[M×M], hằng số K, độ lệch , số lượng cá thể của quần thể NoP Output: phương án gần đúng tốt nhất gbest

Begin

1. For i=1 to NoP do 2. xi= random vectors; vi= random vectors; // Khởi tạo giá trị ngẫu nhiên cho vector vị trí và vector dịch chuyển của cá thể i

// Khởi tạo bước lặp

3. end for 4. t= 0; 5. While (the deviation of gbest > ) Do 6. for i=1 to NoP do 7. Compute new position xi // Tính vector vị trí xi

theo công thức (1.12)

// Cập nhật pbesti

// Cập nhật gbesti

8. end for 9. for i=1 to NoP do 10. Update pbesti; 11. end for 12. Update gbest; 13. for i=1 to NoP do 14. lbesti = Ring(xi) ; // Cập nhật lbesti 15. end for 16. for i=1 to NoP do 17.

// Cập nhật vector

Update vik and compute xi ; dịch chuyển vik và xi

19. end for 20. t++ ; 21. if (the deviation of gbest ≤  after K generations) // nếu sau K thế hệ mà độ lệch giữa các gbest

không vượt quá 

then gbest= Variable_Neighborhood_Searching (gbest);

23. End while; 24. Return gbest; End Function

Trong đó phương án lân cận tốt nhất lbesti của phương án hiện tại xi sẽ được

Function Ring(xi)

Input: phương án đang xét xi

Output: x trong đó Fitness(x) = min{Fitness(xi), Fitness(Left(xi)), Fitness(Right(xi))}

tính bởi hàm Ring() như sau:

Hàm tìm kiếm lân cận Variable_Neighborhood_Searching(), hạt nhân của

Function Variable_Neighborhood_Searching ( )

Input: vector vị trí xi Output: vector vị trí xk có Fitness(xk) < Fitness(xi)

Begin

1. t = 0; // Khởi tạo bước lặp 2. while (Fitness(xk) > Fitness (xi) and (t <

Max_Iteration)) 3. r = random [1,M];

// Khởi tạo giá trị r ngẫu

nhiên trong đoạn [1, M] 4. xi = RotateRight(xi, r); 5. rand1 = [1,M]; rand2 = [1,M]; // Khởi tạo ngẫu nhiên

rand1, rand2 [1,M]

6. xk = Exchange (xi, rand1, rand2); 7. if Fitness(xk) < Fitness(xi) then 8. return xk 9. else 10. return xi; 12. end if 11. t = t+1; 12. end while

End.

thuật toán LPSO được mô tả như sau:

(b)

(a)

Hình 1.8. Hàm RotateRight (a) và hàm Exchange (b)

trong đó hàm RotateRight() và hàm Exchange() được thiết kế để giúp tạo ra cá

thể đột biến cho quần thể hiện tại.

Hàm RotateRight sẽ tịnh tiến toàn bộ các phần tử của phương án về bên phải,

còn hàm Exchange sẽ hoán đổi hai phần tử của phương án như hình 1.8.

1.2.3. Thuật toán DE

Tiến hóa vi phân (Differential Evolution - DE) được đề xuất bởi R. Storn

và K. Price vào năm 1997 [26], đây là một giải thuật tiến hóa dựa trên thông

tin định hướng để tạo ra các cá thể ở thế hệ tiếp theo bằng cách sử dụng các

toán tử lai ghép, đột biến và chọn lọc. Đặc trưng của thuật toán DE là sử dụng

thông tin định hướng trong toán tử đột biến để làm đột biến các cá thể của quần

thể hiện tại. Hoạt động của thuật toán DE được mô tả như sau:

Bước 1: Giả sử không gian tìm kiếm gồm D chiều, mỗi cá thể i được biểu

diễn bởi một vector D chiều xi = (xi,1, xi,2,…,xi,D), trong đó xi,j  R, i=1,2,…,N;

j=1,2,…,D.

Để đột biến cá thể xi thuật toán DE lựa chọn 3 cá thể ngẫu nhiên từ quần

thể xr1  xr2  xr3  xi. Khi đó cá thể vi được tính như sau:

(1.13) vi = xr1 + F × (xr2 – xr3)

trong đó F là một hằng số thuộc đoạn [0,1] và được gọi là hằng số đột biến, cá

thể vi được gọi là cá thể đột biến của cá thể xi. Tham số F được sử dụng để điều

chỉnh độ lớn của vector định hướng và được gọi là độ dài bước nhảy định

hướng.

Bước 2: Tiếp theo, thuật toán DE sử dụng toán tử lai ghép để kết hợp thông

tin giữa cá thể cha xi và cá thể đột biến vi. Toán tử lai ghép được thực hiện bằng

cách chọn một số ngẫu nhiên CR  [0,1] làm xác suất lai ghép và các thành

(1.14)

𝑢𝑖,𝑗 = {

𝑣𝑖,𝑗 𝑛ế𝑢 𝑟𝑎𝑛𝑑𝑖,𝑗 ≤ 𝐶𝑅 ℎ𝑜ặ𝑐 𝑖 = 𝐼𝑟𝑎𝑛𝑑 𝑥𝑖,𝑗 𝑛ế𝑢 𝑟𝑎𝑛𝑑𝑖,𝑗 > 𝐶𝑅 ℎ𝑜ặ𝑐 𝑖 ≠ 𝐼𝑟𝑎𝑛𝑑

phần của cá thể sau lai ghép ui được tính như sau:

với i=1,2,…,N; j=1,2,..,D, trong đó:

randi,j là một số ngẫu nhiên trong đoạn [0,1],

Irand là số ngẫu nhiên trong đoạn [1,D], giá trị Irand đảm bảo vector xi luôn

luôn khác vector vi.

Bước 3: Sau cùng, phép chọn theo công thức (1.15) được áp dụng trên cá

(1.15)

𝑥𝑖(𝑡 + 1) = {

𝑢𝑖(𝑡) 𝑛ế𝑢 𝑓(𝑢𝑖(𝑡)) < 𝑓(𝑥𝑖(𝑡)) 𝑥𝑖(𝑡) 𝑛ế𝑢 𝑛𝑔ượ𝑐 𝑙ạ𝑖

thể cha xi và cá thể ui để chọn ra cá thể cho thế hệ tiếp theo.

Chi tiết thuật toán DE được trình bày như trong Algorithm 1.2 dưới đây.

Algorithm 1.2. DE

Input: N :kích thước quần thể, CR : xác suất lai ghép

Output: phương án tối ưu

for (int i = 0; i< N; i++)

xr1  xr2  xr3  xi = rand(1,N) vi(t) = xr1 + F (xr2- xr3) Irand = randi(1,D) for(j=0; j < D;j++) if (i = Irand OR rand(0,1) <= CR) ui,j= vi,j else ui,j= xi,j end if end for if(f(ui(t)) f(xi(t))) xi(t+1) = ui(t)

else

xi(t+1) = xi(t)

end if

end for gbest = fbest(P)

1. Begin 2. t = 0 3. P = initialize(N) 4. gbest = fbest(P) 5. while(t < tmax) 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. 19. 20. 21. 22. 23. 24. t = t+1 25. end while 26. return gbest 27. End Trong đó: f: hàm mục tiêu fbest: hàm tìm cá thể tốt nhất trong quần thể

Điểm khác biệt cơ bản của thuật toán DE với các thuật toán tiến hóa khác

là ở toán tử đột biến. R. Storn và K. Price[26] đã đề xuất nhiều chiến lược lược

đột biến khác nhau và tạo ra các phiên bản DE khác nhau. Sau đây là một số

- rand/1

vi = xr1 + F(xr2 – xr3)

- best/1

vi = xbest + F(xr1 – xr2)

- current to best /1

vi = xi + K(xbest – xi)+F(xr1 – xr2)

- best/2

vi = xbest + K(xr2 – xr3) + F(xr3 – xr4)

- rand/2

vi = xr1 + K(xr2 – xr3) + F(xr4 – xr5)

- current/2

vi = xi + K(xr3 – xi) + F(x1 – xr2)

- phương pháp bánh xe quay vòng dựa trên hạng cá thể [CT1]

phiên bản khác của DE:

trong đó F và K là các bước nhảy định hướng, xr1, xr2, xr3, xr4, xr5 là các cá thể

được chọn một cách ngẫu nhiên từ quần thể, xbest là cá thể tốt nhất trong quần

thể.

1.2.4. Thuật toán Cuckoo Search

1.2.4.1. Khái niệm bước dịch chuyển ngẫu nhiên

Thuật ngữ “random walk” được đưa ra lần đầu bởi Karl Pearson[27] vào

năm 1905. Bước dịch chuyển ngẫu nhiên, đôi khi còn gọi là bước đi ngẫu nhiên

hay quá trình ngẫu nhiên (Random walk)[30], được thể hiện bởi một chuỗi

những biến đổi không xác định trước, chẳng hạn như chuỗi biến đổi của các dữ

liệu tài chính như giá cổ phiếu chứng khoán, tỷ giá ngoại tệ, các dữ liệu y khoa

như huyết áp, các bước di chuyển để kiếm mồi của động vật... Năm 2020, hai

nhà khoa học Hillel Furstenberg (Mỹ) và Gregory Margulis (Nga) đã được trao

giải thưởng Abel - được đánh giá như giải Nobel toán học- cho một nghiên cứu

về bước dịch chuyển ngẫu nhiên.

Về mặt toán học, bước dịch chuyển ngẫu nhiên được đặc trưng bởi một biến

mô tả một quá trình biến đổi ngẫu nhiên trong miền giá trị nào đó. Một cách

tổng quát, random walk là một quá trình ngẫu nhiên bao gồm một chuỗi biến

đổi liên tiếp và được thể hiện như công thức 1.16 dưới đây.

𝑁 𝑖=1

(1.16) 𝑆𝑁 = ∑ 𝑋𝑖 = 𝑆𝑁−1 + 𝑋𝑁

trong đó bước dịch chuyển thứ i, Xi, có độ lớn và hướng tuân theo một phân

phối xác suất nào đó. Trạng thái hiện tại (SN) phụ thuộc vào trạng thái trước đó

(SN-1) và bước dịch chuyển XN.

Hình 1.8 là ví dụ đơn giản nhất về 5 lần dịch chuyển ngẫu nhiên trong tập

các số nguyên Z, trong đó độ lớn của mỗi bước theo 2 trục tọa độ là 1 hoặc 0.

Hình 1.8. Năm lần dịch chuyển ngẫu nhiên trong tập số nguyên Z2

Một ví dụ nổi tiếng hơn về bước dịch chuyển ngẫu nhiên là chuyển động

Brown[63]. Khi thả một hạt phấn hoa xuống nước, dùng kính hiển vi quan sát

ta thấy hạt phấn hoa chuyển động hỗn loạn không ngừng. Chuyển động đó của

các hạt rất nhỏ (cỡ micromet) trong chất lỏng hay chất khí được gọi là chuyển

động Brown, gây ra bởi sự va chạm với các phân tử nước hay không khí chuyển

động, động năng của các phân tử này được cung cấp bởi nhiệt độ môi trường.

Hình 1.9 [63] là mô phỏng quỹ đạo chuyển động Brown của 5 hạt phấn hoa

(hình vuông) được thúc đẩy bởi các va chạm với 800 phần tử chuyển động

khác. Vector chuyển động của một trong năm hạt phấn hoa được biểu thị bằng

mũi tên. Hình 1.9 cũng gợi ý cho một thuật toán tiến hóa nhằm tìm kiếm lời

giải gần đúng bằng cách sử dụng quần thể gồm nhiều cá thể (trong trường hợp

này là 5).

Hình 1.9. Chuyển động Brown của 5 hạt phấn hoa

Hình 1.10[63] mô tả quỹ đạo chuyển động của 3 hạt keo kích thước 0,53

µm trong môi trường nước được quan sát dưới kính hiển vi. Các vị trí liên tiếp

sau mỗi 30 giây được nối bằng các đoạn thẳng, kích thước mỗi mắt lưới là 3,2

µm.

Hình 1.10. Chuyển động Brown của 3 hạt keo

Về mặt toán học, chuyển động Brown được biểu diễn bởi quá trình Wiener

(X0, X1, X2,...) một quá trình ngẫu nhiên liên tục được đặt tên theo Norbert

Wiener và được sử dụng nhiều trong vật lý, toán học và kinh tế, trong đó:

 X0 = 0;

 Xt là một biến ngẫu nhiên liên tục theo thời gian, chẳng hạn như tọa độ

của hạt phấn hoa hay giá trị cổ phiếu (khác với những biến ngẫu nhiên

rời rạc như trong ví dụ gieo xúc sắc hay bắn bia);

 Xj - Xi  (0, j-i) trong đó N(,2) là phân phối chuẩn (còn gọi là phân

phối Gauss) với kỳ vọng  và phương sai 2.

Bước dịch chuyển ngẫu nhiên có nhiều loại phụ thuộc vào phân phối xác

suất nào sẽ chi phối độ lớn của các bước dịch chuyển. Ứng dụng của mỗi loại

khác nhau, không gian dịch chuyển có thể chỉ là tập số nguyên (Z) hay số thực

(R), không gian hình học 2 hay 3 chiều, các bề mặt cong trong không gian N

chiều.

Bước dịch chuyển ngẫu nhiên có nhiều ứng dụng thực tế. Trong lĩnh vực

tài chính, chuyển động Brown thường được dùng để mô phỏng sự dao động

phức tạp của những đại lượng trên thị trường chứng khoán như giá cổ phiếu,

quyết định đặt lệnh niêm yết, gọi vốn, mua, bán cổ phiếu.

Trong lĩnh vực sinh thái học, tâm lý học, khoa học máy tính, vật lý, hóa

học, sinh học, kinh tế học và xã hội học, bước dịch chuyển ngẫu nhiên được sử

dụng để mô hình hóa nhiều quá trình trong các lĩnh vực này và đóng vai trò như

một mô hình cơ bản cho các hoạt động mang tính không xác định. Trong toán

học, giá trị của π có thể được tính gần đúng bằng cách sử dụng bước dịch

chuyển ngẫu nhiên. Trong phạm vi luận án này, mục tiêu đặt ra là tìm các lời

giải gần đúng trong một không gian tìm kiếm rộng thì bước dịch chuyển ngẫu

nhiên chính là công cụ phù hợp để vừa lục soát kỹ vùng lân cận xung quanh vị

trí hiện thời (thao tác Exploitation) vừa thực hiện những bước nhảy vọt xa để

khám phá những khu vực mới (thao tác Exploration).

Một bước dịch chuyển ngẫu nhiên điển hình đồng thời cũng là cơ sở toán

học của thuật toán Cuckoo Search là bước dịch chuyển Lévy Flight.

1.2.4.2. Bước dịch chuyển Lévy Flight

Được đặt tên theo nhà toán học Pháp Paul Lévy, Lévy Flight là bước dịch

chuyển ngẫu nhiên trong đó độ lớn của bước dịch chuyển biến đổi theo phân

phối xác suất Lévy, hướng dịch chuyển là bình đẳng giữa các chiều của không

gian dịch chuyển (từ nay gọi là “không gian tìm kiếm” hay “không gian lời

giải” cho phù hợp với vấn đề đặt ra trong luận án).

Phân phối xác suất Lévy là phân phối xác suất liên tục của một biến ngẫu

nhiên không âm. Hàm mật độ xác suất của phân phối Lévy trong miền giá trị

−

𝑐 2(𝑥−𝜇)

𝑐

𝑒

(1.17)

𝑓(𝑥, 𝜇, 𝑐) = √

(𝑥−𝜇)3/2

2𝜋 Có thể nhận thấy:

𝑐

(1.18)

𝑓(𝑥, 𝜇, 𝑐)~√

2𝜋

𝑥3/2 𝑘ℎ𝑖 𝑥 → ∞

x  [, +) là:

Hàm mật độ này được thể hiện như trong hình 1.11.

Hình 1.11. Đồ thị hàm mật độ xác suất của phân phối Lévy

Hình 1.12 mô phỏng 1000 bước dịch chuyển Lévy flight trong không gian

hai chiều với tọa độ xuất phát là [0,0], hướng dịch chuyển được phân bố đều,

độ lớn các bước tuân theo phân phối Lévy.

Bước dịch chuyển ngẫu nhiên Lévy Flight đã được các nhà khoa học xác

nhận là phù hợp để mô tả quỹ đạo di chuyển của các động vật (chim, thú) khi

đi kiếm mồi. Vì thế trong thuật toán Cuckoo Search, Lévy Flight được sử dụng

để biến đổi các phương án (tức là các cá thể) từ vòng đời trước sang vòng đời

sau.

Trong hình 1.12, lưu ý rằng khi được cài đặt với những tham số phù hợp,

Lévy flight thực hiện thao tác Exploration tốt hơn nhờ có những bước nhảy tầm

xa, ngược lại chuyển động Brown thực hiện thao tác Exploitation kỹ càng hơn

để lục soát trong phạm vi lân cận.

Hình 1.12. 1000 bước dịch chuyển Lévy flight và chuyển động Brown

1.2.4.3. Thuật toán

Thuật toán Cuckoo Search(CS) [60],[61] được Yang và Deb đưa ra vào

năm 2009, đến nay CS đã được nhiều nhà khoa học nghiên cứu và áp dụng cho

các bài toán tối ưu khác nhau, trong đó có bài toán MS-RCPSP [CT5]. Thuật

toán này được phát triển dựa trên đặc tính sinh hoạt của loài chim Cuckoo và

hành vi bay của một số loài chim và ruồi giấm - gọi là Lévy flight. CS được

xây dựng dựa trên ba quy luật như sau:

- Mỗi lần, một con chim Cuckoo chỉ đẻ một quả trứng vào một tổ được chọn

ngẫu nhiên;

- Tổ tốt nhất với trứng chất lượng cao nhất sẽ được chuyển qua các thế hệ

tiếp theo;

- Số lượng tổ là không đổi và trứng bị chim chủ phát hiện với xác suất

pa ∈ [0, 1], khi đó chim chủ có thể vứt bỏ quả trứng hoặc bỏ cả tổ và xây

dựng một cái tổ hoàn toàn mới.

CS phù hợp với các bài toán tối ưu tính toán trên dữ liệu lớn bằng cách tạo

ra sự cân bằng trong các kỹ thuật tìm kiếm nghiệm toàn cục và tìm kiếm cục

bộ nhằm tạo ra các nghiệm tốt hơn ở thế hệ tiếp theo.

CS dạng đơn giản quy định tổ cũng đồng nghĩa với trứng. Mục tiêu của

thuật toán là sinh ra những tổ mới có tiềm năng tốt hơn thay thế các tổ (nghiệm)

có chất lượng kém. Việc tạo ra tổ mới áp dụng kỹ thuật Lévy Flight với các

phép Tìm kiếm toàn cục (Global Search) và Tìm kiếm cục bộ (Local Search).

Hai kỹ thuật tìm kiếm trên giúp CS mở rộng được không gian tìm kiếm, thoát

khỏi được cực trị địa phương.

Thế hệ tiếp theo tạo ra bằng phép tìm kiếm cục bộ, áp dụng công thức

t+1

t + αs

H(pa-e)

(1.19)

= xi

(xj

- xk

(1.19):

trong đó:

- xi: lịch biểu (các thể) ở thế hệ thứ i;

- t: vị trí của tác vụ trong một phương án (lịch biểu, cá thể);

- xk

t) là độ chênh 2 phương án;

j, k: là hai cá thể bất kỳ, khi đó (xj

- H(x): hàm bước = 0 (khi x<0) hoặc 1 (khi x>0);

- α: là hằng số, nhận giá trị {1, 0.1, 0.01};

- s: stepsize – bước di chuyển ngẫu nhiên  [0,1].

Thế hệ tiếp theo tạo ra bằng phép tìm kiếm toàn cục, áp dụng công thức

t+1

t + α L(s,λ)

(1.20)

= xi

𝜆 𝛤(𝜆)𝑠𝑖𝑛(𝜋𝜆/2)

(1.21)

𝜋

𝑠1+𝜆 , 𝑠 >> 𝑠0 > 0

xi với: 𝐿(𝑠, 𝜆) =

(1.20).

trong đó:

- λ: là một hằng số, 0 < λ ≤ 2

- Γ(λ): là hàm trả lại giá trị (λ-1)!

Chi tiết thuật toán CS được trình bày trong Algorithm 1.3.

Algorithm 1.3. Thuật toán CS

Input : dataset

tmax : số thế hệ tiến hóa

Output : cá thể tốt nhất và makespan

Pnew = {Tạo cá thể mới bằng Lévy Flight (1.20)}

Pi = {Lấy ngẫu nhiên một cá thể từ Pall } if f(Pnew) < f(Pi) { Pi = Pnew } Ppa = pa% tổ kém nhất từ Pall For j = 1 to size(Ppa)

Pnew = {Tạo cá thể mới bằng Lévy Flight (1.19)}

if f(Pnew) < f(Pjpa) { Pjpa = Pnew } End For

1. Begin 2. Load and Valid dataset 3. t = 0 4. Pall = {Initial population} 5. f = {Calculate the fitness, makespan, bestnest} 6. while(t

makespan = f(bestnest) t = t+1 End while

16. Pall = {Thay thế Ppa vào Pall} 17. f = {Calculate the fitness, bestnest} 18. 19. 20. 21. return {bestnest, makespan} 22. End Với:

- f: hàm tính makespan của một lịch biểu

Thuật toán CS thực hiện bằng cách tiến hóa quần thể qua nhiều thế hệ khác nhau.

Ở mỗi thế hệ, CS thực hiện tạo một cá thể mới bằng kỹ thuật tìm kiếm toàn cục

(Global Search). Sau khi tính toán, tiến hóa, thuật toán sẽ thay thế một số cá thể kém

nhất bằng các cá thể mới, các cá thể mới tạo ra bằng kỹ thuật tìm kiếm cục bộ (Local

Search). Kết quả của thuật toán là một cá thể (lịch biểu) với thời gian thực hiện tối

thiểu.

Kết luận chương 1

Bài toán MS-RCPSP là bài toán thuộc lớp NP-Khó và có nhiều ứng dụng

trong thực tế. Tuy nhiên, do không gian lời giải rất lớn, nên khó tìm ra được

nghiệm tối ưu. Do vậy, người ta thường dùng các thuật toán tiến hóa để tìm ra

các nghiệm tốt, chấp nhận được cho các bộ dữ liệu theo yêu cầu cụ thể.

Chương 1 của luận án đã trình bày phát biểu toán học của bài toán MS-

RCPSP, các ứng dụng trong thực tế của bài toán này. Để phục vụ cho việc giải

bài toán này trong Chương 2, chương này cũng giới thiệu một số thuật toán

metaheuristic hiệu quả, thường được áp dụng để tìm ra nghiệm gần đúng trong

thời gian chấp nhận được như PSO, DE, CS.

Kết quả nghiên cứu của chương này được công bố tại:

- Tạp chí HNUE Journal of Science, Vol. 62, No. 3, pp. 88-96, 2017 [CT1];

- Tạp chí Nghiên cứu khoa học và công nghệ quân sự, Tin học, điều khiển và

ứng dụng, Viện KHCNQS/11-2018, số đặc san, pp. 63-73, 2018 [CT3];

- Hội thảo Quốc gia: Ứng dụng công nghệ cao vào thực tiễn, 2019 [CT4].

CHƯƠNG 2

GIẢI BÀI TOÁN MS-RCPSP BẰNG PHƯƠNG PHÁP TỐI ƯU BẦY

ĐÀN VÀ PHƯƠNG PHÁP TIẾN HÓA VI PHÂN

Bài toán lập lịch thực hiện dự án với tài nguyên giới hạn và đa kỹ năng

(MS-RCPSP) [31],[42],[43] có nhiều ứng dụng trong thực tế do bổ sung thêm

yếu tố kỹ năng của tài nguyên thực hiện tác vụ. Theo đó, mỗi tài nguyên có thể

có nhiều loại kỹ năng, mỗi loại kỹ năng có một mức độ kỹ năng cụ thể. Trong

môi trường sản xuất, có thể hiểu kỹ năng chính là chuyên môn của nhân công

và chuyên môn sẽ được phân làm các mức độ (tay nghề) khác nhau. Để thực

hiện một tác vụ, tài nguyên cần đáp ứng về loại kỹ năng và mức kỹ năng phù

hợp với yêu cầu của tác vụ.

Chương 2 nghiên cứu sinh đề xuất một số giải thuật metaheuristic để giải

bài toán MS-RCPSP. Các nội dung chính của chương này gồm:

Phần 2.1: Trình bày phương pháp biểu diễn cá thể của bài toán MS-RCPSP.

Phần 2.2: Trình bày thang đo độ chênh giữa các cá thể, phục vụ trong việc

tính toán, lai ghép cá thể trong quá trình tiến hóa.

Phần 2.3: Trình bày thuật toán đề xuất M-PSO đề giải bài toán MS-RCPSP.

Thuật toán này được xây dựng trên cơ sở của thuật toán tối ưu bầy đàn PSO

với việc bổ sung kỹ thuật di cư nhằm thoát khỏi cực trị địa phương và mở rộng

khả năng tìm kiếm được các nghiệm tốt hơn.

Phần 2.4: Trình bày thuật toán đề xuất DEM đề giải bài toán MS-RCPSP.

Đây là thuật toán được xây dựng trên cơ sở của thuật toán tiến hóa vi phân với

cải tiến mới bằng việc bổ sung hàm tái thiết lập tài nguyên thực hiện tác vụ.

Với mỗi thuật toán, tác giả sẽ trình bày các thực nghiệm cụ thể trên bộ dữ

liệu iMOPSE - bộ dữ liệu chuẩn cho bài toán MS-RCPSP. Sau đó đưa ra các

phân tích, đánh giá cụ thể từ kết quả thực nghiệm.

2.1. Phương pháp biểu diễn cá thể

Trong giải thuật lập lịch, một lịch biểu được thể hiện như một vector có

chiều dài bằng số tác vụ cần thực hiện, mỗi phần tử của vector sẽ lưu giá trị là

chỉ số của tài nguyên thực hiện tác vụ đó.

Với bài toán MS-RCPSP, một cá thể hay một lịch biểu là một vector có số

phần tử bằng số tác vụ của dữ liệu đầu vào, giá trị mỗi phần tử của vector lịch

biểu là chỉ số của tài nguyên sử dụng để thực hiện tác vụ đó. Tài nguyên này

cần đáp ứng các yêu cầu ràng buộc theo điều kiện của bài toán, tức là có loại

kỹ năng giống với kỹ năng yêu cầu và mức kỹ năng (level) phải lớn hơn hoặc

bằng mức kỹ năng yêu cầu.

Ví dụ 2.1: Xét một dự án gồm 10 tác vụ, 2 tài nguyên thực hiện.

- Tập hợp tác vụ W={W1, W2, W3, W4, W5, W6, W7, W8, W9, W10}

- Tập hợp tài nguyên L = {L1, L2}.

W10

Đồ thị ưu tiên của các tác vụ thể hiện như trong hình 2.1 dưới đây.

Hình 2.1. Đồ thị ưu tiên các tác vụ trong dự án

Thời gian thực hiện từng tác vụ (tính theo giờ) được thể hiện trong bảng 2.1.

Bảng 2.1: Thời gian thực hiện các tác vụ

Tác vụ W1 W2 W3 W4 W5 W6 W7 W8 W9 W10 2 Thời gian 3 4 3 2 4 2 5 5 2

Hình 2.2 biểu diễn việc bố trí tài nguyên thực hiện các dự án theo thời gian.

Việc bố trí tài nguyên thực hiện tác vụ cần đáp ứng được thứ tự ưu tiên của bài

L1 W1

W10

1 2

3 4

7 8

11 12 13 14

16 17

time

toán cũng như đáp ứng yêu cầu về kỹ năng, mức kỹ năng của tài nguyên.

Hình 2.2. Tài nguyên thực hiện tác vụ theo thời gian

Với phương án lịch biểu được thể hiện trong hình 2.2, ta có thể biểu diễn

Tác vụ Tài nguyên

W1 W2 W3 W4 W5 W6 W7 W8 W9 W10 1 1

lịch biểu này dưới dạng một vector như sau:

Như vậy, tài nguyên L1 sẽ thực hiện các tác vụ: W1, W4, W5, W6, W7, W10;

tài nguyên L2 thực hiện các tác vụ: W2, W3, W8, W9.

2.2. Thang đo độ chênh của cá thể

Với bài toán MS-RCPSP, một tác vụ có thể được thực hiện bởi nhiều tài

nguyên khác nhau. Để phục vụ cho việc tính toán và hiệu chỉnh cá thể, chúng

ta định nghĩa một thang đo cas the như sau.

Các ký hiệu sử dụng trong thang đo độ chênh:

• p: thang đo độ chênh, pi: vector thang độ chênh của tác vụ i. pi,j: giá trị của

phần tử thứ j trên thang đo của tác vụ i;

• pS: thang đo của cá thể S;

• Si: chỉ số tài nguyên thực hiện tác vụ i trong cá thể S;

• ∆: khoảng cách giữa các phần tử trong thang đo, mỗi phần tử trong thang đo

thể hiện chỉ số của một tài nguyên thực hiện tác vụ ∆i: khoảng cách giữa các

tài nguyên trong thang đo của tác vụ i;

• d: vector độ chênh giữa 02 cá thể, có số phần tử bằng số tác vụ của cá thể.

Định nghĩa 2.1: thang đo cho một tác vụ là một vector thể hiện chỉ số của

các tài nguyên có thể thực hiện được tác vụ đó. Thang đo ký hiệu là p.

Ví dụ 2.2: cho bộ dữ liệu của bài toán MS-RCPSP với 10 tác vụ, 3 tài

nguyên và khả năng thực hiện của các tài nguyên như sau:

- L1 = {W1, W2, W3, W5, W7, W9, W10 }

- L2 = {W2, W3, W5, W6, W8, W10}

- L3 = { W1, W3, W4, W6, W7 }

Khi đó, thang đo có thể được biểu diễn như bảng 2.2 dưới đây.

Thang đo này sẽ được sử dụng để hiệu chỉnh cá thể mới tạo ra khi các chỉ

số tài nguyên sau khi tính toán không nằm trong tập tài nguyên thực hiện của

tác vụ.

Bảng 2.2: Thang đo tài nguyên thực hiện tác vụ

Thang đo của tác vụ Chỉ số tài nguyên thứ nhất Chỉ số tài nguyên thứ hai Chỉ số tài nguyên thứ ba

1 3

1 2

1 2 3

1 2

2 3

1 3

1 2 p1 p2 p3 p4 p5 p6 p7 p8 p9 p10

Biểu diễn độ chênh giữa các cá thể

Định nghĩa 2.2: vector d gọi là vector độ chênh giữa 2 cá thể có số phần tử

bằng số tác vụ của cá thể, giá trị của mỗi phần tử được tính theo công thức 2.1.

di = mod(abs(pi,j - pi,k),100)

(2.1)

trong đó:

i: tác vụ i; -

- j: vị trí của tài nguyên thực hiện tác vụ i của cá thể 2 trên vector thang

đo pi;

- k: vị trí của tài nguyên thực hiện tác vụ i của cá thể 1 trên vector thang

đo pi.

Tính độ chênh giữa hai cá thể dựa trên thang đo

Trong bài toán MS-RCPSP, mỗi tác vụ có thời gian thực hiện cố định,

không phân biệt tài nguyên thực hiện. Do vậy, khoảng giữa các phần tử của

thang đo được tính như công thức 2.2 dưới đây.

(2.2) ∆ = 100/(k-1) với k > 1

k: số tài nguyên có thể thực hiện tác vụ. Trường hợp chỉ có 1 tài nguyên

(k=1) thì ∆=100.

Khi đó, giá trị của mỗi phần tử trong thang đo được tính như công thức

(2.3)

(2.3) pi,j = ∆* (j-1)

j: là vị trí của phần tử trên thang đo của tác vụ i.

Ví dụ 2.3: tác vụ W1 có 6 tài nguyên có thể thực hiện được, lần lượt là: L1,

L3, L4, L5, L9, L10.

W1 L1 L3 L4 L5 L9 L10

L9 L10

20 p1:0 20 40 60 80 100

Thang đo được biểu diễn như trong hình 2.3.

Hình 2.3. Biểu diễn giá trị trên thang đo

Phép trừ 02 cá thể - tính độ chênh

Phép trừ 02 cá thể tạo ra vector độ chênh được tính theo công thức 2.1.

Ví dụ 2.4: Có 2 tác vụ W1 và W2. Tài nguyên có thể thực hiện từng tác vụ được biểu

diễn trong bảng 2.3.

L10

Bảng 2.3: Tài nguyên có thể thực hiện tác vụ

Số tài nguyên thực hiện được W1 là 6, số tài nguyên thực hiện được W2 là

5. Khi đó:

- với tác vụ W1: ∆1 = 100/5 = 20

- với tác vụ W2: ∆2 = 100/4 = 25

Thang đo khoảng cách như trong bảng 2.4 dưới đây.

Bảng 2.4: Giá trị vector thang đo

0 20 40 60 80 100

0 25 50 75 100 p1 p2

xét 2 cá thể S1, S2 có tài nguyên thực hiện từng tác vụ được biểu diễn như

trong bảng 2.5.

Cá thể | Task

Bảng 2.5: Tài nguyên thực hiện tác vụ của cá thể S1, S2 W1 L3 L5 W2 L8 L10 S1 S2

Vector độ chênh d được tính như sau:

d1 =mod(abs(p2,8 – p1,3)) = mod(abs(75-20)) = 55

d2 = mod(abs(p2,10 – p1,5)) = mod(abs(100-60)) = 40

Kết quả thu được vector độ chênh d có giá trị được biểu diễn trong bảng

2.6.

Bảng 2.6: Giá trị của vector độ chênh d

W2 40 W1 55 Task d

Tính độ chênh giữa 2 cá thể được trình bày trong Algorithm 2.1.

Algorithm 2.1. Tính độ chênh giữa 2 cá thể

d = {} p = thang đo for i=1 to taskcount

j = vị trí tài nguyên thực hiện task i của S1 k = vị trí tài nguyên thực hiện task i của S2 di = mod(abs(pi,j - pi,k),100)

end for return d;

Input: - S1,S2: 2 cá thể đầu vào - taskcount: số lượng tác vụ Output: vector độ chênh Begin 1 2 3 4 5 6 7 8 9 10 End

Phép cộng 02 cá thể - tạo cá thể mới

Phép cộng 02 cá thể tạo ra một cá thể mới, được thực hiện qua các bước

như sau:

- Tính độ chênh giữa 02 cá thể

- Cộng thang đo của cá thể 1 với độ chênh

- Cá thể mới nhận được bằng việc tham chiếu kết quả vào thang đo để

tìm tài nguyên thực hiện, được thực hiện theo công thức 2.4

(2.4) Si = index (round(mod((di + pi,j),100)) )

Trong đó:

i: chỉ số của tác vụ -

- j: vị trí tài nguyên thực hiện tác vụ trong thang đo

- index: trả về chỉ số tài nguyên ở vị trí tương ứng trên thang đo

Trong ví dụ 2.4 ở trên, xét S = S1 + S2, ta có:

S1 = index (round(mod(d1 + p1,3))) = index(round(75)) = 9

S2 = index (round(mod(d2 + p2,8))) = index(round(115)) = 6

Như vậy, ta được phương án mới S với W1 được thực hiện bởi L9, W2 được

thực hiện bởi tài nguyên L6. Chi tiết được thể hiện trong bảng 2.7.

Bảng 2.7: Kết quả cộng hai cá thể

W2 40 75 115 6 W1 55 20 75 9 Task d p S1 + p S

Phép cộng 2 cá thể được trình bày trong Algorithm 2.2.

Algorithm 2.2. Cộng 2 cá thể để tạo cá thể mới

S = {} p = thang đo d = độ chênh giữa S1 và S2 for i=1 to taskcount

Si = index (round(mod((di + p1,i),100)) )

end for return S;

Input: - S1,S2: hai cá thể đầu vào - taskcount: số lượng tác vụ Output: cá thể mới Begin End

1 2 3 4 5 6 7 8 9

2.3. Đề xuất thuật toán M-PSO

Thuật toán tối ưu bầy đàn PSO là thuật toán tiến hóa trong đó mỗi cá thể

được tạo ra dựa trên thừa kế kinh nghiệm của cả quần thể và của chính cá thể

đó, do vậy nâng cao được khả năng hội tụ, nhanh tìm ra được nghiệm tốt.

Là thuật toán có tốc độ hội tụ nhanh nên PSO được giới nghiên cứu quan

tâm và đề xuất nhiều phiên bản cải tiến, trong đó một phương pháp thông dụng

là Tìm kiếm lân cận Local search PSO [CT2], [CT6]. Tuy nhiên phương pháp

Tìm kiếm lân cận đôi lúc khiến chương trình mắc kẹt tại bẫy cực trị địa phương.

Mục tiếp theo sẽ đề xuất một phương pháp hiệu quả khác, phương pháp Di cư,

cho phép thuật toán thoát khỏi vùng cực trị địa phương để tìm tới những vùng

nghiệm mới có thể có các nghiệm tốt hơn.

Thuật toán M-PSO (Migration PSO) là thuật toán áp dụng cho bài toán MS-

RCPSP nhằm cực tiểu hóa makespan, thuật toán được xây dựng dựa trên thuật

toán tối ưu bầy đàn PSO và được cải tiến ở các điểm sau:

(i) Tìm và phát hiện cực trị địa phương;

(ii) Áp dụng kỹ thuật di cư (Migration) để thoát khỏi cực trị địa phương.

2.3.1. Kỹ thuật Di cư

Khi thực hiện tiến hóa, thuật toán PSO có xu hướng rơi vào các vùng cực

trị địa phương nghĩa là sau nhiều thế hệ quần thể vẫn bị hút vào khu vực xung

quanh một cực trị địa phương. Để hướng dẫn quần thể đi tới giá trị tối ưu, cần

phải đưa chúng thoát ra khỏi vùng lân cận xung quanh cực trị địa phương để

chuyển tới một vùng không gian nghiệm khác, đó là mục đích của kỹ thuật di

cư trong luận án này. Ngoài việc giúp thuật toán thoát khỏi cực trị địa phương,

kỹ thuật di cư còn mở rộng không gian tìm kiếm, nâng cao kết quả của thuật

toán.

Định nghĩa 2.3: Quần thể được gọi là tiến hóa không thành công nếu giá

trị makespan của quần thể không thay đổi qua 2 thế hệ liên tiếp.

2.3.1.1. Ý tưởng của kỹ thuật di cư

Kỹ thuật Di cư áp dụng trong thuật toán M-PSO được thực hiện qua các

bước sau:

Bước 1: Tìm và phát hiện cực trị địa phương

Để phát hiện cực trị địa phương, ta dùng một biến nfail để đếm số lần quần

thể tiến hóa không thành công liên tiếp, nếu giá trị này lớn hơn một ngưỡng

quy định (nmax), thì quần thể đã rơi vào cực trị địa phương. Công thức 2.5 trình

bày cách tính nfail.

(2.5) 𝑛𝑓𝑎𝑖𝑙 = { 𝑛𝑓𝑎𝑖𝑙 + 1 𝑖𝑓 𝑛𝑒𝑤𝑚𝑎𝑘𝑒𝑠𝑝𝑎𝑛 = 𝑜𝑙𝑑𝑚𝑎𝑘𝑒𝑠𝑝𝑎𝑛 0 𝑖𝑓 𝑛𝑒𝑤𝑚𝑎𝑘𝑒𝑠𝑝𝑎𝑛 ≠ 𝑜𝑙𝑑𝑚𝑎𝑘𝑒𝑠𝑝𝑎𝑛

Bước 2: Di chuyển quần thể

Việc di chuyển quần thể sang vị trí khác được thực hiện như sau:

- Duyệt từng cá thể của quần thể;

- Với mỗi tác vụ i của cá thể, xem xét tập Li các tài nguyên có thể thực hiện được tác vụ i, sắp xếp các tài nguyên thứ tự tăng dần của chỉ số tài nguyên;

- Lấy tài nguyên ở vị trí đối xứng để thực hiện tác vụ i thay cho tài nguyên

hiện tại.

Hình 2.4 minh họa việc di cư của tác vụ bằng việc thay đổi tài nguyên thực

hiện. Cụ thể, tác vụ đang được thực hiện bởi tài nguyên L2 sẽ được bố trí tài

nguyên thực hiện mới là Lm-1 và tác vụ đang được thực hiện bởi tài nguyên Lm

...

Lm-1

...

Lm-1

sẽ được bố trí tài nguyên mới là L1 để thực hiện.

Hình 2.4. Thay đổi tài nguyên thực hiện tác vụ

Việc dịch chuyển tài nguyên thực hiện tác vụ cần đảm bảo ràng buộc của

bài toán. Sau khi thực hiện với toàn bộ quần thể, ta sẽ được một quần thể mới

được di chuyển bằng kỹ thuật Migration.

Ví dụ 2.2:

Xem xét một dự án với các thông tin như sau:

- Tập tác vụ W ={1, 2, 3, 4, 5, 6, 7, 8, 9, 10};

- Năng lực của các tài nguyên được thể hiện như trong Bảng 2.8.

- Tập tài nguyên L={1, 2, 3, 4};

Bảng 2.8: Năng lực của các tài nguyên

W1 W2 W3 W4 W5 W6 W7 W8 W9 W10 × × × × × ×

× × × × × × × ×

× × × × × × ×

L1 L2 L3 L4 × × × × × × ×

Xem xét một phương án lịch biểu với các thiết lập tài nguyên thực hiện tác

vụ như trong bảng 2.9.

Bảng 2.9: Lịch biểu khả thi của dự án trong ví dụ 2.2

Tác vụ 1 2 3 4 5 6 7 8 9 10

Tài nguyên 1 1 2 1 2 2 4 1 1 4

Xét tác vụ 1, tập tài nguyên thực hiện tác vụ 1, W1 = {L1, L2, L3, L4}

Áp dụng kỹ thuật di cư với tác vụ 1, ta thấy, tài nguyên thực hiện tác vụ 1

hiện tại là L1, dùng kỹ thuật di cư để thiết lập tài nguyên thực hiện tác vụ 1 bằng

cách lấy tài nguyên đối xứng trong tập tài nguyên W1, ta có tài nguyên mới để

thực hiện tác vụ 1 là L4.

Áp dụng tương tự với các tác vụ 2, 3, 4, 5, 6, 7, 8, 9, 10, ta sẽ được cá thể

sau khi di cư với thiết lập tài nguyên thực hiện được thể hiện trong bảng 2.10.

Bảng 2.10: Lịch biểu mới sau khi di cư

Tác vụ 1 2 3 4 5 6 7 8 9 10

Tài nguyên 4 3 4 4 3 2 2 4 4 2

Ta có thể thấy, trong lịch biểu mới, tại vị trí của tác vụ 6, tài nguyên thực

hiện không thay đổi do W6 = {L1,L2,L3}. Điều này hạn chế khả năng tạo ra các

bước di chuyển lớn của cá thể. Tuy nhiên, vấn đề này sẽ ít gặp phải trong bài

toán với số lượng tài nguyên thực hiện lớn hơn.

2.3.1.2. Hàm Migration

Algorithm 2.2. Migration

Input: Pall – quần thể hiện tại

Output: Pnew – quần thể sau khi di chuyển

Begin

1. Pnew = {}

2. For i=1 to size(P) // duyệt lần lượt từng cá thể

3. Pi = Pall[i]; // lấy cá thể thứ i từ quần thể

4. For j = 1 to y // duyệt lần lượt từng task

Wi = Danh sách tài nguyên thực hiện Wi

Wi = Sort(Wi) // sắp xếp chỉ số tài nguyên trong Wi

idx = Chỉ số tài nguyên thực hiện task i

idx = size(Wi) – idx + 1

Li = Wi[idx]

10. End for // j

11. Pnew = Pnew + {Pi}

12. End for // i

13. Return Pnew;

End Function

2.3.2. Thuật toán M-PSO

M-PSO được trình bày trong Algorithm 2.3 với đầu vào của thuật toán là

số thế hệ thực hiện để tìm phương án tốt nhất (tmax) và ngưỡng phát hiện cực trị

địa phương (nmax). Các bước chạy chi tiết như sau:

Algorithm 2.3. M-PSO

Input: nmax: ngưỡng áp áp dụng migration, tmax: số thế hệ

Output phương án tốt nhất gbest

1 Begin

Pall = Load dữ liệu iMOPSE và khởi tạo quần thể ban đầu

t = 0

nfail = 0

5 while ( t < tmax )

6 t = t + 1

7 for i=1 to size(Pall) do

8 tính giá trị hàm mục tiêu f(Pi)

9 end for

10 for i = 1 to size(Pall) do

11 if f(Pi) < f(fitnessi) then

12 pbesti = Pi

13 f(pbesti) = f(Pi)

14 end if

15 end for

16 for i=1 to size(Pall) do

17 if(f(Pi) < f(gbest)) then

18 gbest = Pi

19 f(gbest) = f(Pi)

20 end if

21 if f(Pi)!= f(Pi-1) then

22 nfail = 0

23 else

24 nfail += 1

25 end if

26 end for

27 for i=1 to size(Pall) do

28 cập nhật vector dịch chuyển theo (1.1.a)

29 Cập nhật vector vị trí theo (1.1.b)

30 end for

31 if (nfail = nmax)

32 Pall = Migration(Pall)

33 nfail = 0

34 end if

35 end while

36 return gbest

37 end

f: objective function

Các dòng 21 đến 25 thể hiện biến đếm để phát hiện cực trị địa phương.

Các dòng 31 đến 34 xử lý việc áp dụng kỹ thuật di cư quần thể khi đã phát

hiện ra cực trị địa phương.

2.3.3. Thực nghiệm

2.3.3.1. Dữ liệu thực nghiệm

Để đánh giá, thuật toán đã được cài đặt, chạy thử nghiệm với bộ dữ liệu

iMOPSE [42],[45], đây là bộ dữ liệu chuẩn đã được chứng minh phù hợp với

bài toán MS-RCPSP và đã có nhiều nhóm nghiên cứu sử dụng.

Bộ dữ liệu được lưu trữ dưới dạng file def, mỗi file bao gồm các thông tin:

 Số tác vụ (Task) cần thực hiện;

 Số tài nguyên (Resource) sử dụng để thực hiện các tác vụ;

 Số lương ràng buộc giữa các tác vụ (Precedence Relation), chỉ ra thứ tự ưu

tiên trong việc thực hiện các tác vụ;

 Số lượng kỹ năng của các tài nguyên (Skill);

 Kỹ năng và mức kỹ năng của mỗi tài nguyên, một tài nguyên có thể bao

gồm nhiều kỹ năng.

Chi tiết bộ dữ liệu iMOPSE được trình bày trong bảng 2.11 dưới đây.

Bảng 2.11: Bộ dữ liệu iMOPSE cho bài toán MS-RCPSP

Dataset instance Tasks Resources Skills

100_5_20_15 100_5_48_9 100_5_48_15 100 100 100 Precedence Relations 22 48 46 15 9 15 5 5 5

Dataset instance Tasks Resources Skills

100_5_64_9 100_5_64_15 100_10_26_15 100_10_47_9 100_10_48_15 100_10_64_9 100_10_65_15 100_20_22_15 100_20_47_9 100_20_46_15 100_20_65_9 100_20_65_15 200_10_50_9 200_10_50_15 200_10_84_9 200_10_85_15 200_10_128_15 200_40_144_15 200_20_55_9 200_20_54_15 200_20_97_9 200_20_97_15 200_20_145_15 200_40_45_9 200_40_45_15 200_40_90_9 200_40_91_9 100 100 100 100 100 100 100 100 100 100 100 100 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 Precedence Relations 64 64 26 47 48 64 65 22 47 46 65 65 50 50 84 85 128 133 55 54 97 97 145 45 45 90 91 9 15 15 9 15 9 15 15 9 15 9 15 9 15 9 15 15 15 9 15 9 15 15 9 15 9 15 5 5 10 10 10 10 10 20 20 20 20 20 10 10 10 10 10 40 20 20 20 20 20 40 40 40 40

2.3.3.2. Cấu hình thực nghiệm

Các tham số thực nghiệm:

- Dữ liệu: 30 file dữ liệu trong bộ dữ liệu iMOPSE như trong bảng 2.11;

- Khởi tạo quần thể ban đầu với 100 cá thể;

- Số thế hệ tiến hóa: 100.000;

- Số lần chạy thực nghiệm trên mỗi bộ dữ liệu: 50;

- Hệ số phát hiện cực trị địa phương nmax: 30.

Môi trường thực nghiệm:

- Thực nghiệm được tiến hành trên môi trường Matlab 2014

- Máy tính thực nghiệm: CPU Intel Core i5, tốc độ 2.2 GHz, RAM 6GB,

hệ điều hành Windows 10 (64 bit).

2.3.3.3. Kết quả thực nghiệm

nghiệm của M-PSO được so sánh với:

Kết quả thực nghiệm được thể hiện trong bảng 2.12 dưới đây. Kết quả thực

- Thuật toán GA-M: là thuật toán di truyền cải tiến của nhóm

Myszkowski, thuật toán này được nhóm tác giả công bố cùng với bộ

công cụ GA Runner để chạy và kiểm chứng kết quả, nên kết quả của

GA-M là khách quan và tin cậy [42],[45].

- Một số thuật toán lai (hybrid) như: HAntCO, GRASP[44]. Đây là các

thuật toán tiến hóa được lai ghép tính ưu việt của hai hoặc nhiều thuật

toán hoặc kỹ thuật khác nhau.

Bảng 2.12: Kết quả thực nghiệm M-PSO

GA-M

HAntCO

GRASP

M-PSO

TT

Dataeset

Best Avg

Std

Best Avg

Std

Best Avg

Std

100_5_22_15

517

524

5.3

0.8

505

503

504

0.5

485

486

1.7

504

100_5_46_15

584

587

4.7

604

552

556

2.6

530

531

0.5

604

100_5_48_9

528

535

9.7

1.6

523

510

0.8

490

492

1.6

521

100_5_64_15

527

530

2.5

2.9

523

501

502

0.8

478

479

1.3

516

100_5_64_9

508

521

9.9

3.9

515

494

0.6

471

474

2.5

507

100_10_26_15

292

0.0

2.2

270

251

258

3.2

233

0.4

266

100_10_47_9

296

0.0

302

263

264

0.7

257

261

3.7

297

100_10_48_15

279

282

2.9

4.4

286

256

257

1.2

244

245

0.6

278

100_10_64_9

296

305

6.6

5.1

296

255

257

1.9

240

246

5.9

287

100_10_65_15

286

290

5.0

3.5

287

256

260

1.9

244

245

1.3

281

100_20_22_15

163

169

5.8

3.6

170

134

137

1.6

128

131

3.1

161

100_20_46_15

197

207

6.9

2.6

199

170

174

3.1

162

165

2.9

194

100_20_47_9

185

186

0.5

3.7

187

133

140

2.2

124

128

3.6

180

100_20_65_15

240

0.5

2.7

220

213

228

230

1.8

218

100_20_65_9

181

187

4.5

3.1

185

135

1.4

125

0.3

180

200_10_128_15

577

583

4.9

3.1

528

491

496

4.2

461

464

2.7

522

GA-M

HAntCO

GRASP

M-PSO

TT

Dataeset

Best Avg

Std

Best Avg

Std

Best Avg

Std

200_10_50_15

553

577

17.5

543

524

528

3.8

489

490

0.7

529

200_10_50_9

585

589

5.0

556

4.8

506

508

1.4

487

491

3.7

546

200_10_84_9

567

583

11.4

581

6.9

526

527

0.8

508

510

2.1

571

200_10_85_15

549

555

4.9

538

6.5

496

498

1.1

473

476

2.5

526

200_20_145_15

326

328

2.0

314

4.4

262

271

4.2

236

237

1.4

309

200_20_54_15

363

385

20.8

349

6.6

304

308

3.7

256

0.3

336

200_20_55_9

312

318

4.2

317

3.1

257

258

0.6

251

255

3.5

313

200_20_97_15

424

438

9.7

368

4.8

347

334

337

3.3

356

200_20_97_9

321

326

6.2

332

4.1

253

256

1.6

255

256

0.9

326

200_40_133_15

215

222

6.2

221

3.4

163

170

4.1

147

151

4.1

214

200_40_45_15

201

210

6.3

212

2.6

164

163

167

206

200_40_45_9

209

213

2.9

215

3.8

144

147

1.6

152

162

9.5

209

200_40_90_9

211

215

3.1

214

1.8

148

153

4.5

145

152

7.1

211

200_40_91_15

200

205

3.4

212

2.9

153

159

2.6

135

143

8.3

207

Bảng 2.13: So sánh kết quả thực nghiệm M-PSO với các thuật toán khác

BEST

AVG

Thuật toán

Tỉ lệ (%)

Tổng STD

Số lượng

Từ Đến

Từ

Đến

85.3

M-PSO

30/30

5.0

32.97 30/30

4.3

33.56 173.3

GA-M

29/30

-4.59 34.78 29/30

-4.55 32.55 110.9

HAntCO

27/30

-7.04 15.79 26/30

-10.2 16.88

56.7

GRASP

Trong bảng 2.13:

- Cột “Số lượng” thể hiện số bộ dữ liệu (trên tổng số 30 bộ) mà thuật toán

M-PSO có kết quả tốt hơn thuật toán ở hàng tương ứng.

- Tỉ lệ (%) cho biết kết quả của M-PSO tốt hơn/kém hơn kết quả của các

thuật toán. Giá trị âm thể hiện một vài trường hợp mà M-PSO cho kết

quả kém hơn.

2.3.4. Đánh giá chất lượng lời giải của thuật toán

Luận án đã tiến hành thực nghiệm thuật toán M-PSO áp dụng cho bài toán

MS-RCPSP. Thực nghiệm được chạy trên 30 bộ dữ liệu iMOPSE, với số lần

chạy thực nghiệm là 50 lần, số thế hệ tiến hóa là 100.000, thuật toán được cài

đặt trên môi trường thử nghiệm Matlab 2014. Kết quả thực nghiệm được trình

bày trong bảng 2.12. Kết quả thực nghiệm được tổng hợp và so sánh trong

bảng 2.13.

So sánh với GA-M cải tiến của nhóm Myszkowski, ta thấy:

- Về giá trị BEST và AVG: M-PSO tốt hơn GA-M trong tất cả các trường

hợp, trong đó giá trị BEST tốt hơn GA-M từ 5.0% đến 32.97%, giá trị

AVG tốt hơn GA-M từ 4.3% đến 33.56%.

- Về giá trị độ lệch chuẩn STD, tổng độ lệch chuẩn của GA-M là 173,3,

của M-PSO là 85,3. Từ kết quả này, có thể thấy, thuật toán M-PSO mang

lại hiệu quả cao hơn thuật toán GA-M và tính ổn định của M-PSO cũng

tốt hơn.

So sánh với các thuật toán lai (hybrid) khác

- Bảng 2.13 cho thấy, kết quả của M-PSO có kết quả tốt hơn các thuật

toán lai ở hầu hết các trường hợp, cụ thể: tốt hơn HAntCO 29/30 bộ dữ

liêu, tốt hơn GRASP 27/30 bộ dữ liệu với giá trị BEST, 26/30 bộ dữ liệu

với giá trị AVG. Một số trường hợp M-PSO kém hơn các thuật toán lai,

tuy nhiên, giá trị kém hơn không nhiều. Ví dụ, khi so sánh với thuật toán

GRASP, trường hợp kém nhất của M-PSO so với GRASP là -7.04%,

trong khi đó giá trị tốt nhất cao hơn GRASP là 15.79%.

Như vậy, trong thuật toán mới M-PSO với việc bổ sung phương pháp di cư

quần thể đã mang lại hiệu quả tốt cho thuật toán. Bản chất của việc di cư quần

thể là việc mở rộng không gian tìm kiếm, giúp thuật toán có khả năng quét và

duyệt được nhiều phương án hơn, do vậy có khả năng tìm được nghiệm tốt hơn.

Ngoài ra, phương pháp di cư giúp thuật toán mới dễ dàng thoát khỏi cực trị địa

phương.

2.3.5. Hình ảnh so sánh M-PSO và GA-M

Hình 2.5. So sánh giá trị BEST giữa M-PSO và GA-M

Hình 2.6. So sánh giá trị STD giữa M-PSO và GA-M

2.4. Đề xuất thuật toán DEM

Thuật toán DEM (Reallocate Differential Evolution for MS-RCPSP)

[CT7], [CT8] được xây dựng trên cơ sở là thuật toán DE để giải bài toán MS-

RCPSP. Mục tiêu của thuật toán này là tìm ra được lịch biểu với thời gian thực

hiện ngắn nhất. DEM áp dụng cho MS-RCPSP với cải tiến như sau:

Với cá thể tốt nhất sau mỗi thế hệ, áp dụng phương pháp tìm và thay thế

tài nguyên thực hiện các tác vụ của cá thể. Phương pháp này được gọi là

tái thiết lập tài nguyên thực hiện.

2.4.1. Phương pháp tái thiết lập tài nguyên thực hiện

2.4.1.1. Ý tưởng của phương pháp tái thiết lập

Trong bài toán MS-RCPSP, một lịch biểu là một cá thể biểu diễn tài nguyên

thực hiện tác vụ thỏa mãn các ràng buộc ban đầu. Sau mỗi thế hệ, thuật toán sẽ

tìm ra được lịch biểu tốt nhất (Cbest), dựa trên lịch biểu này, thực hiện tiếp thay

đổi các tài nguyên thực hiện từng tác vụ sao cho vẫn đảm bảo được ràng buộc

của bài toán. Việc thay đổi tài nguyên thực hiện tác vụ được gọi là phương pháp

tái thiết lập (Reallocate). Phương pháp này giúp mở rộng được không gian tìm

kiếm và có thể tránh được cực trị địa phương.

Phương pháp tái thiết lập được thực hiện qua các bước như sau:

- Bước 1: Tìm tài nguyên sử dụng nhiều nhất trong Cbest, gọi là Lb. Đây là tài

nguyên kết thúc công việc sau cùng trong các tài nguyên sử dụng để thực

hiện dự án.

- Bước 2: Duyệt lần lượt từng tác vụ được thực hiện bởi tài nguyên Lb theo

thứ tự ưu tiên thực hiện của các tác vụ trên lịch biểu.

b: tập tác vụ đang được thực hiện bởi Lb

- Bước 3: Với mỗi tác vụ Wi ∈ WRb (i=1- sizeof(WRb)), thực hiện:

• Tìm tất cả các tài nguyên có khả năng thực hiện được tác vụ Wi khác với

tài nguyên hiện tại (Lb), ký hiệu là LW;

W ∈ LW, thực hiện:

• Duyệt lần lượt từng tài nguyên có thể thực hiện tác vụ Wi, với mỗi tài

nguyên Lj

o (1) Thiết lập tài nguyên thực hiện Wi là Rj

o (2) Xóa Wi khỏi danh sách tác vụ mà là Lb đang thực hiện.

Sau (1) và (2) ta sẽ nhận được lịch biểu mới, tính makespan của lịch biểu

mới newbest, nếu tốt hơn makespan của Cbest, thay thế Cbest bằng lịch newbest và

dừng lại, nếu không, tiếp tục thực hiện vòng lặp để kiểm tra.

𝐶𝑏𝑒𝑠𝑡 { 𝑛𝑒𝑤𝑏𝑒𝑠𝑡 𝑖𝑓 𝑓(𝑛𝑒𝑤𝑏𝑒𝑠𝑡) < 𝑓(𝐶𝑏𝑒𝑠𝑡) 𝐶𝑏𝑒𝑠𝑡 𝑖𝑓 𝑓(𝑛𝑒𝑤𝑏𝑒𝑠𝑡) ≥ 𝑓(𝐶𝑏𝑒𝑠𝑡)

Phép dịch chuyển này giúp thuật toán mở rộng không gian tìm kiếm bằng

việc tạo ra các cá thể mới dựa trên cá thể tốt nhất. Do cá thể newbest được tạo ra

từ cá thể tốt nhất nên có khả năng sử dụng được kinh nghiệm của cả quần thể

và của cá thể tốt nhất qua các thế hệ, đây chính là đặc tính của thuật toán DE.

Do vậy, sau khi áp dụng Reallocate, chúng ta có thể nhận được các cá thể tốt

hơn.

2.4.1.2. Sơ đồ thuật toán

Các bước thực hiện của phương pháp tái thiết lập được thể hiện chi tiết

trong sơ đồ thuật toán hình 2.7.

2.4.1.3. Hàm Reallocate

Thuật toán tái thiết lập tài nguyên [CT7], [CT8] thực hiện tác vụ được thể

hiện chi tiết trong Algorithm 2.2 sau đây.

Algorithm 2.2. Reallocate

Input: currentBest (các thể tốt nhất sau mỗi thế hệ)

Output: lịch biểu sau khi được hiệu chỉnh

1. makespan = f(currentBest)

2. newbest = currentBest;

3. Lb = lastResource (newbest) //tài nguyên hoàn thành sau

cùng

4. Wb = {các tác vụ được thực hiện bởi Lb}

5. For i=1 to size(Wb) // duyệt lần lượt từng tác vụ

6. Wi = Wb[i]; // lấy tác vụ thứ i

7. Li = {các tài nguyên thực hiện được Wi # Lb}

8. For j = 1 to size(Li) // duyệt lần lượt từng tài nguyên

Li[j] = Li[j] + {Wi} // chuyển ti sang Li[j]

Lb = Lb – {Wi} // loại Wi khỏi Lb

10.

newmakespan = f(newbest) // tính toán lại makespan

11.

If newmakespan < makespan

12.

makespan = newmakespan

13.

Return newbest; // dịch chuyển thành công, trả

14.

về kết quả và dừng hàm

End if

15.

newbest = currentBest; // dịch chuyển không thành

16.

công, lấy lại lịch biểu ban đầu (trước khi dịch

chuyển) để thực hiện vòng lặp tiếp theo

End for // j

17.

18. End for // i

19. Return newbest;

End Function

Với:

- f: hàm tính makespan của một lịch biểu

- size: hàm tính số phần tử của một tập/mảng

- lastResource: hàm trả về tài nguyên kết thúc thực hiện sau

cùng

Ví dụ 2.3:

Xem xét một dự án với các thông tin như sau:

- Tập tác vụ W ={1, 2, 3, 4, 5, 6, 7, 8, 9, 10}

Bắt đầu

newbest = Cbest; makespan = f(newbest)

Lb = max(newbest); i=0 b = {các task trong Lb}

Sai

i++; i < size(WR

Đúng

Wi ∈ WR b, i=1.. size(WR b); j=0 Lt = {tập tài nguyên thực hiện được Wi } # Lb

j++; j < size(Lt)

j Thêm Wi vào Lt Xóa Wi khỏi Lb

Sai

f(newbest) < makespan

Đúng

Cbest = newbest makespan = f(newbest)

Kết thúc

- Tập tài nguyên L={1, 2, 3}.

Hình 2.7. Sơ đồ khối thực hiện di chuyển tác vụ sang tài nguyên khác

Thời gian thực hiện tác vụ được thể hiện trong bảng 2.14.

Bảng 2.14: Thời gian thực hiện các tác vụ

Tác vụ 1 2 3 4 5 6 7 8 9 10

Thời gian 2 4 3 5 2 2 5 3 4 2

Hình 2.8 thể hiện mối quan hệ giữa các tác vụ. Cụ thể như sau:

- Task 2 thực hiện và hoàn thành trước khi task 6,8 bắt đầu;

- Task 3 thực hiện và hoàn thành trước khi task 7 bắt đầu;

- Task 4 thực hiện và hoàn thành trước khi task 5 bắt đầu;

- Task 8 thực hiện và hoàn thành trước khi task 9 bắt đầu;

- Task 5 thực hiện và hoàn thành trước khi task 10 bắt đầu.

Task 0 và task 11 là 2 tác vụ giả với thời gian thực hiện bằng 0, thể hiện là

W11

W10

thời điểm bắt đầu và kết thúc dự án.

Hình 2.8. Thứ tự ưu tiên của các tác vụ

Năng lực của các tài nguyên được cho như trong bảng 2.15.

Bảng 2.15: Năng lực các tài nguyên

Tác vụ W1 W2 W3 W4 W5 W6 W7 W8 W9 W10 × × × × × × × L1

× × × × × × ×

× × × × × × L2 L3

Giả sử, sau một thế hệ, ta tìm được lịch biểu với tài nguyên thực hiện tác

vụ được thiết lập như trong bảng 2.16.

Bảng 2.16: Tài nguyên thực hiện tác vụ

Tác vụ 1 2 3 4 5 6 7 8 9 10

Tài nguyên 1 1 2 1 2 2 3 2 1 1

Ta có thể thấy, biểu đồ Gantt của lịch biểu 2.15 như trong hình 2.9 dưới

L1 L2 L3

W5 W6 W7

đây. Makespan của lịch biểu 2.15 là: 17

W10 Time 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

Hình 2.9. Biểu đồ Gantt của lịch biểu 2.15

Áp dụng hàm Reallocate, ta thiết lập tài nguyên thực hiện tác vụ W9 là L2,

lịch biểu mới được biểu diễn như trong hình 2.10. Lịch biểu mới có makespan

W10

L1 L2 L3

W5 W6 W7

là 16, tốt hơn so với kết quả trước.

Time 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

Hình 2.10. Biểu đồ Gantt của lịch biểu mới

Cụ thể các việc tái thiết lập tài nguyên thực hiện tác vụ được thể hiện trong

Resources

Before Reallocate

After Reallocate

Time

hình 2.11 dưới đây.

Hình 2.11. Minh họa phương pháp tái thiết lập tài nguyên

2.4.2. Thuật toán

Các cải tiến của DEM được trình bày trong Algorithm 2.6 dưới đây.

Algorithm 2.6. Thuật toán DEM

Input : tmax - số thế hệ tối đa, dataset

Output : cá thể tốt nhất và thời gian thực hiện dự án

for (int i = 0; i< Size; i++)

P1  P2  P3  Pi = Lấy ngẫu nhiên cá thể từ Pall F = rand(0,1) Vi = P1 + F (P2 - P3) // parameter of the mutation operator for(j=0; j

end if

end for {Pbest, makespan} = fbest(Pall) Pbest = Reallocate(Pbest) {Pbest, makespan} = fbest(Pall)

1. Begin 2. Load and Valid iMOPSE dataset 3. t = 0 4. Pall = Initial population 5. {Pbest, makespan} = fbest(Pall) 6. while( t< tmax) 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. 19. 20. 21. 22. 23. 24. 25. 26. t = t+1 27. end while 28. return {Pbest, makespan} 29. End

Trong đó: f: hàm mục tiêu fbest: hàm trả lại cá thể tốt nhất

2.4.3. Kết quả thực nghiệm

Để thực nghiệm thuật toán DEM, luận án sử dụng bộ dữ liệu iMOPSE trong

bảng 2.11, các thông số thực nghiệm được thiết lập tương tự như trong mục

2.3.3.2. Kết quả thực nghiệm được trình bày như trong bảng 2.17 sau đây.

Bảng 2.17: Kết quả thực nghiệm DEM với bộ dữ liệu iMOPSE

GA-M

HAntCO

GRASP

DEM

TT

Dataeset

BEST AVG STD BEST AVG STD BEST AVG STD BEST AVG STD

100_5_22_15

517

524

5.3

504

505

0.8

503

504

0.5

484

486

1.8

100_5_46_15

584

587

4.7

604

552

556

2.6

528

529

2.1

604

100_5_48_9

528

535

9.7

521

510

0.8

489

491.7 1.3

1.6

523

100_5_64_15

527

530

2.5

516

501

502

0.8

495

499

1.5

2.9

523

100_5_64_9

508

521

9.9

507

494

0.6

485

488.7 0.6

3.9

515

100_10_26_15

292

0.0

266

251

258

3.2

232

235

3.8

2.2

270

100_10_47_9

296

0.0

297

263

264

0.7

252

254.7

302

100_10_48_15

279

282

2.9

278

256

257

1.2

243

245.2 0.5

4.4

286

100_10_64_9

296

305

6.6

287

255

257

1.9

251

253

1.9

5.1

296

100_10_65_15

286

290

5.0

281

256

260

1.9

249

252.1 1.2

3.5

287

100_20_22_15

163

169

5.8

161

134

137

1.6

128

131.4 0.5

3.6

170

100_20_46_15

197

207

6.9

194

170

174

3.1

161

163.1 1.6

2.6

199

100_20_47_9

185

186

0.5

180

133

140

2.2

123

125.2 2.7

3.7

187

100_20_65_15

240

0.5

218

213

210

213.3 0.8

2.7

220

GA-M

HAntCO

GRASP

DEM

TT

Dataeset

BEST AVG STD BEST AVG STD BEST AVG STD BEST AVG STD

100_20_65_9

181

187

4.5

180

3.1

135

1.4

125

126.7 1.4

185

16 200_10_128_15 577

583

4.9

522

3.1

491

496

4.2

460

463.8 1.1

528

200_10_50_15

577

17.5

529

553

524

528

3.8

484

486.2 0.4

543

200_10_50_9

585

589

5.0

546

4.8

506

508

1.4

484

486.7 0.9

556

200_10_84_9

567

583

11.4

571

6.9

526

527

0.8

521

523

1.6

581

200_10_85_15

549

555

4.9

526

6.5

496

498

1.1

481

483.3 2.3

538

21 200_20_145_15

326

328

2.0

309

4.4

262

271

4.2

242

244.9 0.3

314

200_20_54_15

385

20.8

336

363

6.6

304

308

3.7

257

259.3 2.3

349

200_20_55_9

312

318

4.2

313

3.1

257

258

0.6

248

250

5.7

317

200_20_97_15

424

438

9.7

356

4.8

347

330

332.3 3.5

368

200_20_97_9

321

326

6.2

326

4.1

253

256

1.6

240

245.6 4.1

332

26 200_40_133_15

215

222

6.2

214

3.4

163

170

4.1

139

144.1 3.9

221

200_40_45_15

201

210

6.3

206

2.6

164

162

163.9 0.6

212

200_40_45_9

209

213

2.9

209

3.8

144

147

1.6

151

163

12.5

215

200_40_90_9

211

215

3.1

211

1.8

148

153

4.5

146

154

7.7

214

200_40_91_15

200

205

3.4

207

2.9

153

159

2.6

131

137

5.3

212

Bảng 2.18: So sánh kết quả thực nghiệm DEM với các thuật toán

BEST

AVG

Thuật toán

Tỉ lệ (%)

Tổng STD

Số lượng

Từ

Đến

Từ

Đến

74.9

DEM

30/30

4.53

33.51 30/30

5.79

32.71

173.3

GA-M

30/30

3.67

36.71 30/30

3.05

35.38

173.32

HAntCO

29/30

-4.86 15.46 27/30

-10.88 15.81

56.7

GRASP

Trong bảng 2.18:

- Cột “Số lượng” thể hiện số bộ dữ liệu (trên tổng số 30 bộ) mà thuật toán

- Tỉ lệ (%) cho biết kết quả của DEM tốt hơn/kém hơn các thuật toán còn

DEM có kết quả tốt hơn thuật toán ở hàng tương ứng.

lại. Giá trị âm thể hiện một vài trường hợp mà DEM cho kết quả kém

hơn.

Bảng 2.19: So sánh kết quả thực nghiệm DEM với M-PSO

DEM M-PSO Dataset

BEST AVG STD BEST AVG STD

100_5_22_15

484

486

1.8

485

486

1.7

100_5_46_15

528

529

2.1

530

531

0.5

100_5_48_9

489

491.7 1.3

490

492

1.6

100_5_64_15

495

499

1.5

478

479

1.3

100_5_64_9

485

488.7 0.6

471

474

2.5

100_10_26_15

232

235

3.8

233

0.4

100_10_47_9

252

254.7

257

261

3.7

100_10_48_15

243

245.2 0.5

244

245

0.6

100_10_64_9

251

253

1.9

240

246

5.9

100_10_65_15

249

252.1 1.2

244

245

1.3

100_20_22_15

128

131.4 0.5

128

131

3.1

100_20_46_15

161

163.1 1.6

162

165

2.9

DEM M-PSO Dataset

BEST AVG STD BEST AVG STD

100_20_47_9

123

125.2 2.7

124

128

3.6

100_20_65_15

210

213.3 0.8

228

230

1.8

100_20_65_9

125

126.7 1.4

125

0.3

200_10_128_15 460

463.8 1.1

461

464

2.7

200_10_50_15

484

486.2 0.4

489

490

0.7

200_10_50_9

484

486.7 0.9

487

491

3.7

200_10_84_9

521

523

1.6

508

510

2.1

200_10_85_15

481

483.3 2.3

473

476

2.5

200_20_145_15

242

244.9 0.3

236

237

1.4

200_20_54_15

257

259.3 2.3

256

0.3

200_20_55_9

248

250

5.7

251

255

3.5

200_20_97_15

330

332.3 3.5

334

337

3.3

200_20_97_9

240

245.6 4.1

255

256

0.9

200_40_133_15

139

144.1 3.9

147

151

4.1

200_40_45_15

162

163.9 0.6

163

167

200_40_45_9

151

163

12.5

152

162

9.5

200_40_90_9

146

154

7.7

145

152

7.1

200_40_91_15

131

137

5.3

135

143

8.3

2.4.4. Đánh giá chất lượng lời giải của thuật toán

Luận án đã tiến hành thực nghiệm thuật toán DEM áp dụng cho bài toán

MS-RCPSP. Thực nghiệm được chạy trên 30 bộ dữ liệu iMOPSE, với số lần

chạy thực nghiệm là 50 lần, số thế hệ tiến hóa là 100.000, thuật toán được cài

đặt trên môi trường thử nghiệm Matlab 2014. Kết quả thực nghiệm được trình

bày trong bảng 2.17. Kết quả thực nghiệm được tổng hợp và so sánh trong

bảng 2.18.

So sánh với GA-M cải tiến của nhóm Myszkowski, ta thấy:

- Về giá trị BEST và AVG: DEM tốt hơn GA-M trong tất cả các trường

hợp, trong đó giá trị BEST tốt hơn GA-M từ 4.53% đến 33.51% (chi tiết

trong hình 2.12)., giá trị AVG tốt hơn GA-M từ 5.79% đến 32.71% (chi

tiết trong hình 2.14).

- Về giá trị độ lệch chuẩn STD, tổng độ lệch chuẩn của GA-M là 173.3,

của DEM là 74.9 (chi tiết trong hình 2.13).. Từ kết quả này, có thể thấy,

thuật toán DEM mang lại hiệu quả cao hơn thuật toán GA-M và tính

ổn định của DEM cũng tốt hơn.

So sánh với các thuật toán lai (hybrid) khác

- Bảng 2.18 cho thấy, kết quả của DEM có kết quả tốt hơn các thuật toán

lai ở hầu hết các trường hợp, cụ thể: tốt hơn HAntCO với tất cả các bộ

dữ liệu (30/30), tốt hơn GRASP 26/30 bộ dữ liệu với giá trị BEST. Một

số trường hợp DEM kém hơn các thuật toán lai, tuy nhiên, giá trị kém

hơn không nhiều. Xét về tổng số các bộ dữ liệu, DEM tốt hơn các thuật

toán lai ở hầu hết các trường hợp.

Bảng 2.19 so sánh kết quả thực nghiệm của thuật toán M-PSO và thuật toán

DEM trên bộ dữ liệu iMOPSE. Các phương kết quả áp dụng với bài toán MS-

RCPSP của 2 thuật toán này cho thấy:

- Với giá trị BEST, DEM tốt hơn M-PSO ở 19/30 bộ dữ liệu, DEM có giá

trị bằng M-PSO ở 2 trường hợp và DEM có giá kém hơn M-PSO ở 9/30

bộ dữ liệu. Tuy nhiên, giá trị STD của DEM là 74.9, tốt hơn so với M-

PSO là 85.3, điều này cho thấy DEM có độ ổn định hơn M-PSO.

- Cũng qua kết quả trong bảng 2.19 cho thấy, DEM tốt hơn M-PSO trong

các trường hợp dự án có cùng số tác vụ nhưng số lượng tài nguyên lớn

hơn.

Các kết quả của DEM có được nhờ việc ứng dụng thuật toán tiến hóa vi

phân (DE) kết hợp với cải tiến quan trọng là việc áp dụng hàm Reallocate. DE

có đặc tính định hướng cao dựa trên kinh nghiệm của quần thể và cá thể qua

các thế hệ, hàm Reallocate sẽ giúp tính toán lại các thể tốt nhất tìm được sau

mỗi thế hệ bằng việc thay thế tài nguyên thực hiện các tác vụ, việc này giúp

thuật toán mở rộng được không gian tìm kiếm và nâng cao khả năng hội tụ.

2.4.5. Hình ảnh so sánh DEM với thuật toán GA-M

Hình 2.12. So sánh giá trị BEST giữa DEM với GA-M

Hình 2.13. So sánh giá trị STD giữa DEM với GA-M

Hình 2.14. So sánh giá trị AVG giữa DEM với GA-M

Kết luận chương 2

Bài toán MS-RCPSP là bài toán có nhiều ứng dụng trong thực tế và đã được

chứng minh là bài toán thuộc lớp NP-Khó, nên không thể tìm được nghiệm

chính xác trong thời gian chấp nhận được. Để giải bài toán này, cần có các thuật

toán cận tối ưu để tìm các các lời giản tốt trong thời gian ngắn.

Trong chương này, luận án đã trình bày về cách mã hóa cá thể và thang đo

độ chênh giữa hai cá thể, đây là cơ sở quan trọng cho các cải tiến tiếp theo. Để

giải bài toán, 2 thuật toán mới đã được đề xuất gồm:

Thuật toán 1: M-PSO, là thuật toán được xây dựng trên cơ sở của thuật toán

tối ưu bầy đàn với cải tiến mới là kỹ thuật di cư, kỹ thuật này giúp thoát khỏi

cực trị địa phương và mở rộng không gian tìm kiếm của bài toán.

Thuật toán 2: DEM, là thuật toán được phát triển từ thuật toán tiến hóa vi

phân (DE) để áp dụng cho bài toán MS-RCPSP. Cải tiến quan trọng của DEM

là áp dụng hàm Reallocate để tái thiết lập tài nguyên thực hiện các tác vụ trong

một lời giải, giúp bài toán mở rộng không gian tìm kiếm và hội tụ nhanh chóng.

Thuật toán này đã được công bố trong công trình [CT7], [CT8].

Để kiểm chứng tính hiệu quả của M-PSO và DEM, luận án đã triển khai

thực nghiệm với bộ dữ liệu iMOPSE và có đánh giá so sánh cụ thể sau mỗi

phần thực nghiệm.

Kết quả nghiên cứu của chương này được công bố tại:

- Hội thảo quốc tế 6th NAFOSTED Conference on Information and Computer

Science (NICS), Hanoi, Vietnam, pp. 73-76, 2019 [CT5].

- Tạp chí International Journal of Electrical and Computer Engineering

(IJECE), (Q3), Vol. 8, No. 5, pp. 3851-3858, October 2018 [CT2];

- Tạp chí Scientific Programming (IF:1.28, Q3), Volume 2020, Article ID

8860384, 12, 2020 [CT8].

CHƯƠNG 3

BÀI TOÁN REAL-RCPSP

Mô hình bài toán MS-RCPSP bổ sung yếu tố kỹ năng và mức kỹ năng của

tài nguyên, nên khi yêu cầu tài nguyên thực hiện tác vụ cũng cần chỉ ra loại kỹ

năng và mức kỹ năng tối thiểu cần thiết để thực hiện. Việc điều chỉnh này giúp

bài toán MS-RCPSP có thể áp dụng được vào một số lĩnh vực thực tế. Tuy

nhiên, trong các mô hình sản xuất, cần có những yêu cầu cụ thể và chính xác

hơn như với mỗi tác vụ, tài nguyên (công nhân) có mức kỹ năng (trình độ) cao

hơn có thể hoàn thành công việc sớm hơn hoặc với chất lượng tốt hơn. Đây

chính là nhược điểm của bài toán MS-RCPSP, bài toán này quy định thời gian

thực hiện một tác vụ là như nhau với bất kỳ tài nguyên thực hiện nào. Để khắc

phục hạn chế này của bài toán MS-RCPSP, luận án đã đưa ra mô hình bài toán

Real-RCPSP với ràng buộc về thời gian thực hiện tác vụ thay đổi theo mức kỹ

năng của tài nguyên thực hiện. Phần tiếp theo của chương 03, luận án sẽ trình

bày các vấn đề sau:

Phần 3.1: Phát biểu bài toán mới Real-RCPSP. Đây là bài toán có khả năng

ứng dụng cao trong thực tiễn do được bổ sung các ràng buộc về thời gian thực

hiện liên quan đến mức kỹ năng của các tài nguyên.

Phần 3.2: Xếp loại bài toán Real-RCPSP.

3.1. Bài toán Real-RCPSP

Trong thực tế sản xuất, thông thường, nhân công (tài nguyên) có trình độ

tay nghề (mức kỹ năng) cao hơn, thường hoàn thành công việc với thời gian ít

hơn hoặc chất lượng tốt hơn hoặc cả hai. Do vậy, để áp dụng tốt hơn việc lập

kế hoạch điều phối công việc, kế hoạch trong sản xuất kinh doanh. Luận án đề

xuất một bài toán mới là Real-RCPSP. Bài toán này được phát triển dựa trên

cơ sở của bài toán MS-RCPSP và bổ sung thêm ràng buộc về mức kỹ năng của

tài nguyên thực hiện. Tài nguyên thực hiện tác vụ có mức kỹ năng cao hơn mức

kỹ năng yêu cầu thì thời gian hoàn thành tác vụ có thể nhanh hơn.

3.1.1. Phát biểu bài toán

Các ký hiệu:

 Ci: tập tác vụ (task) cần thực hiện trước tác vụ i

 S: tập tất các các kỹ năng của các tài nguyên; Si: Tập các kỹ năng của tài

nguyên i, Si  S;

 Si: kỹ năng thứ i;

 tjk: thời gian thực hiện tác vụ j bởi tài nguyên k, thời gian thực hiện cùng

một tác vụ có thể khác nhau với tài nguyên thực hiện khác nhau.

 L: tập các tài nguyên;

 Lk: tập tài nguyên có thể thực hiện tác vụ k; Lk  L

 Li: tài nguyên thứ i

 W: tập các tác vụ của dự án;

 Wk: tập các tác vụ có thể thực hiện bởi tài nguyên k, Wk  W

 Wi: tác vụ thứ i

 ri: tập các kỹ năng được yêu cầu để thực hiện tác vụ i. Một tài nguyên có

thể thực hiện được tác vụ i nếu có kỹ năng giống với kỹ năng yêu cầu của

tác vụ i và có mức kỹ năng lớn hơn hoặc bằng mức kỹ năng yêu cầu.

i: biến xác định tài nguyên v có đang thực hiện tác vụ u tại thời điểm i

 Bk, Ek: thời gian bắt đầu và thời gian kết thúc thực hiện tác vụ k

 Au,v

hay không; 1: có, 0: không

 hi: mức kỹ năng của kỹ năng (skill) i; gi: loại kỹ năng i;

 m: makespan của lịch biểu

 P: một lịch biểu khả thi của bài toán; Pall: Tập tất cả các lịch biểu

 f(P): hàm mục tiêu, để tính makespan của P

 n: số tác vụ, z: số tài nguyên

Mục tiêu của bài toán Real-RCPSP là tìm lịch biểu P sao cho:

f(P)  min

lịch biểu tìm được cần thỏa mãn các ràng buộc sau:

(3.1)  Sk    Lk L

 (3.2) tjk  0  Wj W,  Lk L

(3.3)  Ej  0  WjW

(3.4)

(3.5)

𝑞  ∀ 𝐿𝑘 ∈ 𝐿, ∀𝑞 ∈ 𝑚 ∶ ∑ 𝐴𝑖,𝑘

(3.6) ≤ 1  Ei  Ej - tj WjW, j1, WiCj  ∀ W𝑖 ∈ 𝑊𝑘 ∃ 𝑆𝑞 ∈ 𝑆𝑘 ∶ 𝑔𝑆𝑞 = 𝑔𝑟𝑖 và ℎ𝑆𝑞 ≥ ℎ𝑟𝑖 𝑛 𝑖=1

𝑞 ∈ {0; 1}

𝑞 = 1; với 𝐴𝑗,𝑘

(3.7)  ∀ 𝑊𝑗 ∈ 𝑊 ∃! 𝑞 ∈ [0, 𝑚], ! 𝐿𝑘 ∈ 𝐿: 𝐴𝑗,𝑘

 (3.8) 𝑡𝑖𝑘 ≤ 𝑡𝑖𝑙 𝑣ớ𝑖 ℎ𝑘 ≤ ℎ𝑙 ∀ (𝑟𝑘, 𝑟𝑙) ∈ {𝑆𝑘 × 𝑆𝑙 }

Cụ thể:

 Các ràng buộc (3.1 đến 3.7) được phát biểu tương tự như bài toán MS-

RCPSP

 Ràng buộc (3.8): là ràng buộc riêng của bài toán Real-RCPSP, thể hiện tài

nguyên thực hiện có mức kỹ năng (trình độ) lớn hơn yêu cầu của tác vụ,

thì thời gian thực hiện có thể nhỏ hơn hơn thời gian chuẩn của tác vụ.

3.1.2. Những ứng dụng thực tế của bài toán Real-RCPSP

Cải tiến quan trọng của bài toán Real-RCPSP là sự điều chỉnh thời gian

thực hiện mỗi tác vụ theo mức kỹ năng. Nếu xem xét cụ thể trong các dự án

thực tế, thông thường với cùng một tác vụ, nhân công (tài nguyên) có trình độ

cao sẽ hoàn thành trong thời gian ngắn hơn nhân công có trình độ thấp. Do vậy,

bài toán Real-RCPSP có khả năng ứng dụng cao trong thực tiễn, một số lĩnh

vực cụ thể có thể áp dụng mô hình bài toán này là:

- Trong lĩnh vực sản xuất: thông thường các quy trình sản xuất thành phẩm

sẽ thực hiện theo dây chuyền gồm nhiều công đoạn, mỗi công đoạn yêu cầu

nhân công thực hiện với trình độ tay nghề khác nhau. Khi đó, bài toán Real-

RCPSP sẽ căn cứ trên các tài nguyên sẵn có, đưa ra một kế hoạch sản xuất

tốt, tiết kiệm tối đa thời gian thực hiện.

- Trong lĩnh vực logistic: bài toán này giúp lên kế hoạch, điều phối kho bãi,

thiết bị giao vận một cách phù hợp theo các nhu cầu lưu kho, vận chuyển cụ

thể, tránh lãng phí tài nguyên.

- Cấp phát tài nguyên trong các hệ thống công nghệ thông tin: tùy theo từng

công việc cụ thể, nhu cầu sử dụng tài nguyên có thể khác nhau, các tài

nguyên bao gồm: hệ thống máy chủ, hệ thống lưu trữ, lưu lượng mạng, khả

năng xử lý, ... Bài toán Real-RCPSP có thể áp dụng một cách hiệu quả trong

việc phân công, cấp phát tài nguyên theo từng yêu cầu cụ thể, trong các hệ

thống IoT và nhiều lĩnh vực ứng dụng khác.

3.2. Xếp loại bài toán Real-RCPSP thông qua phân loại Graham

Lập lịch (Scheduling) là tên gọi chung để chỉ họ bài toán bao gồm rất nhiều

nhánh với những đặc trưng đa dạng. Những trường hợp riêng, những bài toán

con mới trong họ bài toán lập lịch không ngừng được các nhóm nghiên cứu đề

xuất và nghiên cứu vì chúng xuất hiện trong mọi mặt của khoa học, công nghệ

và đời sống. Họ bài toán lập lịch có nhiều lớp, nhiều bài toán con và nhiều biến

thể khác nhau, nên cần được phân loại để thuận lợi trong việc so sánh, đối chiếu.

Năm 1979 Graham [51] đã đề xuất một cách phân loại cho các bài toán Lập

lịch. Cách phân loại Graham, sau khi được Veltman [9] bổ sung vào năm 1990,

được giới nghiên cứu công nhận và sử dụng một cách rộng rãi. Cách phân loại

Graham khá đơn giản và dễ thực hiện, đồng thời cho phép biểu diễn tất cả

những yếu tố - vốn rất đa dạng và phức tạp của các bài toán - chỉ bằng ba thành

phần ký hiệu là α|β|γ. Ngoài ra cách phân loại Graham (đôi khi còn được gọi là

Ký pháp Graham) có thể được mở rộng để biểu thị hầu hết các bài toán con

trong họ bài toán Lập lịch, nói cách khác gần như mọi bài toán Lập lịch đều có

thể biểu diễn được bằng ký pháp Graham, hơn nữa cách biểu diễn đó lại rất

ngắn gọn.

Để phân loại các bài toán lập lịch, Graham xem xét ba thành phần cơ bản

mà bài toán lập lịch nào cũng có, đó là:

 α: thành phần đặc trưng cho tác vụ, mô tả những tác vụ mà hệ thống cần

thực hiện.

 β: thành phần đặc trưng cho hệ thống đang cần lập lịch, mô tả những đặc

trưng của hệ thống.

 γ: thành phần đặc trưng cho mục tiêu của việc lập lịch, cho biết đại lượng

nào cần được tối ưu hóa.

Sau đó Veltman đề xuất và được giới nghiên cứu nhất trí sử dụng ba thành

phần đó theo một thứ tự logic hơn như sau:

 Thành phần thứ nhất (α) mô tả những đặc trưng của hệ thống như: số lượng

tài nguyên (trong trường hợp cụ thể, tài nguyên là các server, router, công

nhân, robot...), năng lực tính toán của tài nguyên, cơ chế đồng bộ hóa và

mạng kết nối giữa các tài nguyên.

 Thành phần thứ hai (β) mô tả các tính chất của tác vụ, công việc.

 Thành phần thứ ba (γ) chỉ ra mục tiêu của bài toán là gì, mô tả đại lượng

cần được tối ưu hóa. Chẳng hạn như việc giải bài toán hướng đến việc tối

thiểu hóa thời gian thực hiện, tối đa hóa lợi nhuận hay tối thiểu hóa chi phí.

Trong ký pháp Graham, mỗi thành phần là một hoặc một dãy ký hiệu ngăn

cách nhau bởi dấu phẩy, các ký hiệu đó cho biết bài toán thuộc lớp bài toán con

nào trong những trường hợp đã biết.

Thành phần thứ nhất (α)

Để biểu diễn những đặc trưng của hệ thống, thành phần thứ nhất bao gồm

hai trường là Kiểu tài nguyên và Số lượng tài nguyên. Mỗi trường bao gồm

những ký hiệu phản ánh những đặc trưng dưới đây.

Kiểu tài nguyên:

 1: hệ thống chỉ có một tài nguyên duy nhất

 P: hệ thống gồm nhiều tài nguyên giống hệt nhau về năng lực và chúng hoạt

động song song với nhau.

 𝑃̅: như trường hợp P song song bổ sung thêm giả thiết rằng số lượng tài

nguyên lớn hơn hoặc bằng số lượng tác vụ cần thực hiện.

 Q: hệ thống gồm những tài nguyên khác nhau về năng lực. Bài toán Real-

RCPSP có đặc trưng này.

 MPM: mỗi tài nguyên có thể thực hiện bất cứ tác vụ nào hay bất cứ công

đoạn nào của tác vụ trong trường hợp tác vụ bao gồm nhiều công đoạn.

 O: Bài toán Open Shop

 F: Bài toán Flow Shop

 J: Bài toán Job Shop

Số lượng tài nguyên:

 Để trống: số lượng tài nguyên thay đổi tùy theo giải pháp sử dụng. Bài toán

Real-RCPSP có đặc trưng này.

 Một số nguyên dương m: các giải pháp bắt buộc phải sử dụng đúng m tài

nguyên, m được quy định bởi giả thiết của bài toán.

 ∞: các giải pháp được sử dụng số lượng tài nguyên tùy ý, không giới hạn

Thành phần thứ hai (β):

Thành phần này mô tả các đặc trưng của tác vụ công việc phải thực hiện

thông qua một hoặc nhiều trường con ngăn cách nhau bởi dấu phẩy. Các trường

con bao gồm:

Thứ tự thực hiện hoặc quyền ưu tiên giữa các tác vụ:

 Để trống: các tác vụ được thực hiện độc lập với nhau, nói cách khác tập

cạnh E=∅

 prec: bài toán có quy định một thứ tự thực hiện nào đó giữa các tác vụ, khi

đó tác vụ cha phải được thực hiện trước tác vụ con. Thứ tự này được biểu

diễn thông qua đồ thị G thuộc dạng DAG (có hướng, không có chu trình).

Bài toán Real-RCPSP có đặc trưng này.

 {outtree, intree, tree, fork, join, chains}: đồ thị G hình cây có gốc, thuộc

một trong các dạng mô tả trong hình 3.1, trong đó Fork và Join là hai trường

Fork

Join

Outtree

Intree

Chains

hợp riêng của đồ thị dạng Outtree và Intree khi số nút nguồn =1.

Hình 3.1. Các kiểu thứ tự thực hiện tác vụ

Chi phí thực hiện hoặc thời gian thực hiện tác vụ:

 Để trống: thời gian truyền thông giữa các tác vụ bằng không, mỗi tác vụ chỉ

được thực hiện bởi duy nhất 1 tài nguyên, thời gian thực hiện tùy thuộc vào

tác vụ và tài nguyên thực hiện tác vụ đó. Bài toán Real-RCPSP có đặc trưng

này.

 ri: mỗi tác vụ phải hoàn thành trước một thời hạn cho trước nào đó.

 pi = 1: mọi tác vụ đều có chi phí/thời gian thực hiện bằng nhau và bằng 1

đơn vị

 pi = p: mọi tác vụ đều có chi phí/thời gian thực hiện bằng nhau và bằng p

đơn vị

 pmtn: quá trình thực hiện một tác vụ có thể bị dừng lại để tài nguyên chuyển

sang thực hiện một tác vụ khác có mức ưu tiên cao hơn, sau khi xong mới

quay lại tiếp tục thực hiện tác vụ ban đầu

Chi phí hoặc thời gian truyền thông:

 Để trống: chi phí/thời gian truyền được giả thiết là bằng không. Bài toán

Real-RCPSP có đặc trưng này.

 cij: mỗi tuyến liên kết (biểu diễn bởi 1 cạnh eijE) tương ứng với một chi

phí/thời gian truyền riêng được tính theo một công thức nào đó.

 c: chi phí/thời gian truyền của mọi tuyến liên kết là bằng nhau: c(eij) = c;

eij E

Thành phần thứ ba (γ):

Thành phần này mô tả mục tiêu của bài toán bằng các ký hiệu như sau:

 Cmax: mục tiêu của việc xếp lịch là nhằm tối thiểu hóa makespan. Bài toán

Real-RCPSP có đặc trưng này.

 Lmax: mục tiêu của việc xếp lịch là nhằm tối thiểu hóa thời gian trễ.

Theo các quy định về phân loại bài toán như trên, bài toán Real-RCPSP

được biểu diễn theo ký pháp Graham như sau:

Q|prec|Cmax

Kết luận chương 3

Bài toán Real-RCPSP là một nhánh của bài toán MS-RCPSP trong đó thời

gian thực hiện tác vụ sẽ thay đổi theo mức kỹ năng của tài nguyên thực hiện,

mức kỹ năng càng cao (so với yêu cầu) thì thời gian thực hiện càng ngắn. Bài

toán này có thể triển khai ứng dụng trong nhiều lĩnh vực, đặc biệt là trong việc

lập lịch điều phối quá trình sản xuất sản phẩm.

Trong chương này, luận án đã trình bày phát biểu toán học của bài toán, các

ứng dụng của bài toán Real-RCPSP và phân loại bài toán.

Kết quả nghiên cứu của chương này được công bố tại:

Tạp chí Journal of Advanced Transportation (IF: 1.67,

Q2), Volume 2020, Article ID 8897710, 11 pages, 2020 [CT9]

CHƯƠNG 4

GIẢI BÀI TOÁN REAL-RCPSP BẰNG PHƯƠNG PHÁP TIẾN HÓA

Bài toán Real-RCPSP bổ sung thêm ràng buộc về thời gian thay đổi theo

VI PHÂN VÀ PHƯƠNG PHÁP CUCKOO SEARCH

mức kỹ năng của tài nguyên thực hiện, do vậy có khả năng ứng dụng cao trong

thực tế đặc biệt trong việc lập kế hoạch sản xuất trong các dây chuyền công

nghiệp. Trong chương này, luận án sẽ tập trung vào các phương pháp để giải

bài toán mới, giúp tìm được các phương pháp lịch biểu tốt. Phần tiếp theo của

chương 04 sẽ trình bày các vấn đề sau:

Phần 4.1: Trình bày phương pháp biểu diễn cá thể của bài toán Real-

RCPSP.

Phần 4.2: Giới thiệu bộ dữ liệu thực nghiệm chuyền may của công ty TNG

[54], đây là bộ dữ liệu được số hóa từ các hợp đồng may mặc thực tế.

Phần 4.3: Trình bày thuật toán A-DEM đề giải bài toán Real-RCPSP. Đây

là thuật toán được xây dựng trên cơ sở của thuật toán tiến hóa vi phân (DE) với

cải tiến mới bằng việc bổ sung hàm thích nghi (Adaptive).

Phần 4.4: Trình bày thuật toán R-CSM để giải bài toán Real-RCPSP. Thuật

toán này được phát triển từ thuật toán Cuckoo Search (CS) [60],[61] với cải

tiến mới là áp dụng phương pháp Reallocate để tái thiết lập tài nguyên thực

hiện tác vụ đối với cá thể tốt nhất sau mỗi thế hệ.

Phần 4.5: Trình bày thuật toán RR-CSM, đây là thuật toán cải tiến từ thuật

toán R-CSM với cải tiến mới là áp dụng thêm kỹ thuật Rotate trên cá thể tốt

nhất đã được cải tiến trong R-CSM.

Các thuật toán được kiểm chứng bằng việc thực nghiệm trên 2 bộ dữ liệu

iMOPSE và bộ dữ liệu của TNG (bộ dữ liệu thực tế được thu thập từ hoạt động

sản xuất chuyền may công nghiệp, sau đó được số hóa để phù hợp với đầu vào

của bài toán Real-RCPSP).

4.1. Phương pháp biểu diễn cá thể

Trong bài toán Real-RCPSP, một cá thể hay một lịch biểu là một vector có

số phần tử bằng số tác vụ của dữ liệu đầu vào, mỗi phần tử của vector lịch biểu

có giá trị bằng chỉ số của tài nguyên sử dụng để thực hiện tác vụ đó. Ngoài vấn

đề đáp ứng các ràng buộc của bài toán (tương tự như bài toán MS-RCPSP như

trình bày trong phần 2.1), Real-RCPSP còn chứa các thông tin mô tả về thời

gian thực hiện tác vụ theo mức kỹ năng.

Định nghĩa 4.1: Thời gian chuẩn thực hiện một tác vụ là thời gian thực

hiện tác vụ đó với tài nguyên đáp ứng yêu cầu tối thiểu. Tài nguyên có mức kỹ

năng cao hơn yêu cầu tối thiểu sẽ thực hiện tác vụ với thời gian nhỏ hơn hoặc

bằng thời gian chuẩn.

Ví dụ 4.1: Xét một dự án gồm 10 tác vụ, 2 tài nguyên thực hiện.

- Tập hợp tác vụ W={W1, W2, W3, W4, W5, W6, W7, W8, W9, W10}

- Tập hợp tài nguyên L = {L1, L2}.

Thứ tự ưu tiên của các tác vụ được biểu diễn như trong hình 2.1

Thời gian chuẩn thực hiện từng tác vụ (tính theo giờ) được thể hiện trong

bảng 4.1.

Bảng 4.1: Thời gian chuẩn thực hiện các tác vụ

Tác vụ 1 2 3 4 5 6 7 8 9 10

Thời gian 4 6 3 5 3 7 4 5 6 4

Thông tin về năng lực của tài nguyên được thể hiện trong bảng 4.2.

Bảng 4.2: Năng lực tài nguyên của dự án

Kỹ năng 1 Kỹ năng 2 Kỹ năng 3

Tài nguyên g1 h1 h2 g3 h3 g2

× 1 3 × 4 ×

× 2 × 5 L1 L2

Bảng 4.2 cho thấy, các tài nguyên gồm có ba loại kỹ năng, kỹ năng g1 có

mức kỹ năng 1 hoặc 2, kỹ năng g2 có mức kỹ là 3 và kỹ năng g3 có mức kỹ

năng là 4 hoặc 5.

Thông tin về yêu cầu tài nguyên thực hiện của tác vụ và thời gian thực hiện

tương ứng với các mức kỹ năng được thể hiện như trong bảng 4.3 dưới đây.

Bảng 4.3: Yêu cầu tài nguyên thực hiện tác vụ và thời gian thực hiện

Tác vụ Thời gian thực hiện theo mức kỹ năng

Kỹ năng h3 h4 h5 h1 h2

4 3 2 2 3

5 4 4 g1 g2 W1 W2

3 2 2 3 g1 W3

4 3

3 3 2 g3 g2 W4 W5

7 6 5

4 3 2 2 3 g2 g1 W6 W7

5 4 3 3 4 g1 W8

6 5

4 3 3 g3 g2 W9 W10

Trong bảng 4.3, cột kỹ năng thể hiện loại kỹ năng yêu cầu để thực hiện tác

vụ, các cột h1 đến h5 thể hiện yêu cầu về mức kỹ năng của tài nguyên thực hiện,

mức kỹ năng càng cao thì thời gian thực hiện tác vụ càng thấp.

Căn cứ trên yêu cầu như trong bảng 4.3, một lịch biểu có thể được biểu diễn

như một vector dưới dạng như sau:

Tác vụ Tài nguyên 1 1 2 2 2 W1 W2 W3 W4 W5 W6 W7 W8 W9 W10 1 2 2 2 1

Như vậy, tài nguyên L1 sẽ thực hiện các tác vụ: W2, W5, W6, W10; tài nguyên

L2 thực hiện các tác vụ: W1, W3, W4, W7, W8, W9. Với lịch biểu này, thời gian

thực hiện từng tác vụ được thể hiện trong bảng 4.4.

Trong bảng 4.4, các tác vụ W2, W3, W5, W6, W10 được thực hiện bởi tài

nguyên đáp ứng yêu cầu tối thiểu, do vậy thời gian thực hiện bằng thời gian

chuẩn. Các tác vụ còn lại được thực hiện với tài nguyên có mức kỹ năng cao

hơn nên có thời gian thực hiện thấp hơn thời gian chuẩn.

Bảng 4.4: Thời gian thực hiện các tác vụ

Tác vụ 1 2 3 4 5 6 7 8 9 10

Thời gian 3 5 3 3 3 7 3 4 5 4

Lịch biểu này có thể được biểu diễn dạng biểu đồ Gantt như trong hình 4.1

Time

dưới đây.

Hình 4.1. Biểu đồ Gantt của lịch biểu trong ví dụ 4.1

4.2. Đề xuất thuật toán A-DEM

Thuật toán tiến hóa vi phân (DE: Differential Evolution) được áp dụng để

giải các bài toán NH-Khó. Trong DE, mỗi cá thể tiến hóa qua các thế hệ bằng

cách sử dụng 02 tham số chính là bước nhảy F và hệ số lai ghép CR, đây là các

hằng số sử dụng cho toàn bộ quá trình tiến hóa của thuật toán. Việc sử dụng

các hằng số làm DE có khả năng hội tụ nhanh, tuy nhiên dễ rơi vào cực trị địa

phương.

Thuật toán A-DEM (Adaptive DE for Real-RCPSP) được xây dựng trên cơ

sở thuật toán DE với các cải tiến quan trọng như sau:

(i) Tìm một cá thể lân cận tốt nhất với cá thể đang xem xét bằng cấu trúc hình

sao, cá thể này sử dụng trong quá trình đột biến.

(ii) Thay đổi hệ số lai ghép (CR) một cách linh động (Adaptive) theo từng thế

hệ dựa trên việc ghi nhận số cá thể đột biến thành công.

4.2.1. Phương pháp thích nghi

Trong thuật toán DE gốc, một toán tử quan trọng quyết định đến quá trình

đột biến của cá thể là hệ số lai ghép CR, là một hằng số. Thuật toán A-DEM sử

dụng cách tiếp cận thích nghi (Adaptive) để thay đổi tham số CR theo từng thế

hệ tiến hóa. Điều này giúp thuật toán mở rộng không gian tìm kiếm, hạn chế

rơi vào cực trị địa phương đồng thời sử dụng được kinh nghiệm tốt của thế hệ

trước để tạo ra các thế hệ sau tốt hơn, giúp thuật toán hội tụ nhanh hơn.

4.2.1.1. Kiến trúc Star

Kiến trúc hình sao (Star topology) [10],[35],[58] là một kiến trúc quần thể

trong đó các cá thể kết nối đến một cá thể ở trung tâm. Hình 4.2 là một ví dụ

về kiến trúc hình sao, trong đó, trong đó các cá thể bên ngoài sẽ đều có kết nối

đến cá thể trung tâm.

Hình 4.2. Kiến trúc hình sao

Kiến trúc hình sao có thể áp dụng trong việc tìm các cá thể lân cận dựa trên

một hoặc nhiều tiêu chí đo khác nhau như khoảng cách, thời gian truyền thông

tin, tính chất tương tự... Trong bài toán tiến hóa, chúng ta có thể áp dụng cấu

trúc hình sao để tìm các cá thể gần nhau phục vụ cho việc lai ghép, đột biến

trong các thế hệ. Áp dụng trong bài toán Real-RCPSP, việc tìm các cá thể lân

cận dựa trên khoảng cách chênh lệch (tính theo giờ) giữa một cá thể với các cá

thể khác.

Ví dụ 4.2:

Xem xét quần thể gồm 10 cá thể, với thời gian thực hiện của từng cá thể

được thể hiện trong hình 4.3.a.

Mục tiêu: tìm 03 các thể khác là lân cận với cá thể thứ 5 theo cấu trúc hình

sao. Ta thực hiện qua các bước sau:

Bước 1: sắp xếp quần thể theo thứ tự tăng dần của thời gian thực hiện, ta

có kết quả như trong hình 4.3.b.

Bước 2: duyệt danh sách Pall đã sắp xếp để tính khoảng cách với với cá thể

P5, ta có d5 = 13.

Bước 3: duyệt Pall để lấy 3 cá thể lân cận với P5. Các cá thể lân cận lấy được

S = {P2, P4, P6}.

gồm: P5

Thời gian Thời gian Pall Pall sorted d5

123 123 14 P1 P1

130 127 10 P2 P4

175 130 7 P3 P2

127 137 0 P4 P5

137 150 13 P5 P6

150 162 25 P6 P9

201 173 36 P7 P10

185 175 38 P8 P3

162 185 48 P9 P8

(a) Quần thể ban đầu

173 64 201 P10

P7 (b) Quần thể sau khi sắp xếp

Hình 4.3. Tìm các cá thể lân cận

4.2.1.2. Ý tưởng của phương pháp thích nghi

Mục tiêu của phương pháp thích nghi (Adaptive) là điều chỉnh hệ số lai

ghép µCR qua mỗi thế hệ nhằm tăng hiệu quả của thuật toán, việc điều chỉnh

phụ thuộc vào kết quả thực hiện tiến hóa của quần thể. Để ứng dụng tốt trong

bài toán Real-RCPSP, kỹ thuật thích nghi kết hợp với cấu trúc hình sao được

sử dụng để tìm kiếm các lân cận. Các bước cụ thể như sau:

- Hệ số lai ghép của cá thể thứ i, ký hiệu là CRi được tính hàm ngẫu nhiên

Cauchy của tham số lai ghép µCR, trong đo µCR được tính dựa trên số lượng

cá thể đột biến thành công trong thế hệ trước đó.

- Khi thực hiện thuật toán DE, tại thời điểm xem xét đột biến cá thể, thay vì

lựa chọn ngẫu nhiên 03 cá thể từ quần thể ban đầu, chúng ta sẽ sử dụng một

cá thể là localbest được tính toán dựa trên kiến trúc hình sao.

- Số lượng cá thể lân cận trong kiến trúc hình sao được thay đổi theo mỗi thế

hệ.

Ví dụ 4.3:

Xem xét ví dụ 4.2, tìm cá thể tốt nhất theo cấu trúc hình sao của cá thể thứ

5, biết rằng tại thời điểm thực hiện, số lượng cá thể lân cận để tìm cá thể tốt

nhất là w = 4.

S = {P5, P2, P4, P6}.

Sau bước 3 của ví dụ 4.2, ta có P5

S để tìm ra cá thể tốt nhất, tức là cá thể có thời gian thực hiện tối

Duyệt P5

thiểu. Căn cứ vào kết quả trong hình 4.3.b, ta dễ dàng tìm được cá thể tốt nhất

là P4 với thời gian thực hiện là 127.

Với ý tưởng điều chỉnh trong quá trình tiến hóa, khi áp dụng phương pháp

thích nghi vào thuật toán DE, sẽ mang lại các thay đổi như sau:

- Hệ số lai ghép thay đổi (thích nghi) theo kết quả thực hiện qua từng thế hệ

giúp việc tính toán linh động hơn, đa dạng hơn về cách lai ghép, đột biến,

lựa chọn.

- Sử dụng một cá thể localbest sẽ giúp việc đột biến thực hiện tốt hơn do tận

dụng được kinh nghiệm của cá thể tốt trước đó, điều này giúp thuật toán

nhanh hội tụ

- Sử dụng cấu trúc hình sao, giúp mở rộng không gian tìm kiếm, sẽ hạn chế

việc rơi vào cực trị địa phương.

Phương pháp thích nghi này được thể hiện thành hàm StarAdaptive dưới

đây.

4.2.1.3. Hàm StarAdaptive

Các bước thực hiện tìm kiếm cá thể lân cận tốt nhất, được chi tiết trong

Algorithm 4.1 StarAdaptive dưới đây. Đầu vào gồm: quần thể ban đầu,

vị trí của cá thể hiện tại và số cá thể lân cận để duyệt tìm cá thể tốt nhất.

Algorithm 4.1. StarAdaptive

Input: Pall: quần thể i: vị trí của cá thể hiện tại w: số cá thể lân cận Output: Pibest: cá thể tốt nhất trong

Begin

1. PR = {} 2. fitness ← f(Pall) // tính thời gian thực hiện của các cá

thể

3. mp = fitness(i) 4. Psortall ← sort(Pall, fitness) // sắp xếp quần thể theo fitness 5. Di = findDistance(i) 6. For j=1 to size(Pall) // duyệt lần lượt từng cá thể 7. If abs( fitness(j) – mp) ≤ Di 8. PS= PS + {Pj} 9. End if 10. End for 11. Pibest = fbest(PS) 12. Return Pibest

End Function

Trong đó:

findDistance: hàm tìm khoảng cách tối đa tính từ vị trí

i để có thể lấy đủ số cá thể lân cận với Pi

Hàm StarAdaptive sẽ được dùng trong thuật toán A-DEM để tìm kiếm cá

thể tốt nhất trong các cá thể lân cận với cá thể hiện tại.

4.2.2. Thuật toán A-DEM

Thuật toán A-DEM sử dụng kỹ thuật thích nghi trên cơ sở thay đổi hệ số

lai ghép và tìm cá thể tốt nhất dựa trên kiến trúc Star được thực hiện qua các

bước như sau:

- Bước 1: Khởi tạo quần thể với N cá thể: Pall

- Bước 2: Khởi tạo các giá trị ban đầu

- Bước 3: Thực hiện các tiến hóa qua các thế hệ

- Bước 4: Với mỗi thế hệ, duyệt từng cá thể Pi và thực hiện

best theo kiến trúc Star

- Bước 4.1: Tính toán Pi

- Bước 4.2: Tính toán hệ số lai ghép CR dựa trên tham số lai ghép µCR

- Bước 4.3: Lấy ngẫu nhiên 02 cá thể P1, P2 từ quần thể (khác với cá thể hiện

tại)

- Bước 4.4: Tạo ra cá thể vi bằng phép đột biến theo công thức:

Vi  Pi + F  (Pbest – Pi) + F  (P1 - P2)

𝑈𝑖,𝑗 = {

𝑉𝑖,𝑗 𝑛ế𝑢 rand(0,1) ≤ 𝐶𝑅𝑖 ℎ𝑜ặ𝑐 𝑖 = 𝐼𝑟𝑎𝑛𝑑 𝑃𝑖,𝑗 𝑛ế𝑢 rand(0,1) > 𝐶𝑅𝑖 ℎ𝑜ặ𝑐 𝑖 ≠ 𝐼𝑟𝑎𝑛𝑑

j ∈ (1,taskcount)

- Bước 4.5: Tạo ra cá thể mới Ui theo công thức

𝑈𝑖 𝑛ế𝑢 f(Ui) < 𝑓(𝑃𝑖) 𝑃𝑖 ngược lại

𝑃𝑖 = { - Bước 4.7: Ghi nhận hệ số đột biến thành công vào tập SCR

- Bước 4.6: Thay thế Pi theo công thức

µCR = (1 - c) × µCR + c × mean(SCR)

- Bước 5: Tính toán lại tham số lai ghép µCR theo công thức

w = wmax – i/N × (wmax – wmin)

- Bước 6: Hiệu chỉnh lại số cá thể lân cận theo công thức

- Bước 7: Tìm Pbest

Cải tiến chính của thuật toán A-DEM nằm trong các bước: 4.1, 4.2, 4.4, 4.7, 5,

A-DEM được trình bày trong Algorithm 4.2 dưới đây.

Algorithm 4.2. A-DEM Input: tmax: số thế hệ, dataset, N số cá thể ban đầu

Output phương án tốt nhất Pbest và makespan

Begin t = 0 Load and valid Dataset Pall  initialize(N) // khởi tạo quần thể gồm N cá thể {Pbest, makespan}  fbest(Pall) // tìm cá thể tốt nhất µCR = 0.5; wmin = 4; wmax = 10; w = 3 while(t