Thuật toán tiến hóa cho bài toán lập lịch dự án Earliness-Tardiness
Abstract
Hoàn thành quá sớm hoặc quá muộn có thể gây thiệt hại cho dự án. Ví dụ, trong việc vận chuyển hàng hóa đến cảng biển, nếu hàng hóa đến quá sớm, sẽ mất thời gian và chi phí để lưu lại tại bến tàu. Ở trường hợp khác, việc vận chuyển quá muộn sẽ làm giảm chất lượng sản phẩm và phá vỡ hợp đồng. Mục tiêu của bài báo này là giảm thiểu tình trạng các dự án được hoàn thành quá trễ hay quá sớm. Đầu tiên, bài báo giới thiệu tóm tắt một số nghiên cứu liên quan, qua đó chỉ ra vai trò và ứng dụng thực tế của bài toán MS-RCPSP (Multi-Skill Resource Constrained Project Scheduling Problem) và hai yếu tố Độ sớm và Độ trễ trong bài toán lập lịch. Đồng thời, tác giả nêu bật đóng góp mới của nghiên cứu này, đó là đề xuất một bài toán mới tên là E-RCPSP (Earliness tardiness MS-RCPSP). Bài toán mới này là bài toán đầu tiên trong họ MS-RCPSP đặt tổng Độ sớm và Độ trễ thành hàm mục tiêu, điều chưa từng xuất hiện trong các nghiên cứu trước đây về MS-RCPSP. Sau đó, bài báo giới thiệu mô hình toán học của bài toán E-RCPSP bao gồm hàm mục tiêu, các thành phần của dự án và các ràng buộc, đặc biệt là ràng buộc về thời gian. Để giải quyết bài toán E-RCPSP, bài báo xây dựng hai thuật toán gần đúng dựa trên thuật toán tiến hóa GA (Genetic Algorithm) và thuật toán tiến hóa DE (Differential Evolution). Phần cuối của bài báo trình bày những thực nghiệm trên tập dữ liệu chuẩn iMOPSE nhằm kiểm chứng và so sánh hiệu năng của hai thuật toán đề xuất.
References
H. Najafzad, H. Davari-Ardakani, R. Nemati-Lafmejani, "Multi-skill project scheduling problem under time-of-use electricity tariffs and shift differential payments", In Energy Journal, vol. 168, pp. 619-636, Elsevier, 2019.
P.B. Myszkowski, M. Laszczyk, I. Nikulin, M. Skowro, "iMOPSE: a library for bicriteria optimization in Multi-Skill
Resource-Constrained Project Scheduling Problem", In Soft Computing Journal, 23: 32397, 2019.
P.B. Myszkowski, M. Skowro´nski, L. Olech, K. O´ slizło, " Hybrid Ant Colony Optimization in solving Multi–Skill
Resource–Constrained Project Scheduling Problem", In Soft Computing Journal, Volume 19, Issue 12, pp.3599–3619, 2015.
S. Javanmard, B. Afshar-Nadjafi, S.T. Niaki, "Preemptive multi-skilled resource investment project scheduling prob lem: Mathematical modeling and solution approaches," In Computers & Chemical Engineering, 96, pp. 55-68, 2017.
Skowronski M., Myszkowski P.B., " Specialized genetic operators for Multi–Skill Resource–Constrained Project
Scheduling Problem", In 19th Inter, Conference on Soft Computing- Mendel 2013, pp. 57-62, 2013
Y. Khoshjahan, A.A. Najafi, B.A. Nadjafi, "Resource constrained project scheduling problem with discounted
earliness-tardiness penalties: Mathematical modeling and solving procedure", In Computers & Industrial Engineering, 2013.
V. A. Strusevich, K. Rustogi, "Scheduling with Times Changing Effects and Rate-Modifying Activities", In
Springer International Publishing, 2017.
Kramer, A., Subramanian, A., " A unified heuristic and an annotated bibliography for a large class of earliness–tardiness scheduling problems", In Journal of Scheduling, vol. 22, 2019.
A.H. Hosseinian, V. Baradaran, " An Evolutionary Algorithm Based on a Hybrid Multi-Attribute Decision Mak
ing Method for the Multi-Mode Multi-Skilled Resource Constrained Project Scheduling Problem", In 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", In Journal of Industrial and Systems Engineering, pp. 72-99, 12.2019.
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)", In Applied Intelligence, 50, pp. 2151-2176, 2020.
Younis, Muhanad Tahrir, and Shengxiang Yang, "Hybrid meta-heuristic algorithms for independent job scheduling in grid computing", In Applied soft computing, vol.72, pp. 498 517, 2018.
Maghsoudlou, Hamidreza, Behrouz Afshar-Nadjafi, and Seyed Taghi Akhavan Niaki," Multi-skilled project schedul ing with level-dependent rework risk; three multi-objective mechanisms based on cuckoo search", In Applied Soft Computing, vol. 54, pp. 46-61, 2017.
Bibiks, Kirils, et al.," Improved discrete cuckoo search for the resource-constrained project scheduling problem", In Applied Soft Computing, vol. 69, pp. 493-503, 2018.
Zhu, Lei, Jian Lin, Zhou-Jing Wang, "A discrete oppositional multi-verse optimization algorithm for multi-skill resource constrained project scheduling problem", In Applied Soft Computing, vol. 85, 2019.
Mario Vanhoucke, Erik Demeulemeester, and Willy Herroelen," An Exact Procedure for the Resource-Constrained In Kluwer Academic Publishers. Manufactured in The Netherlands, 2001.
Maarten Otten, Aleida Braaksma, Richard J. Boucherie, "Minimizing Earliness/Tardiness costs on multiple machines with an application to surgery scheduling", Operations Research for Health Care, vol. 22, 2019.
S. Akande, G. Ajisegiri, " Three classes of Earliness Tardiness (E/T) scheduling problems", In Fuel Communica
tions, vol. 10, 2022.
S. Akande, Ajisegiri GO, " Single machine multi-criteria scheduling problem: total completion time, maximum lateness, and maximum earliness performance measures", In International Journal of Planning and Scheduling, vol. 3, 2021.
K.Price, R.Storn, J.Lampinen: "Differential Evolution- A Practical Approach to Global Optimization", In Springer, Berlin, Germany, 2005.
