Simulated Annealing and Tabu Search for Discrete-Continuous Project Scheduling with Discounted Cash Flows
RAIRO - Operations Research - Recherche Opérationnelle, Tome 48 (2014) no. 1, pp. 1-24.

Discrete-continuous project scheduling problems with positive discounted cash flows and the maximization of the NPV are considered. We deal with a class of these problems with an arbitrary number of discrete resources and one continuous, renewable resource. Activities are nonpreemptable, and the processing rate of an activity is a continuous, increasing function of the amount of the continuous resource allotted to the activity at a time. Three common payment models - Lump Sum Payment, Payments at Activity Completion times, and payments in Equal Time Intervals are analyzed. Formulations of mathematical programming problems for an optimal continuous resource allocation for each payment model are presented. Applications of two local search metaheuristics - Tabu Search and Simulated Annealing are proposed. The algorithms are compared on a basis of computational experiments. Some conclusions and directions for future research are pointed out.

DOI : 10.1051/ro/2013045
Classification : 68M20, 90B35, 90C30, 90C59
Mots-clés : discrete-continuous project scheduling, discounted cash flows, net present value, payment models, nonlinear programming, metaheuristics, simulated annealing, tabu search 
@article{RO_2014__48_1_1_0,
     author = {Walig\'ora, Grzegorz},
     title = {Simulated {Annealing} and {Tabu} {Search} for {Discrete-Continuous} {Project} {Scheduling} with {Discounted} {Cash} {Flows}},
     journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
     pages = {1--24},
     publisher = {EDP-Sciences},
     volume = {48},
     number = {1},
     year = {2014},
     doi = {10.1051/ro/2013045},
     mrnumber = {3143766},
     language = {en},
     url = {http://www.numdam.org/articles/10.1051/ro/2013045/}
}
TY  - JOUR
AU  - Waligóra, Grzegorz
TI  - Simulated Annealing and Tabu Search for Discrete-Continuous Project Scheduling with Discounted Cash Flows
JO  - RAIRO - Operations Research - Recherche Opérationnelle
PY  - 2014
SP  - 1
EP  - 24
VL  - 48
IS  - 1
PB  - EDP-Sciences
UR  - http://www.numdam.org/articles/10.1051/ro/2013045/
DO  - 10.1051/ro/2013045
LA  - en
ID  - RO_2014__48_1_1_0
ER  - 
%0 Journal Article
%A Waligóra, Grzegorz
%T Simulated Annealing and Tabu Search for Discrete-Continuous Project Scheduling with Discounted Cash Flows
%J RAIRO - Operations Research - Recherche Opérationnelle
%D 2014
%P 1-24
%V 48
%N 1
%I EDP-Sciences
%U http://www.numdam.org/articles/10.1051/ro/2013045/
%R 10.1051/ro/2013045
%G en
%F RO_2014__48_1_1_0
Waligóra, Grzegorz. Simulated Annealing and Tabu Search for Discrete-Continuous Project Scheduling with Discounted Cash Flows. RAIRO - Operations Research - Recherche Opérationnelle, Tome 48 (2014) no. 1, pp. 1-24. doi : 10.1051/ro/2013045. http://www.numdam.org/articles/10.1051/ro/2013045/

[1] E.H.L. Aarts and J.H.M. Korst, Simulated annealing and Boltzmann machines: A stochastic approach to combinatorial Optimization and Neural Computing., Wiley, Chichester (1989). | MR | Zbl

[2] L.A. Belady and C.J. Kuehner, Dynamic space sharing in computer systems. Commun. ACM 12 (1968) 282-288. | Zbl

[3] P. Brucker, A. Drexl, R. Möhring, K. Neumann and E. Pesch, Resource-constrained project scheduling: notation, classification, models and methods. Eur. J. Oper. Res. 112 (1999) 3-41. | Zbl

[4] E.L. Demeulemeester and W.S. Herroelen, Project Scheduling - A Reseach Handbook. Kluwer, Boston (2002). | Zbl

[5] L.E. Drezet, (2008) RCPSP with financial costs, in C. Artigues, S. Demassey and E. Néron, Resource-Constrained Project Scheduling: Models, Algorithms, Extensions and Applications, ISTE-Wiley, London (2002) 213-226.

[6] S.E. Elmaghraby, Activity nets: a guided tour through some recent developments. Eur. J. Oper. Res. 82 (1995) 383-408. | Zbl

[7] F. Glover and M. Laguna, Tabu Search. Kluwer, Norwell (1997). | MR | Zbl

[8] 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. | MR | Zbl

[9] W.S. Herroelen, P. Van Dommelen and E.L. Demeulemeester, Project network models with discounted cash flows: a guided tour through recent developments. Eur. J. Oper. Res. 100 (1997) 97-121. | Zbl

[10] W.S. Herroelen, B. De Reyck and E.L. Demeulemeester, Resource-constrained project scheduling: a survey of recent developments. Comput. Oper. Res. 25 (1998) 279-302. | MR | Zbl

[11] O. Icmeli, S.S. Erengçüand C.J. Zappe, Project scheduling problems: a survey. Inter. J. Oper. Production Manag. 13 (1993) 80-91.

[12] J. Józefowska, M. Mika, R. Różycki, Waligóra, G. and Wȩglarz J. Simulated annealing for multi-mode resource-constrained project scheduling problem. Annal. Oper. Res. 102 (2001) 137-155. | Zbl

[13] J. Józefowska, M. Mika, R. Różycki, G. Waligóra and J. Wȩglarz, A heuristic approach to allocating the continuous resource in discrete-continuous scheduling problems to minimize the makespan. J. Schedul. 5 (2002) 487-499. | Zbl

[14] J. Józefowska, G. Waligóra and J. Wȩglarz, (2002) Tabu list management methods for a discrete-continuous scheduling problem, Eur. J. Oper. Res. 137 288-302. | Zbl

[15] J. Józefowska and J. Wȩglarz, (1998) On a methodology for discrete-continuous scheduling, Eur. J. Oper. Res. 107 338-353. | Zbl

[16] A. Kimms, Mathematical Programming and Financial Objectives for Scheduling Projects. Kluwer, Dordrecht (2012). | Zbl

[17] R., Kolisch and S. Hartmann, (2000) Experimental evaluation of state-of-the-art heuristics for the resource-constrained project scheduling problem. Eur. J. Oper. Res. 127 (2001) 394-407. | Zbl

[18] R. Kolisch and S. Hartmann, Experimental investigation of heuristics for resource-constrained project scheduling: An update. Eur. J. Oper. Res. 174 (2006) 23-37. | Zbl

[19] R. Kolisch and R. Padman, An integrated survey of deterministic project scheduling. OMEGA Int. J. Manag. Sci. 29 (2001) 249-272.

[20] C. Lawrence, J.L. Zhou and Tits A.L. Users guide for CFSQP Version 2.5, http://www.aemdesign.com/download-cfsqp/cfsqp-manual.pdf (1997) (Accessed 2nd April 2013).

[21] M. Mika, G. Waligóra and J. Wȩglarz, Simulated annealing and tabu search for multi-mode resource-constrained project scheduling with positive discounted cash flows and different payment models. Eur. J. Oper. Res. 164 (2005) 639-668. | MR | Zbl

[22] M. Mika, G. Waligóra and J. Wȩglarz, Tabu search for multi-mode resource-constrained project scheduling with schedule-dependent setup times. Eur. J. Oper. Res. 187 (2008) 1238-1250. | Zbl

[23] L. Özdamar and G. Ulusoy, A survey on the resource-constrained project scheduling problem. IIE Trans. 27 (1995) 574-586.

[24] J. Skorin-Kapov, Tabu search applied to the quadratic assignment problem. ORSA J. Comput. 2 (1990) 33-45. | Zbl

[25] G. Ulusoy, F. Sivrikaya-Şerifoğlu and Ş. Şahin, Four payment models for the multi-mode resource constrained project scheduling problem with discounted cash flows. Annal. Oper. Res. 102 (2001) 237-261. | MR | Zbl

[26] P.J.M. Van Laarhoven and E.H.L. Aarts. Simulated Annealing: Theory Appl., Reidel, Dordrecht (1987). | Zbl

[27] G. Waligóra, Discrete-continuous project scheduling with discounted cash flows - a tabu search approach. Comput. Oper. Res. 35 (2008) 2141-2153. | MR | Zbl

[28] G. Waligóra, Tabu search for discrete-continuous scheduling problems with heuristic continuous resource allocation. Eur. J. Oper. Res. 193 (2009) 849-856. | Zbl

[29] G. Waligóra, Heuristic approaches to discrete-continuous project scheduling problems to minimize the makespan, Comput. Optim. Appl. 48 (2011) 399-421. | MR | Zbl

[30] Waligóra, G. (2011) Discrete-continuous project scheduling with discounted cash inflows and various payment models - a review of recent results. Annal. Oper. Res. DOI: 10.1007/s10479-011-1014-0. | Zbl

[31] J. Wȩglarz Time-optimal control of resource allocation in a complex of operations framework. IEEE Trans. Systems, Man and Cybernetics 6 (1976) 783-788. | MR | Zbl

[32] J. Wȩglarz, Multiprocessor scheduling with memory allocation - a deterministic approach. IEEE Trans. Comput. 29 (1980) 703-709. | MR | Zbl

[33] J. Wȩglarz, J. Józefowska, M. Mika and G. Waligóra, Project scheduling with finite or infinite number of activity processing modes - a survey, Eur. J. Oper. Res. 208 (2011) 177-205. | MR | Zbl

Cité par Sources :