A modified modeling approach and a heuristic procedure for the multi-mode resource constrained project scheduling problem with activity splitting
Faghih-Mohammadi, Fatemeh1 ; Seifi, Abbas1 ; Khalighi-Sikaroudi, Mohammad1
1 Department of Industrial Engineering, Amirkabir University of Technology, Hafiz St. 424, P.O. Box 15875-4413, Tehran, Iran.
RAIRO - Operations Research - Recherche Opérationnelle, Tome 50 (2016) no. 1, pp. 91-118.

This paper presents a new heuristic method for solving multi-mode resource constrained project scheduling problems with renewable resources. Assumptions such as resource vacation and activity splitting are also considered. The proposed heuristic determines one mode for the execution of each activity first, so that the multi-mode problem is reduced to a single-mode one. Our method is compared to two of the existing methods in terms of computational time and solution quality. The results show that while it can outperform one of them (especially as the size of the problem grows), it is outperformed by the other for tested instances with low complexity, but can yield good results for tested instances with higher values of this parameters. This quality may be useful in real-world scheduling problems. We also validate the first phase of our method, i.e., mode selection, with numerical experiments. Our results indicate that better mode vectors selected in the first phase lead to better makespans for the MRCPSP. Moreover, we correct some erroneous constraints in the mathematical model of the problem. We implement the mathematical programming model of the problem in GAMS, and show that solving it to optimality requires much more computational effort compared to our method.

Reçu le :
Accepté le :
DOI : 10.1051/ro/2015014
Classification : 90B35, 68M20, 91B32
Mots-clés : Project scheduling, resource constrained, multi-mode, splitting, renewable resources
Faghih-Mohammadi, Fatemeh 1 ; Seifi, Abbas 1 ; Khalighi-Sikaroudi, Mohammad 1

