Nội dung được dịch bởi AI, chỉ mang tính chất tham khảo
Tối ưu hóa bầy kiến cho lập lịch dự án có giới hạn về tài nguyên
Tóm tắt
Bài báo trình bày một phương pháp tối ưu hóa bầy kiến (ACO) dành cho vấn đề lập lịch dự án có giới hạn về tài nguyên (RCPSP). Nhiều tính năng mới thú vị cho ACO nói chung đã được đề xuất và đánh giá. Cụ thể, việc sử dụng kết hợp hai phương pháp đánh giá pheromone bởi các con kiến để tìm ra giải pháp mới, sự thay đổi ảnh hưởng của các quy tắc hiển thị lên quyết định của các con kiến trong quá trình thực hiện thuật toán và tùy chọn mà một con kiến tinh hoa quên đi giải pháp tốt nhất đã tìm thấy, đã được nghiên cứu. Chúng tôi đã kiểm tra thuật toán ACO trên một bộ các bài toán chuẩn lớn từ Thư viện Lập lịch Dự án. So với một số heuristics khác cho RCPSP, bao gồm thuật toán di truyền, làm nguội giả, tìm kiếm tabu và các phương pháp lấy mẫu khác, thuật toán của chúng tôi cho kết quả tốt nhất trung bình. Đối với gần một phần ba số bài toán chuẩn không được biết đến với giải pháp tối ưu trước đó, thuật toán đã có thể tìm ra các giải pháp tốt nhất mới.
Từ khóa
#Tối ưu hóa bầy kiến #Thuật toán lập lịch #Kiểm tra benchmark #Thuật toán di truyền #Làm nguội giả #Phương pháp lấy mẫu #Thư viện #Vấn đề NP-khó #Phương pháp lặpTài liệu tham khảo
van der zwaan, 1999, ant colony optimization for job shop scheduling, Third Workshop on Genetic Algorithms and Artificial Life
valls, 0, “ Resource-constrained project scheduling A critical activity reordering heuristic ” unpublished
10.1002/(SICI)1520-6750(200004)47:3<201::AID-NAV2>3.0.CO;2-L
nonobe, 1999, Formulation and tabu search algorithm for the resource constrained project scheduling problem (RCPSP)
möhring, 2000, Solving Project Scheduling Problems by Minimum Cut Computations
michels, 1999, an ant system for the shortest common supersequence problem, New Ideas in Optimization, 51
ulusoy, 1989, heuristic performance and network/resource characteristics in resource-constrained project scheduling, J Oper Res Soc, 40, 1145, 10.1057/jors.1989.196
10.1016/S0167-739X(00)00043-1
stützle, 1998, an ant approach for the flow shop problem, Proc 6th Eur Congr Intelligent Techniques and Soft Computing, 3, 1560
10.1080/05695557808975212
10.1109/4235.585892
10.1109/3477.484436
10.1007/s001860000091
elmaghraby, 1977, Activity Networks
10.1002/(SICI)1520-6750(199810)45:7<733::AID-NAV5>3.3.CO;2-7
hartmann, 1999, Self-adapting genetic algorithm with an application to project scheduling
10.1016/S0377-2217(99)00485-3
10.1016/S0305-0548(97)00055-5
iredi, 2001, bi-criterion optimization with multi colony ant algorithms, First International Conference on Evolutionary Multi-Criterion Optimization (EMO 01), 1993, 359, 10.1007/3-540-44719-9_25
10.1016/S0377-2217(99)00347-1
10.1016/S0377-2217(98)00204-5
10.1007/3-540-45561-2_28
10.1007/BF01719262
bouleimen, 1998, A new efficient simulated annealing algorithm for the resource constrained project scheduling problem
10.1287/mnsc.21.8.944
colorni, 1994, ant system for job-shop scheduling, Belg J Oper Res Stat Comput Sci, 34, 39
10.1007/3-540-45365-2_50
dorigo, 1992, Optimization learning and natural algorithms
den besten, 2000, Ant Colony Optimization for the Total Weighted Tardiness Problem, 1917, 611
10.1142/S0219525998000119
10.1109/CEC.1999.782657
10.1109/CEC.1999.782653
10.1007/978-3-642-50296-5
10.1016/0377-2217(95)00357-6
10.1016/0272-6963(95)00032-1
kolisch, 1999, heuristic algorithms for solving the resource-constrained project scheduling problem: classification and computational analysis, Handbook on Recent Advances in Project Scheduling, 197, 10.1007/978-1-4615-5533-9_9
10.1002/(SICI)1520-6750(199602)43:1<23::AID-NAV2>3.0.CO;2-P
kolisch, 1996, psplib – a project scheduling problem library, Eur J Oper Res, 96, 205, 10.1016/S0377-2217(96)00170-1
kolisch, 1999, benchmark instances for project scheduling problems, Handbook on Recent Advances in Project Scheduling, 147, 10.1007/978-1-4615-5533-9_7