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 hợp riêng của đồ thị dạng Outtree và Intree khi số nút nguồn =1.
Outtree
Intree
Fork
Join
Chains
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 eijE) 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 VI PHÂN VÀ PHƯƠNG PHÁP CUCKOO SEARCH
Bài toán Real-RCPSP bổ sung thêm ràng buộc về thời gian thay đổi theo 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ụ
1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | |
Thời gian | 4 | 6 | 3 | 5 | 3 | 7 | 4 | 5 | 6 | 4 |
Có thể bạn quan tâm!
-
Phương Pháp Tái Thiết Lập Tài Nguyên Thực Hiện -
Đánh Giá Chất Lượng Lời Giải Của Thuật Toán -
Xếp Loại Bài Toán Real-Rcpsp Thông Qua Phân Loại Graham -
Ý Tưởng Của Phương Pháp Thích Nghi -
Đánh Giá Chất Lượng Lời Giải Của Thuật Toán -
Đánh Giá Chất Lượng Lời Giải Của Thuật Toán
Xem toàn bộ 156 trang tài liệu này.
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 | ||||
g1 | h1 | g2 | h2 | g3 | h3 | |
L1 | × | 1 | × | 3 | × | 4 |
L2 | × | 2 | × | 5 |
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
Kỹ năng | Thời gian thực hiện theo mức kỹ năng | |||||
h1 | h2 | h3 | h4 | h5 | ||
W1 | g1 | 4 | 3 | 3 | 2 | 2 |
W2 | g2 | 5 | 4 | 4 | ||
W3 | g1 | 3 | 3 | 2 | 2 | |
W4 | g3 | 4 | 3 | |||
W5 | g2 | 3 | 3 | 2 | ||
W6 | g2 | 7 | 6 | 5 | ||
W7 | g1 | 4 | 3 | 3 | 2 | 2 |
W8 | g1 | 5 | 4 | 4 | 3 | 3 |
W9 | g3 | 6 | 5 | |||
W10 | g2 | 4 | 3 | 3 |
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:
W1 | W2 | W3 | W4 | W5 | W6 | W7 | W8 | W9 | W10 | |
Tài nguyên | 2 | 1 | 2 | 2 | 1 | 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ụ
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 dưới đây.
Time
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.