Thuật toán Ro-CS giải bài toán lập lịch với tài nguyên giới hạn

The Ro-CS Algorithm solving the MS-RCPSP Problem

  • Đặng Quôc Hữu Trường Đại học Thương mại, Hà Nội, Việt Nam
  • Nguyen The Loc
Keywords: Evolutionary Computing, Optimization, MS-RCPSP problem, Tính toán tiến hóa, thuật toán cận tối ưu, bài toán MS-RCPSP

Abstract

Bài báo đề xuất phương pháp tìm lời giải cho Bài toán MS-RCPSP (Multi Skill-Resource Constrained Project Scheduling Problem). MS-RCPSP đã được chứng minh là bài toán NP-Khó, do vậy cần sử dụng các phương pháp tính toán tiến hóa, cận tối ưu nhằm tìm được lời giải phù hợp trong thời gian chấp nhận được. Thuật toán đề xuất là thuật toán lai ghép giữa thuật toán Cuckoo Search (CS) và kỹ thuật Rotate giúp mở rộng không gian tìm kiếm sau mỗi thế hệ tiến hóa, nhằm tăng khả năng tìm được lời giải tốt hơn. Thuật toán mới gọi là Ro-CS có khả năng áp dụng để tìm lời giải cho bài toán MS-RCPSP. Để kiểm chứng thuật toán Ro-CS, bài báo tiến hành thực nghiệm trên bộ dữ liệu chuẩn iMOPSE, kết quả thực nghiệm được tổng hợp, đánh giá, so sánh, phân tích cho thấy tính hiệu quả của thuật toán đề xuất.

References

A. Christian, S. Demassey, E. Néron, “Resource Constrained Project Scheduling: Models, Algorithms, Extensions and Applications”, ISBN 978-1-84821-034-9, 2008.

R. Klein: “Scheduling of Resource-Constrained Projects”, Springer Science & Business Media, Vol. 10, 2012.

Huu Dang Quoc, Loc Nguyen The, Cuong Nguyen Doan, "Naixue Xiong: Effective Evolutionary Algorithm for Solving the Real-Resource-Constrained Scheduling Problem," Journal of Advanced Transportation, vol. 2020, Article ID 8897710, 11 pages, 2020

P.B. Myszkowski, M. Skowronski, L. Olech, K. O ´ sliz ´ ło, "Hybrid Ant Colony Optimization in solving Multi–Skill Resource–Constrained Project Scheduling Problem", Soft Computing Journal, Volume 19, Issue 12, pp.3599–3619,

P.B. Myszkowski, M. Laszczyk, I. Nikulin, M. Skowro, “iMOPSE: a library for bicriteria optimization in MultiSkill Resource-Constrained Project Scheduling Problem”, Soft Computing Journal, 23: 32397, 2019.

P.B. Myszkowski, M.E. Skowronski, K.Sikora, “A new benchmark dataset for Multi-Skill Resource-Constrained Project Scheduling Problem”, Computer Science and Information Systems, ACSIS, Vol. 5, pp. 129–138, 2015. DOI: 10.15439/2015F273.

A.H. Hosseinian, V. Baradaran, "An Evolutionary Algorithm Based on a Hybrid Multi-Attribute Decision Making Method for the Multi-Mode Multi-Skilled ResourceConstrained Project Scheduling Problem.", Journal of Optimization in Industrial Engineering, 12.2, pp. 155-178,2019.

A.H. Hosseinian, V. Baradaran, "Detecting communities of workforces for the multi-skill resource-constrained project scheduling problem: A dandelion solution approach.", Journal of Industrial and Systems Engineering, pp. 72-99, 12.2019.

S. Javanmard, B. Afshar-Nadjafi, S.T. Niaki, "Preemptive multi-skilled resource investment project scheduling problem: Mathematical modeling and solution approaches.", Computers & Chemical Engineering, 96, pp. 55-68, 2017.

H. Najafzad, H. Davari-Ardakani, R. Nemati-Lafmejani, "Multi-skill project scheduling problem under time-of- use electricity tariffs and shift differential payments.", Energy Journal, vol. 168, pp. 619-636, Elsevier,2019.

Huu Dang Quoc, Loc Nguyen The, Cuong Nguyen Doan, Toan Phan Thanh, Naixue Xiong, “Intelligent Differential Evolution Scheme for Network Resources in IoT”, Scientific Programming (IF:1.28, Q3), Volume 2020, Article ID 8860384 | 12, 2020. DOI: 10.1155/2020/8860384

X.S. Yang, “Nature-Inspired Metaheuristic Algorithms”, Luniver Press, ISBN-13: 978-1-905986-28-6, 2010.

X.S. Yang, S. Deb, “Cuckoo search via Lévy flights”, Proc. of World Congress on Nature & Biologically Inspired Computing (NaBIC 2009), USA, pp. 210-214, 2009.

Bộ dữ liệu iMOPSE và công cụ GARunner: http://imopse.ii.pwr.wroc.pl/download.html

Published
2022-06-30