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.
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] Simulated annealing and Boltzmann machines: A stochastic approach to combinatorial Optimization and Neural Computing., Wiley, Chichester (1989). | MR | Zbl
and ,[2] Dynamic space sharing in computer systems. Commun. ACM 12 (1968) 282-288. | Zbl
and ,[3] Resource-constrained project scheduling: notation, classification, models and methods. Eur. J. Oper. Res. 112 (1999) 3-41. | Zbl
, , , and ,[4] Project Scheduling - A Reseach Handbook. Kluwer, Boston (2002). | Zbl
and ,[5] 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.
, (2008)[6] Activity nets: a guided tour through some recent developments. Eur. J. Oper. Res. 82 (1995) 383-408. | Zbl
,[7] Tabu Search. Kluwer, Norwell (1997). | MR | Zbl
and ,[8] A survey of variants and extensions of the resource-constrained project scheduling problem. Eur. J. Oper. Res. 207 (2010) 1-14. | MR | Zbl
and ,[9] Project network models with discounted cash flows: a guided tour through recent developments. Eur. J. Oper. Res. 100 (1997) 97-121. | Zbl
, and ,[10] Resource-constrained project scheduling: a survey of recent developments. Comput. Oper. Res. 25 (1998) 279-302. | MR | Zbl
, and ,[11] C.J. Zappe, Project scheduling problems: a survey. Inter. J. Oper. Production Manag. 13 (1993) 80-91.
,[12] Simulated annealing for multi-mode resource-constrained project scheduling problem. Annal. Oper. Res. 102 (2001) 137-155. | Zbl
, , , and[13] A heuristic approach to allocating the continuous resource in discrete-continuous scheduling problems to minimize the makespan. J. Schedul. 5 (2002) 487-499. | Zbl
, , , and ,[14] Tabu list management methods for a discrete-continuous scheduling problem, Eur. J. Oper. Res. 137 288-302. | Zbl
, and , (2002)[15] On a methodology for discrete-continuous scheduling, Eur. J. Oper. Res. 107 338-353. | Zbl
and , (1998)[16] 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] Experimental investigation of heuristics for resource-constrained project scheduling: An update. Eur. J. Oper. Res. 174 (2006) 23-37. | Zbl
and ,[19] An integrated survey of deterministic project scheduling. OMEGA Int. J. Manag. Sci. 29 (2001) 249-272.
and ,[20] Users guide for CFSQP Version 2.5, http://www.aemdesign.com/download-cfsqp/cfsqp-manual.pdf (1997) (Accessed 2nd April 2013).
, and[21] 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
, and ,[22] Tabu search for multi-mode resource-constrained project scheduling with schedule-dependent setup times. Eur. J. Oper. Res. 187 (2008) 1238-1250. | Zbl
, and ,[23] A survey on the resource-constrained project scheduling problem. IIE Trans. 27 (1995) 574-586.
and ,[24] Tabu search applied to the quadratic assignment problem. ORSA J. Comput. 2 (1990) 33-45. | Zbl
,[25] 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
, and ,[26] Simulated Annealing: Theory Appl., Reidel, Dordrecht (1987). | Zbl
and .[27] Discrete-continuous project scheduling with discounted cash flows - a tabu search approach. Comput. Oper. Res. 35 (2008) 2141-2153. | MR | Zbl
,[28] Tabu search for discrete-continuous scheduling problems with heuristic continuous resource allocation. Eur. J. Oper. Res. 193 (2009) 849-856. | Zbl
,[29] Heuristic approaches to discrete-continuous project scheduling problems to minimize the makespan, Comput. Optim. Appl. 48 (2011) 399-421. | MR | Zbl
,[30] 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
(2011)[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] Multiprocessor scheduling with memory allocation - a deterministic approach. IEEE Trans. Comput. 29 (1980) 703-709. | MR | Zbl
,[33] Project scheduling with finite or infinite number of activity processing modes - a survey, Eur. J. Oper. Res. 208 (2011) 177-205. | MR | Zbl
, , and ,Cité par Sources :