1 Department of Industrial Engineering, Amirkabir University of Technology, Hafiz St. 424, P.O. Box 15875-4413, Tehran, Iran. 
@article{RO_2016__50_1_91_0,
     author = {Faghih-Mohammadi, Fatemeh and Seifi, Abbas and Khalighi-Sikaroudi, Mohammad},
     title = {A modified modeling approach and a heuristic procedure for the multi-mode resource constrained project scheduling problem with activity splitting},
     journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
     pages = {91--118},
     publisher = {EDP-Sciences},
     volume = {50},
     number = {1},
     year = {2016},
     doi = {10.1051/ro/2015014},
     zbl = {1333.90041},
     language = {en},
     url = {http://archive.numdam.org/articles/10.1051/ro/2015014/}
}
TY  - JOUR
AU  - Faghih-Mohammadi, Fatemeh
AU  - Seifi, Abbas
AU  - Khalighi-Sikaroudi, Mohammad
TI  - A modified modeling approach and a heuristic procedure for the multi-mode resource constrained project scheduling problem with activity splitting
JO  - RAIRO - Operations Research - Recherche Opérationnelle
PY  - 2016
SP  - 91
EP  - 118
VL  - 50
IS  - 1
PB  - EDP-Sciences
UR  - http://archive.numdam.org/articles/10.1051/ro/2015014/
DO  - 10.1051/ro/2015014
LA  - en
ID  - RO_2016__50_1_91_0
ER  - 
%0 Journal Article
%A Faghih-Mohammadi, Fatemeh
%A Seifi, Abbas
%A Khalighi-Sikaroudi, Mohammad
%T A modified modeling approach and a heuristic procedure for the multi-mode resource constrained project scheduling problem with activity splitting
%J RAIRO - Operations Research - Recherche Opérationnelle
%D 2016
%P 91-118
%V 50
%N 1
%I EDP-Sciences
%U http://archive.numdam.org/articles/10.1051/ro/2015014/
%R 10.1051/ro/2015014
%G en
%F RO_2016__50_1_91_0
Faghih-Mohammadi, Fatemeh; Seifi, Abbas; Khalighi-Sikaroudi, Mohammad. A modified modeling approach and a heuristic procedure for the multi-mode resource constrained project scheduling problem with activity splitting. RAIRO - Operations Research - Recherche Opérationnelle, Tome 50 (2016) no. 1, pp. 91-118. doi : 10.1051/ro/2015014. http://archive.numdam.org/articles/10.1051/ro/2015014/

B. Afshar-Nadjafi, H. Najjarbashi and E. Mehdizadeh, A branch-and-bound procedure for resource leveling in multi-mode resource constraint project scheduling problem. Res. J. Recent Sci. 1 (2012) 33–38.

P. Agrawal and S. Rao, Energy-aware scheduling of distributed systems. IEEE Trans. Autom. Sci. Eng. 11 (2014) 1163–1175. | DOI

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

N. Anne and V. Muthukumar, Energy aware scheduling of aperiodic real-time tasks on multiprocessor systems. J. Comput. Sci. Eng. 7 (2013) 30–43. | DOI

H. Aydin, R. Melhem, D. Mosse and P. Mejia-Alvarez, Power-aware scheduling for periodic real-time tasks. IEEE Trans. Comput. 53 (2004) 584–600. | DOI

F. Ballestın, A. Barrios and V. Valls, An evolutionary algorithm for the resource-constrained project scheduling problem with minimum and maximum time-lags. J. Scheduling 14 (2009) 391–406. | DOI | Zbl

F. Ballestin, A. Barrios and V. Valls, Looking for the best modes helps solving the MRCPSP/max. Int. J. Prod. Res. 51 (2013) 813–827. | DOI

E. Bampis, V. Chau, D. Letsios, G. Lucarelli, I. Milis and G. Zois, Energy efficient scheduling of MapReduce jobs, in Proc. of Euro-Par 2014: Parallel Processing: 20th International Conference. Edited by F. Silva, I. Dutra and V. Santos Costa. Springer, Porto (2014) 198–209.

N. Bansal and K. Pruhs, The geometry of scheduling, in Proc. of FOCS’10, The IEEE 51st Annual Symposium on Foundations of Computer Science. IEEE, Washington DC, USA (2010) 407−414.

N. Bansal, H.L. Chan, R. Khandekar, K. Pruhs, B. Schieber and C. Stein, Non-preemptive min-sum scheduling with resource augmentation, in Proc. of 48th Annual IEEE Symposium on Foundations of Computer Science, FOCS’07. IEEE, Providence, RI (2007) 614–624.

N. Bansal, T. Kimbrel and K. Pruhs, Speed scaling to manage energy and temperature. J. ACM 54 (2007) Article No. 3. | DOI | Zbl

N. Bansal, K. Pruhs and C. Stein, Speed scaling for weighted flow time, in Proc. of SODA’07, The Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms. SIAM, Philadelphia, USA (2007) 805–813. | Zbl

N. Bansal, H.L. Chan, K. Pruhs and D. Katz, Improved bounds for speed scaling in devices obeying the cube-root rule. In Automata, languages and programming. Springer, Berlin Heidelberg (2009) 144–155. | Zbl

N. Bansal, H.L. Chan and K. Pruhs, Speed scaling with an arbitrary power function. ACM Trans. Algorithms 9 (2013) Article No. 18. | DOI | Zbl

A. Barrios, F. Ballestin and V. Valls, A double genetic algorithm for the MRCPSP/max. Comput. Oper. Res. 38 (2011) 33–43. | DOI | Zbl

T. Berthold, S. Heinz, M.E. Lubbecke, R.H. Mohring and J. Schulz, A constraint integer programming approach for resource-constrained project scheduling. In Integration of AI And OR Techniques in Constraint Programming for Combinatorial Optimization Problems. Springer, Berlin Heidelberg (2009) 313–317. | 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, A new and efficient heuristic for scheduling projects with resource restrictions and multiple execution modes. Eur. J. Oper. Res. 90 (1996) 349–361. | DOI | Zbl

F.F. Boctor, Other benchmarks (2004) Available at: http://www.om-db.wi.tum.de/psplib/dataob.html. Accessed 10 April 2015.

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 | Zbl

J. Buddhakulsomsiri and D.S. Kim, Properties of multi-mode resource-constrained project scheduling problems with resource vacations and activity splitting. Eur. J. Oper. Res. 175 (2006) 279–295. | DOI | Zbl

R.A. Carrasco, Resource Cost Aware Scheduling. Ph.D. thesis, Columbia University, Canada (2013).

R.A. Carrasco, G. Iyengar and C. Stein, Energy aware scheduling for weighted completion time and weighted tardiness. Technical report. Preprint (2011). | arXiv

R.A. Carrasco, G. Iyengar and C. Stein, Single machine scheduling with job-dependent convex cost and arbitrary precedence constraints. Oper. Res. Lett. 41 (2013) 436–441. | DOI | Zbl

S. Chakrabarti, C.A. Phillips, A.S. Schulz, D.B. Shmoys, C. Stein and J. Wein, Improved scheduling algorithms for minsum criteria (extended abstract). In Proc. of Automata, Languages and Programming: 23rd International Colloquium, ICALP ’96, Paderborn, Germany, July 8-12, 1996. Springer Science & Business Media (1996) 646−657. | Zbl

J. Cheng, J. Fowler, K. Kempf and S. Mason, Multi-mode resource-constrained project scheduling Problems with nonpreemptive activity splitting. Comput. Oper. Res. 53 (2015) 275–287. | DOI | Zbl

T.C.E. Cheng, A. Janiak and M.Y. Kovalyov, Bicriterion single machine scheduling with resource dependent processing times. SIAM J. Optim. 8 (1998) 617–630. | DOI | Zbl

T.C.E. Cheng, Q. Ding and B.M.T. Lin, A concise survey of scheduling with time-dependent processing times. Eur. J. Oper. Res. 152 (2004) 1–13. | DOI | Zbl

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 | Zbl

A. Drexl and J. Gruenewald, Nonpreemptive multi-mode resource constrained Project scheduling. IIE. Trans. 25 (1993) 74–81. | DOI

I. Goiri, F. Julià, R. Nou, J.L. Berral, J. Guitart and J. Torres, Energy-aware scheduling in virtualized datacenters, in Proc. of the 2010 IEEE International Conference on Cluster Computing. IEEE, Heraklion, Crete (2010) 58–67.

A. Grigoriev, M. Sviridenko and M. Uetz, Machine scheduling with resource dependent processing times. Math. Program. 110 (2007) 209–228. | DOI | Zbl

L.A. Hall, D.B. Shmoys and J. Wein, Scheduling to minimize average completion time: off-line and on-line algorithms, in Proc. of ACM-SIAM Symposium on Discrete Algorithms, SODA 7. New Orleans, Louisiana (1996) 142–151. | Zbl

L.A. Hall, A.S. Schulz, D.B. Shmoys and J. Wein, Scheduling to minimize average completion time: off-line and on-line approximation algorithms. Math. Oper. Res. 22 (1997) 513–544. | DOI | Zbl

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

S. Hartmann and D. Briskorn, A survey of variants and extensions of the resource-constrained project scheduling problem. Eur. J. Oper. Res. 207 (2010) 1–14. | DOI | Zbl

R. Heilmann, Resource–constrained project scheduling: a heuristic for the multi-mode case. OR. Spektrum. 23 (2001) 335–357. | DOI | Zbl

R. Heilmann, A branch-and-bound procedure for the multi-mode resource-constrained project scheduling problem with minimum and maximum time lags. Eur. J. Oper. Res. 144 (2003) 348–365. | DOI | Zbl

A. Janiak and M.Y. Kovalyov, Single machine scheduling subject to deadlines and resource dependent processing times. Eur. J. Oper. Res. 94 (1996) 284–291. | DOI | 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. 198 (2008) 299–308. | DOI | MR | Zbl

J. Josefowska, M. Mika, R. Rozycki, G. Waligora and J. Weglarz, Simmulated annealing for multi-mode resource constrained project scheduling. Ann. Oper. Res. 102 (2001) 137–155. | DOI | MR | Zbl

B. Kalyanasundaram and K. Pruhs, Speed is as powerful as clairvoyance. J. ACM. 47 (2000) 617–643. | DOI | MR | Zbl

A. Kandhalu, J. Kim, K. Lakshmanan and R. Rajkumar, Energy-aware partitioned fixed-priority scheduling for chip multi-processors, in Proc. 17th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications. IEEE, Toyama (2011) 93–102.

R. Kolisch, Serial and parallel resource-constrained project scheduling methods revisited: theory and computation. Eur. J. Oper. Res. 90 (1996) 320–333. | DOI | Zbl

R. Kolisch and A. Sprecher, Multi Mode Data Sets (1996). Available at http://www.om-db.wi.tum.de/psplib/datamm.html. Accessed 10 April 2015.

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

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

A. Lova, P. Tormos and F. Barber, Multi-mode resource constrained project scheduling: scheduling schemes, priority rules and mode selection rules. Intel. Artif. 30 (2006) 69–86.

A. Mastor, An experimental and comparative evaluation of production line balancing techniques. Manag. Sci. 16 (1970) 728–746. | DOI | Zbl

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

G.D. Micheli, Synthesis and Optimization of Digital Circuits. McGraw-Hill (1994).

R. Mishra, N. Rastogi, D. Zhu, D. Mossé and R. Melhem, R., Energy aware scheduling for distributed real-time systems, in Proc. of the International Parallel and Distributed Processing Symposium. IEEE Computer Society (Washington), Nice, France (2003) 21–29.

K.T. Nguyen, Lagrangian Duality in Online Scheduling with Resource Augmentation and Speed Scaling. In Algorithms – ESA 2013. Vol. 8125 of Int. Lect. Notes Comput. Sci. Springer, Berlin Heidelberg (2013) 755–766. | MR | Zbl

C.A. Phillips, A.S. Schulz, D.B. Shmoys, C. Stein and J. Wein, Improved bounds on relaxations of a parallel machine scheduling problem. J. Comb. Optim. 1 (1998) 413–426. | DOI | MR | Zbl

C. Phillips, C. Stein and J. Wein, Minimizing average completion time in the presence of release dates. Math. Program. 82 (1998) 199–223. | DOI | MR | Zbl

C. Phillips, C. Stein, E. Torng and J. Wein, Optimal time-critical scheduling via resource augmentation. Algorithmica 32 (2002) 163–200. | DOI | MR | Zbl

J. Polo, C. Castillo, D. Carrera, Y.W.I. Becerra, M. Steinder, J. Torres and E. Ayguade, Resource-Aware Adaptive Scheduling for MapReduce Clusters, in Proc. of Middleware’11 of the 12th ACM/IFIP/USENIX international conference on Middleware, edited by F. Kon and A.M. Kermarrec. Springer-Verlag, Lisboa (2011) 187–207.

M. Seyed-Hosseini and S.M. Sabzehparvar, A mathematical model for the multi-mode resource-constrained project scheduling problem with mode dependent time lags. J. Supercomput. 44 (2008) 257–273. | DOI | Zbl

N. Sharma, V. Sahula and C.P. Ravikumar, Energy aware task scheduling for soft real time systems using an analytical approach for energy estimation. Int. J. Comput. Sci. Eng. 1 (2012) 33–39.

H. Simonis and T. Hadzic, A Resource Cost Aware Cumulative. In Recent Advances in Constraints: 14th Annual ERCIM International Workshop on Constraint Solving and Constraint Logic Programming, CSCLP 2009, Barcelona, Spain, June 15-17, 2009, Revised Selected Papers. Springer-Verlag, Berlin Heidelberg (2011) 76–89. | Zbl

A. Sprecher and A. Drexl, Solving Multi-mode Resource-Constrained Project Scheduling Problems by a Simple, General and Powerful Sequencing Algorithm. Part I: Theory. Working paper (1996). | Zbl

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

M. Tillenius, E. Larsson, R.M. Badia and X. Martorell, Resource-aware task scheduling. ACM Trans. Embed. Comput. Syst. 14 (2015) Article no. 5. | DOI

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 (2010) 409–418. | DOI | MR | 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

V. van Peteghem and M. Vanhoucke, Multiple Modes |Operations Research & Scheduling research Group (2011) Available http://www.projectmanagement.ugent.be/?q=research/project˙scheduling/multi˙mode. Accessed 10 April 2015.

S. Viswanathan, B. Veeravalli and T.G. Robertazzi, Resource-aware distributed scheduling strategies for large-scale computational cluster/grid systems. IEEE Trans. Parallel Distrib. 18 (2007) 1450–1461. | DOI

S. Vob and A. Witt, Hybrid flow shop scheduling as a multi-mode multi-project scheduling problem with batching requirements: A real-world application. Int. J. Prod. Econ. 105 (2007) 445–458. | DOI

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

T. Wauters, K. Verbeeck, G. Vanden Berghe and P. De Causmaecker, Learning agents for the multi-mode project scheduling problem. J. Oper. Res. Soc. 62 (2011) 281–290. | DOI

J. Wêglarz, Project scheduling with continuously-divisible, doubly constrained resources. Manag. Sci. 27 (1981) 1040−1053. | DOI | Zbl

J. Weglarz, J. Józefowska, M. Mika and G. Waligora, Project scheduling with finite or infinite number of activity processing modes a Survey. Eur. J. Oper. Res. 208 (2011) 177–205. | DOI | MR | Zbl

K.K. Yang, A comparison of dispatching rules for executing a resource-constrained project. Omega 26 (1998) 729–738. | DOI

M. Yong, N. Garegrat and S. Mohan, Towards a Resource Aware Scheduler in Hadoop, in Proc. of ICWS 2009. IEEE, Los Angeles (2009) 102–109.

B.D. Young, S. Pasricha, A.A. Maciejewski, H.J. Siegel and J.T. Smith, Heterogeneous Makespan and Energy-Constrained DAG Scheduling, in Proc. of Workshop on Energy Efficient High Performance Parallel and Distributed Computing. ACM, New York, New York (2013) 3–12.

Q. Zhang, M.F. Zhani, Y. Yang, R. Boutaba and B. Wong, PRISM: fine-grained resource-aware scheduling for MapReduce. IEEE Trans. Cloud. Comput. 3 (2015) 182–194. | DOI

G. Zhu, J.F. Bard and G. Yu, A branch-and-cut procedure for the multimode resource-constrained project scheduling problem. Informs J. Comput. 18 (2006) 377–390. | DOI | Zbl

Cité par Sources :