In this paper, an innovative four-layer heuristic is presented for scheduling multi-mode projects under multiple resource constraints. For this purpose, a biased-random sampling technique, a local search, a decomposition method, and an evolutionary search mechanism, each in a separate layer, are combined, with each layer passing its output to the next layer for improvement. The procedure has been designed based on the fact that what makes the scheduling of multi-mode projects hard to solve is a massive search space of modes compounded with the starting times of activities. That is why the procedure is aimed at balancing exploration versus exploitation in searching a massive search space. On the one hand, it exploits promising areas further and, on the other hand, it searches unexplored areas for expanding its range. Since the first layer provides an initial solution, and each of the other three layers can either improve the result of its previous layer or keep it unchanged, solutions never deteriorate and hence promising areas are exploited. Moreover, unexplored areas are searched effectively because each layer explores solution space differently than its previous layer. Based on whether or not an improvement each layer can make to the result of its previous layer, the effect of the corresponding layer on the performance of the procedure has been measured.
Accepté le :
DOI : 10.1051/ro/2019012
Mots-clés : Multi-mode recourse-constrained projects, Scheduling, heuristics, combinatorial optimization
@article{RO_2019__53_4_1309_0, author = {Zamani, Reza}, title = {An innovative four-layer heuristic for scheduling multi-mode projects under multiple resource constrains}, journal = {RAIRO - Operations Research - Recherche Op\'erationnelle}, pages = {1309--1330}, publisher = {EDP-Sciences}, volume = {53}, number = {4}, year = {2019}, doi = {10.1051/ro/2019012}, mrnumber = {3989211}, zbl = {1425.90054}, language = {en}, url = {http://www.numdam.org/articles/10.1051/ro/2019012/} }
TY - JOUR AU - Zamani, Reza TI - An innovative four-layer heuristic for scheduling multi-mode projects under multiple resource constrains JO - RAIRO - Operations Research - Recherche Opérationnelle PY - 2019 SP - 1309 EP - 1330 VL - 53 IS - 4 PB - EDP-Sciences UR - http://www.numdam.org/articles/10.1051/ro/2019012/ DO - 10.1051/ro/2019012 LA - en ID - RO_2019__53_4_1309_0 ER -
%0 Journal Article %A Zamani, Reza %T An innovative four-layer heuristic for scheduling multi-mode projects under multiple resource constrains %J RAIRO - Operations Research - Recherche Opérationnelle %D 2019 %P 1309-1330 %V 53 %N 4 %I EDP-Sciences %U http://www.numdam.org/articles/10.1051/ro/2019012/ %R 10.1051/ro/2019012 %G en %F RO_2019__53_4_1309_0
Zamani, Reza. An innovative four-layer heuristic for scheduling multi-mode projects under multiple resource constrains. RAIRO - Operations Research - Recherche Opérationnelle, Tome 53 (2019) no. 4, pp. 1309-1330. doi : 10.1051/ro/2019012. http://www.numdam.org/articles/10.1051/ro/2019012/
Machine Learning Heuristic for Solving Multi-Mode Resource-Constrained Project Scheduling Problems (2018).
, and ,Solving the multi-mode resource-constrained project scheduling problem with genetic algorithms. J. Oper. Res. Soc. 54 (2003) 614–626. | DOI | Zbl
, and ,Best-order crossover in an evolutionary approach to multi-mode resource-constrained project scheduling. Int. J. Comput. Inf. Syst. Ind. Manage. (IJCISIM) 6 (2014) 364–372.
and ,Combining monte-carlo and hyper-heuristic methods for the multi-mode resource-constrained multi-project scheduling problem. Inf. Sci. 373 (2016) 476–498. | DOI
, , , and ,Scheduling subject to resource constraints: classification and complexity. Discrete Appl. Math. 5 (1983) 11–24. | DOI | MR | Zbl
, and ,Heuristics for scheduling projects with resource restrictions and several resource-duration modes. Int. J. Prod. Res. 31 (1993) 2547–2558. | DOI
,Resource-constrained project scheduling by simulated annealing. Int. J. Prod. Res. 34 (1996) 2335–2351. | DOI | Zbl
,A new efficient simulated annealing algorithm for the resource-constrained project scheduling problem and its multiple mode version. Eur. J. Oper. Res. 149 (2003) 268–281. | DOI | MR | Zbl
and ,An efficient hybrid differential evolution based serial method for multimode resource-constrained project scheduling. KSCE J. Civil Eng. 20 (2016) 90–100. | DOI
and ,Multi-mode resource-constrained project scheduling using RCPSP and SAT solvers. Eur. J. Oper. Res. 213 (2011) 73–82. | DOI | MR | Zbl
and ,Multi-mode resource-constrained project-scheduling problem with renewable resources: new solution approaches. J. Bus. Econ. Res. (JBER) 11 (2013) 455–468. | DOI
, and ,An improved hybrid method for the multi-mode resource-constrained project scheduling problem. In: Proceedings of the Eighth International Conference on Engineering Computational Technology. Civil-Comp Press, Stirling, UK (2012). | DOI
, ,A decomposition-based genetic algorithm for the resource-constrained project-scheduling problem. Oper. Res. 55 (2007) 457–469. | DOI | Zbl
and ,Ant colony system: a cooperative learning approach to the traveling salesman problem, IEEE Trans. Evol. Comput. 1 (1997) 53–66. | DOI
and ,Activity networks: project planning and control by network models. New York Wiley(1977). | Zbl
,Shuffled frog-leaping algorithm: a memetic meta-heuristic for discrete optimization. Eng. Optim. 38 (2006) 129–154. | DOI | MR
, and ,A new heuristic optimization algorithm: harmony search. Simulation 76 (2001) 60–68. | DOI
, and ,A multi-threaded local search algorithm and computer implementation for the multi-mode, resource-constrained multi-project scheduling problem. Eur. J. Oper. Res. 256 (2017) 729–741. | DOI | MR | Zbl
,Genetic algorithms and tabu search: hybrids for optimization. Comput. Oper. Res. 22 (1995) 111–134. | DOI | Zbl
, and ,A competitive genetic algorithm for resource-constrained project scheduling. Nav. Res. Logist. 45 (1998) 733–750. | DOI | MR | Zbl
,Project scheduling with multiple modes: a genetic algorithm. Ann. Oper. Res. 102 (2001) 111–135. | DOI | MR | Zbl
,A combinatorial particle swarm optimization for solving multi-mode resource-constrained project scheduling problems. Appl. Math. Comput. 195 (2008) 299–308. | MR | Zbl
, , and ,Characterization and generation of a general class of resource-constrained project scheduling problems. Manage. Sci. 41 (1995) 1693–1702. | DOI | Zbl
, and ,PSPLIB – a project scheduling library. Eur. J. Oper. Res. 96 (1996) 205–216. | DOI | Zbl
and ,Local search for nonpreemptive multi-mode resource-constrained project scheduling. IIE Trans. 29 (1997) 987–999. | DOI
and ,New continuous-time and discrete-time mathematical formulations for resource-constrained project scheduling problems. Comput. Chem. Eng. 68 (2014) 96–106. | DOI
, and ,MILP formulations for single-and multi-mode resource-constrained project scheduling problems. Comput. Chem. Eng. 36 (2012) 369–385. | DOI
, and ,Recent developments in deterministic sequencing and scheduling: a survey. In: Deterministic Stochastic Scheduling. Springer, Dordrecht (1982) 35–73. | DOI | MR | Zbl
, and ,Parallel estimation of distribution algorithms. In: Estimation of Distribution Algorithms Springer (2002) 129–145. | DOI | Zbl
, and ,A two-level genetic algorithm for the multi-mode resource-constrained project scheduling problem. Int. J. Syst. Appl. Eng. Dev. 5 (2011) 271–278.
,An automatic algorithm selection approach for the multi-mode resource-constrained project scheduling problem. Eur. J. Oper. Res. 233 (2014) 511–528. | DOI | MR | Zbl
and ,Mode-based versus activity-based search for a nonredundant resolution of the multimode resource-constrained project scheduling problem. Math. Prob. Eng. 2017 (2017). | DOI | MR | Zbl
, and ,A path-relinking algorithm for the multi-mode resource-constrained project scheduling problem. Comput. Oper. Res. 92 (2018) 145–154. | DOI | MR | Zbl
, and ,Bees algorithm for multi-mode, resource-constrained project scheduling in molding industry. Comput. Ind. Eng. 112 (2017) 187–196. | DOI
and ,Experimental evaluation of agent-based approaches to solving multi-mode resource-constrained project scheduling problem. Cybern. Syst. (2018) 1–21.
,Hybridization of genetic algorithm and fully informed particle swarm for solving the multi-mode resource-constrained project scheduling problem. Eng. Optim. 49 (2017) 513–530. | DOI | MR
, and ,Two approaches to problems of resource allocation among project activities – a comparative study. J. Oper. Res. Soc. 31 (1980) 711–723. | MR | Zbl
,A hybrid estimation of distribution algorithm with random walk local search for multi-mode resource-constrained project scheduling problems. Int. J. Comput. Trends Tech (IJCTT) 8 (2014) 57–64. | DOI
and ,Hybrid optimization method for large-scale multimode resource-constrained project scheduling problem. J. Manage. Eng. 32 (2016) 04016020. | DOI
and ,An exact algorithm for project scheduling with multiple modes. OR Spectr. 19 (1997) 195–203. | DOI | MR | Zbl
, and ,Multi-mode resource-constrained project scheduling by a simple, general and powerful sequencing algorithm. Eur. J. Oper. Res. 107 (1998) 431–450. | DOI | Zbl
and ,Network decomposition techniques for resource-constrained project scheduling. Oper. Res. Soc. 53 (2002) 405–414. | DOI | Zbl
,Modelling and solving multi-mode resource-constrained project scheduling. In: International Conference on Principles and Practice of Constraint Programming. Springer (2016). | MR
and ,Resource-constrained project scheduling with time-resource tradeoffs: the nonpreemptive case. Manage. Sci. 28 (1982) 1197–1210. | DOI | Zbl
,An integer programming approach to the multimode resource-constrained multiproject scheduling problem. J. Schedul. 19 (2016) 295–307. | DOI | MR | Zbl
, , and ,Two-phase genetic local search algorithm for the multimode resource-constrained project scheduling problem. IEEE Trans. Evol. Comput. 13 (2009) 848–857. | DOI
and ,A population-based approach to the resource-constrained project scheduling problem. Ann. Oper. Res. 131 (2004) 305–324. | DOI | MR | Zbl
, and ,Justification and RCPSP: a technique that pays. Eur. J. Oper. Res. 165 (2005) 375–386. | DOI | Zbl
, and ,Using resource scarceness characteristics to solve the multi-mode resource-constrained project scheduling problem, J. Heuristics 17 (2011) 705–728. | DOI | Zbl
and ,An experimental investigation of metaheuristics for the multi-mode resource-constrained project scheduling problem on new dataset instances, Eur. J. Oper. Res. 235 (2014) 62–72. | DOI | Zbl
and ,An effective shuffled frog-leaping algorithm for multi-mode resource-constrained project scheduling problem, Inf. Sci. 181 (2011) 4804–4822. | DOI | MR | Zbl
and ,An effective estimation of distribution algorithm for the multi-mode resource-constrained project scheduling problem, Comput. Oper. Res. 39 (2012) 449–460. | DOI
and ,Solving multimode resource-constrained project scheduling problems using an organizational evolutionary algorithm. In: Proceedings of the 18th Asia Pacific Symposium on Intelligent and Evolutionary Systems. Springer (2015). | DOI
and ,A hybrid decomposition procedure for scheduling projects under multiple resource constraints. Oper. Res. 11 (2011) 93–111.
,A polarized adaptive schedule generation scheme for the resource-constrained project scheduling problem. RAIRO: OR 46 (2012) 23–39. | DOI | Numdam | MR | Zbl
,An effective mirror-based genetic algorithm for scheduling multi-mode resource constrained projects. Comput. Ind. Eng. 127 (2019) 914–924. | DOI
,Ant colony optimization for multimode resource-constrained project scheduling. J. Manage. Eng. 28 (2012) 150–159. | DOI
,Cité par Sources :