A Hybrid Estimation of Distribution Algorithm with Random Walk local Search for Multi-mode Resource-Constrained Project Scheduling problems
 | International Journal of ComputerTrends and Technology (IJCTT) |  |
| © 2014 by IJCTT Journal | ||
| Volume-8 Number-2 | ||
| Year of Publication : 2014 | ||
| Authors : Omar S. Soliman , Elshimaa A. R. Elgendi | ||
| DOI : 10.14445/22312803/IJCTT-V8P111 |
Omar S. Soliman , Elshimaa A. R. Elgendi . "A Hybrid Estimation of Distribution Algorithm with Random Walk local Search for Multi-mode Resource-Constrained Project Scheduling problems". International Journal of Computer Trends and Technology (IJCTT) 8(2):57-64, February 2014. ISSN:2231-2803. www.ijcttjournal.org. Published by Seventh Sense Research Group.
Abstract -
Multi-mode resource-constrained project scheduling problems (MRCPSPs) are classified as NP-hard problems, in which a task has different execution modes characterized by different resource requirements. Estimation of distribution algorithm (EDA) has shown an effective performance for solving such real-world optimization problems but it fails to find the desired optima. This paper integrates a novel hybrid local search technique with EDA to enhance their local search ability. The new local search is based on delete-then-insert operator and a random walk (DIRW) to enhance exploitation abilities of EDA in the neighborhoods of the search space. The proposed algorithm is capable to explore and exploit the search mechanism in the search space through its outer and inner loops. The proposed algorithm is tested and evaluated using benchmark test problems of the project scheduling problem library PSPLIB. Simulation results of the proposed algorithm are compared with the classical EDA algorithm. The obtained results showed that the effectiveness of the proposed algorithm and outperformed the compared EDA algorithm
References
[1] R Kolisch and A Drexl, Local search for nonpreemptive multi-mode resource-constrained project scheduling, Iie Trans, 29, 1997, 987–999.
[2] S Hartmann, Project Scheduling with Multiple Modes: A Genetic Algorithm, Ann Oper Res, 102, 2001, 111–135.
[3] J Alcaraz, C Maroto and R Ruiz, Solving the Multi-Mode Resource-Constrained Project Scheduling Problem with Genetic Algorithms, J Oper Res Soc, 54(6), 2003, 614–626.
[4] J Józefowska,M Mika, R Rózycki, G Waligóra and J Weglarz, Simulated annealing for multi-mode resource-constrained project scheduling, Ann of Oper Res, 102, 2001, 137–155.
[5] K Bouleimen and H Lecocq, A new efficient simulated annealing algorithm for the resource-constrained project scheduling problem and its multiple mode version, Eur J Oper Res, 149(2), 2003, 268–281.
[6] B Jarboui, N Damak, P Siarry and A Rebai, A combinatorial particle swarm optimization for solving multi-mode resource-constrained project scheduling problems, Appl Math Comput, 195(1), 2008, 299–308.
[7] V Van Peteghem and M Vanhoucke, An Artificial Immune System for the Multi-Mode Resource-Constrained Project Scheduling Problem, vol. 5482 of Lect Notes Comput Sc. Springer Berlin /Heidelberg, 2009, 85–96.
[8] T Wauters, K Verbeeck, G Vanden Berghe and P De Causmaecker, A multi-agent learning approach for the multi-mode resource-constrained project scheduling problem, Decker, ; Sichman, ; Sierra, ; Castelfranchi, (eds.), Autonomous Agents and Multiagent Systems, Hungary, 10-15 May 2009, Proc. of 8th Int. Conf. on Autonomous Agents and Multiagent Systems (AAMAS 2009), pages 1-8, International Foundation for Autonomous Agents and Multiagent Systems (www.ifaamas.org)
[9] N Damak, B Jarboui, P Siarry and T Loukil, Differential evolution for solving multi-mode resource-constrained project scheduling problems, Comput Oper Res, 36(9), 2009, 2653 – 2659.
[10] S Elloumi and P Fortemps, A hybrid rank-based evolutionary algorithm applied to multi-mode resource-constrained project scheduling problem, Eur J Oper Res., 205(1), 2010, 31 – 41.
[11] M Ranjbar, B De Reyck and F Kianfar, A hybrid scatter search for the discrete time/resource trade-off problem in project scheduling, Eur J Oper Res., 193(1), 2009, 35–48.
[12] L Y Tseng and S C Chen, Two-phase genetic local search algorithm for the multimode resource-constrained project scheduling problem, Trans Evol Comp., 13, 2009, 848 –857.
[13] A Lova, P Tormos, M Cervantes and F Barber, An efficient hybrid genetic algorithm for scheduling projects with resource constraints and multiple execution modes, Int J Pprod Econ., 117(2), 2009, 302–316.
[14] V Van Peteghem and M Vanhoucke, A genetic algorithm for the preemptive and non-preemptive multi-mode resource-constrained project scheduling problem, Eur J Oper Res., 201(2), 2010, 409 – 418.
[15] L Wang and C Fang, An effective shuffled frog-leaping algorithm for multi-mode resource-constrained project scheduling problem, Inform Sciences, 181(20), 2011, 4804 – 4822, Special Issue on Interpretable Fuzzy Systems.
[16] L Wang and C Fang, An effective estimation of distribution algorithm for the multi-mode resource-constrained project scheduling problem, Comput Oper Res., 39(2), 2012, 449 – 460.
[17] P. Larrañaga and J.A. Lozano, Estimation of distribution algorithms: a new tool for evolutionary computation. Genetic algorithms and evolutionary computation (Kluwer Academic Publishers, 2002).
[18] FB Talbot, Resource-Constrained Project Scheduling with Time-Resource Tradeoffs: The Nonpreemptive Case, Manage Sci., 28(10), 1982, 1197–1210.
[19] A Sprecher, S Hartmann and A Drexl, An exact algorithm for project scheduling with multiple modes, OR Spektrum, 19(3), 1997, 195–203.
[20] R Kolisch, A Sprecher. PSPLIB-a project scheduling problem library. Eur J Oper Res, 96(1), 1997, 205–16.
Keywords
Multi-mode resource-constrained project scheduling problems, Estimation of distribution algorithm, Local search, Random walk.