THUẬT TOÁN R-PSO GIẢI BÀI TOÁN LẬP LỊCH THỰC HIỆN DỰ ÁN VỚI TÀI NGUYÊN GIỚI HẠN
278 lượt xemDOI:
https://doi.org/10.54939/1859-1043.j.mst.CSCE5.2021.71-82Từ khóa:
Tính toán tiến hóa; Tối ưu bày đàn; Phương pháp tối ưu; Bài toán MS-RCPSP.Tóm tắt
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ỹ có nhiều ứng dụng trong khoa học và thực tiễn. Mục tiêu của bài toán này là tìm phương án lịch biểu tốt nhất trong việc thực hiện các dự án, các luồng công việc. Việc đánh giá kết quả bài toán dựa trên yếu tố thời gian thực hiện hoặc chi phí thực hiện hoặc cả hai yếu tố thời gian và chi phí (đa mục tiêu). Do vậy, việc nghiên cứu giải bài toán MS-RCPSP là quan trọng, giúp nâng cao hiệu quả vận hành của các luồng công việc, các dây chuyền sản xuất,... MS-RCPSP đã được chứng minh là bài toán thuộc lớp NP-Khó nên không thể tìm được lời giải trong thời gian đa thức mà cần sử dụng các phương pháp cận tối ưu để tìm được nghiệm đủ tốt. Hiện đã có nhiều nhà khoa học nghiên cứu giải bài toán này bằng các phương pháp tiến hóa như GA, Greedy, Ant,... Tuy nhiên, khi áp dụng các thuật toán tiến hóa với không gian lời giải lớn, thuật toán thường rơi vào các cực trị địa phương, nên sẽ không tìm ra được các nghiệm tốt hơn. Bài báo này sẽ nghiên cứu một phương pháp mới để giải bài toán MS-RCPSP dựa trên thuật toán tối ưu bầy đàn bằng cách sử dụng kỹ thuật tái cấp phát tài nguyên thực hiện tác vụ (Reallocate) để mở rộng không gian tìm kiếm, giúp tăng khả năng tìm được các lời giải tốt hơn và tránh được các vùng cực trị địa phương. Để kiểm chứng thuật toán, bài báo tiến hành thực nghiệm trên bộ dữ liệu chuẩn iMOPSE, các kết quả thực nghiệm cho thấy thuật toán đề xuất mới mang lại hiệu quả tốt hơn so với một số thuật toán trước đây.
Tài liệu tham khảo
[1]. A.H. Hosseinian, V. Baradaran, "An Evolutionary Algorithm Based on a Hybrid Multi-Attribute Decision Making Method for the Multi-Mode Multi-Skilled Resource-Constrained Project Scheduling Problem.", Journal of Optimization in Industrial Engineering, 12.2, pp. 155-178,2019.
[2]. 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.
[3]. A.H. Hosseinian, V. Baradaran, "P-GWO and MOFA: two new algorithms for the MSRCPSP with the deterioration effect and financial constraints (case study of a gas treating company).", Applied Intelligence, 50 , pp. 2151-2176 , 2020.
[4]. F. Black, and M. Scholes, “The pricing of options and corporate liabilities”, Journal of Political Economy, 81, pp. 637-654, 1973
[5]. H. Li, K. Womer, “Stochastic Resource-Constrained Project Scheduling and Its Military Applications”, IEEE Trans Computer, 65(12), pp. 3702–3712, 2016.
[6]. 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.
[7]. J. Kennedy, R. Eberhart, "Particle Swarm Optimization", IEEE International Conference on Neural Networks, 1995.
[8]. M. Skowroński, P.B. Myszkowski, P. Kwiatek, M. Adamski, "Tabu Search approach for Multi–Skill Resource–Constrained Project Scheduling Problem", Annals of Computer Science and Information Systems, Volume 1, Proceedings of the 2013 Federated Conference on Computer Science and Information Systems, pp. 153-158, 2013.
[9]. O. Sinnen, “Task scheduling for parallel systems”, Published by JohnWiley & Sons, Inc., Hoboken, New Jersey, Vol 60, 2007.
[10]. P.B. Myszkowski, M. Laszczyk, I. Nikulin, M. Skowro, “iMOPSE: a library for bicriteria optimization in Multi-Skill Resource-Constrained Project Scheduling Problem”, Soft Computing Journal, 23: 32397, 2019.
[11]. P.B. Myszkowski, M. Skowroński, "Specialized genetic operators for Multi–Skill Resource–Constrained Project Scheduling Problem", 19th International Conference on Soft Computing – Mendel 2013, pp. 57-62, 2013.
[12]. P.B. Myszkowski, M. Skowroński, L. Olech, K. Oślizło, "Hybrid Ant Colony Optimization in solving Multi–Skill Resource–Constrained Project Scheduling Problem", Soft Computing Journal, Volume 19, Issue 12, pp.3599–3619, 2015.
[13]. 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.
[14]. R. Klein: “Scheduling of Resource-Constrained Projects”, Springer Science & Business Media, Vol. 10, 2012.
[15]. R. Kolisch, A. Sprecher, “PSPLIB-a project scheduling problem library: OR software-ORSEP operations research software exchange program.”, European journal of operational research, 96(1), pp.205-216, 1997.
[16]. 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.
[17]. W. Guo, J.H. Park, L.T. Yang, A.V. Vasilakos, N. Xiong, G. Chen, "Design and Analysis of a MST-Based Topology Control Scheme with PSO for Wireless Sensor Networks,", 2011 IEEE Asia-Pacific Services Computing Conference, Jeju Island, pp. 360-367, 2011. doi: 10.1109/APSCC.2011
[18]. 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
[19]. H.N.S. Krishnamoorthy, Z. Jacob, E. Narimanov, I. Kretzschmar, V.M. Menon, Science 336 (2012) 205.
