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.

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.

Reçu le :
Accepté le :
DOI : 10.1051/ro/2019012
Classification : 90B50, 90B35, 90B40, 90.08, 68R05
Mots-clés : Multi-mode recourse-constrained projects, Scheduling, heuristics, combinatorial optimization
Zamani, Reza 1

1 
@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://archive.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://archive.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://archive.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://archive.numdam.org/articles/10.1051/ro/2019012/

P.I. Adamu, M.C. Agarana and H.I. Okagbue, Machine Learning Heuristic for Solving Multi-Mode Resource-Constrained Project Scheduling Problems (2018).

J. Alcaraz, C. Maroto and R. Ruiz, Solving the multi-mode resource-constrained project scheduling problem with genetic algorithms. J. Oper. Res. Soc. 54 (2003) 614–626. | DOI | Zbl

A. Andreica and C. Chira, 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.

S. Asta, D. Karapetyan, A. Kheiri, E. Özcan and A.J. Parkes, Combining monte-carlo and hyper-heuristic methods for the multi-mode resource-constrained multi-project scheduling problem. Inf. Sci. 373 (2016) 476–498. | DOI

J. Blazewicz, J.K. Lenstra and A.R. Kan, Scheduling subject to resource constraints: classification and complexity. Discrete Appl. Math. 5 (1983) 11–24. | DOI | MR | Zbl

F.F. Boctor, Heuristics for scheduling projects with resource restrictions and several resource-duration modes. Int. J. Prod. Res. 31 (1993) 2547–2558. | DOI

F.F. Boctor, Resource-constrained project scheduling by simulated annealing. Int. J. Prod. Res. 34 (1996) 2335–2351. | DOI | Zbl

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 (2003) 268–281. | DOI | MR | Zbl

M.-Y. Cheng and D.-H. Tran, An efficient hybrid differential evolution based serial method for multimode resource-constrained project scheduling. KSCE J. Civil Eng. 20 (2016) 90–100. | DOI

J. Coelho and M. Vanhoucke, Multi-mode resource-constrained project scheduling using RCPSP and SAT solvers. Eur. J. Oper. Res. 213 (2011) 73–82. | DOI | MR | Zbl

S. Colak, A. Agarwal and S. Erenguc, Multi-mode resource-constrained project-scheduling problem with renewable resources: new solution approaches. J. Bus. Econ. Res. (JBER) 11 (2013) 455–468. | DOI

A. Csébfalvi, E. Szendrői, 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

D. Debels and M. Vanhoucke, A decomposition-based genetic algorithm for the resource-constrained project-scheduling problem. Oper. Res. 55 (2007) 457–469. | DOI | Zbl

M. Dorigo and L.M. Gambardella, Ant colony system: a cooperative learning approach to the traveling salesman problem, IEEE Trans. Evol. Comput. 1 (1997) 53–66. | DOI

S.E. Elmaghraby, Activity networks: project planning and control by network models. New York Wiley(1977). | Zbl

M. Eusuff, K. Lansey and F. Pasha, Shuffled frog-leaping algorithm: a memetic meta-heuristic for discrete optimization. Eng. Optim. 38 (2006) 129–154. | DOI | MR

Z.W. Geem, J.H. Kim and G. Loganathan, A new heuristic optimization algorithm: harmony search. Simulation 76 (2001) 60–68. | DOI

M.J. Geiger, 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

F. Glover, J.P. Kelly and M. Laguna, Genetic algorithms and tabu search: hybrids for optimization. Comput. Oper. Res. 22 (1995) 111–134. | DOI | Zbl

S. Hartmann, A competitive genetic algorithm for resource-constrained project scheduling. Nav. Res. Logist. 45 (1998) 733–750. | DOI | MR | Zbl

S. Hartmann, Project scheduling with multiple modes: a genetic algorithm. Ann. Oper. Res. 102 (2001) 111–135. | DOI | MR | Zbl

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 (2008) 299–308. | MR | Zbl

R. Kolisch, A. Sprecher and A. Drexl, Characterization and generation of a general class of resource-constrained project scheduling problems. Manage. Sci. 41 (1995) 1693–1702. | DOI | Zbl

R. Kolisch and A. Sprecher, PSPLIB – a project scheduling library. Eur. J. Oper. Res. 96 (1996) 205–216. | DOI | Zbl

R. Kolisch and A. Drexl, Local search for nonpreemptive multi-mode resource-constrained project scheduling. IIE Trans. 29 (1997) 987–999. | DOI

G.M. Kopanos, T.S. Kyriakidis and M.C. Georgiadis, New continuous-time and discrete-time mathematical formulations for resource-constrained project scheduling problems. Comput. Chem. Eng. 68 (2014) 96–106. | DOI

T.S. Kyriakidis, G.M. Kopanos and M.C. Georgiadis, MILP formulations for single-and multi-mode resource-constrained project scheduling problems. Comput. Chem. Eng. 36 (2012) 369–385. | DOI

E.L. Lawler, J.K. Lenstra and A.H.G.R. Kan, Recent developments in deterministic sequencing and scheduling: a survey. In: Deterministic Stochastic Scheduling. Springer, Dordrecht (1982) 35–73. | DOI | MR | Zbl

J.A. Lozano, R. Sagarna and P. Larrañaga, Parallel estimation of distribution algorithms. In: Estimation of Distribution Algorithms Springer (2002) 129–145. | DOI | Zbl

J. Magalhães-Mendes, A two-level genetic algorithm for the multi-mode resource-constrained project scheduling problem. Int. J. Syst. Appl. Eng. Dev. 5 (2011) 271–278.

T. Messelis and P. De Causmaecker, 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

D. Morillo, F. Barber and M.A. Salido, 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

A.E.F. Muritiba, C.D. Rodrigues and F.A. Da Costa, A path-relinking algorithm for the multi-mode resource-constrained project scheduling problem. Comput. Oper. Res. 92 (2018) 145–154. | DOI | MR | Zbl

E. Oztemel and A.A. Selam, Bees algorithm for multi-mode, resource-constrained project scheduling in molding industry. Comput. Ind. Eng. 112 (2017) 187–196. | DOI

E. Ratajczak-Ropel, Experimental evaluation of agent-based approaches to solving multi-mode resource-constrained project scheduling problem. Cybern. Syst. (2018) 1–21.

M. Sebt, M. Afshar and Y. Alipouri, 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

R. Slowinski, Two approaches to problems of resource allocation among project activities – a comparative study. J. Oper. Res. Soc. 31 (1980) 711–723. | MR | Zbl

O.S. Soliman and E.A. Elgendi, 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

R. Sonmez and M. Gürel, Hybrid optimization method for large-scale multimode resource-constrained project scheduling problem. J. Manage. Eng. 32 (2016) 04016020. | DOI

A. Sprecher, S. Hartmann and A. Drexl, An exact algorithm for project scheduling with multiple modes. OR Spectr. 19 (1997) 195–203. | DOI | MR | Zbl

A. Sprecher and A. Drexl, Multi-mode resource-constrained project scheduling by a simple, general and powerful sequencing algorithm. Eur. J. Oper. Res. 107 (1998) 431–450. | DOI | Zbl

A. Sprecher, Network decomposition techniques for resource-constrained project scheduling. Oper. Res. Soc. 53 (2002) 405–414. | DOI | Zbl

R. Szeredi and A. Schutt, Modelling and solving multi-mode resource-constrained project scheduling. In: International Conference on Principles and Practice of Constraint Programming. Springer (2016). | MR

F.B. Talbot, Resource-constrained project scheduling with time-resource tradeoffs: the nonpreemptive case. Manage. Sci. 28 (1982) 1197–1210. | DOI | Zbl

T.A. Toffolo, H.G. Santos, M.A. Carvalho and J.A. Soares, An integer programming approach to the multimode resource-constrained multiproject scheduling problem. J. Schedul. 19 (2016) 295–307. | DOI | MR | Zbl

L.-Y. Tseng and S.-C. Chen, Two-phase genetic local search algorithm for the multimode resource-constrained project scheduling problem. IEEE Trans. Evol. Comput. 13 (2009) 848–857. | DOI

V. Valls, F. Ballestin and S. Quintanilla, A population-based approach to the resource-constrained project scheduling problem. Ann. Oper. Res. 131 (2004) 305–324. | DOI | MR | Zbl

V. Valls, F. Ballestin and S. Quintanilla, Justification and RCPSP: a technique that pays. Eur. J. Oper. Res. 165 (2005) 375–386. | DOI | Zbl

V. Van Peteghem and M. Vanhoucke, Using resource scarceness characteristics to solve the multi-mode resource-constrained project scheduling problem, J. Heuristics 17 (2011) 705–728. | DOI | Zbl

V. Van Peteghem and M. Vanhoucke, 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

L. Wang and C. Fang, An effective shuffled frog-leaping algorithm for multi-mode resource-constrained project scheduling problem, Inf. Sci. 181 (2011) 4804–4822. | DOI | MR | Zbl

L. Wang and C. Fang, An effective estimation of distribution algorithm for the multi-mode resource-constrained project scheduling problem, Comput. Oper. Res. 39 (2012) 449–460. | DOI

L. Wang and J. Liu, 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

R. Zamani, A hybrid decomposition procedure for scheduling projects under multiple resource constraints. Oper. Res. 11 (2011) 93–111.

R. Zamani, A polarized adaptive schedule generation scheme for the resource-constrained project scheduling problem. RAIRO: OR 46 (2012) 23–39. | DOI | Numdam | MR | Zbl

R. Zamani, An effective mirror-based genetic algorithm for scheduling multi-mode resource constrained projects. Comput. Ind. Eng. 127 (2019) 914–924. | DOI

H. Zhang, Ant colony optimization for multimode resource-constrained project scheduling. J. Manage. Eng. 28 (2012) 150–159. | DOI

Cité par Sources :