Hostname: page-component-7479d7b7d-pfhbr Total loading time: 0 Render date: 2024-07-08T14:49:43.991Z Has data issue: false hasContentIssue false
  • English
  • Français

Simulated Annealing and Tabu Search for Discrete-Continuous Project Scheduling with Discounted Cash Flows

Published online by Cambridge University Press:  05 December 2013

Grzegorz Waligóra
Grzegorz Waligóra*
Affiliation:
Institute of Computing Science, Poznan University of Technology, Piotrowo 2, 60-965 Poznan, Poland. [email protected]
Get access

Abstract

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.

Keywords

Discrete-continuous project schedulingdiscounted cash flowsnet present valuepayment modelsnonlinear programmingmetaheuristicssimulated annealingtabu search
Type
Research Article
Information
RAIRO - Operations Research , Volume 48 , Issue 1 , January 2014 , pp. 1 - 24
Copyright
© EDP Sciences, ROADEF, SMAI, 2013

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

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).
Belady, L.A. and Kuehner, C.J., Dynamic space sharing in computer systems. Commun. ACM 12 (1968) 282–288. Google Scholar
Brucker, P., Drexl, A., Möhring, R., Neumann, K. and Pesch, E., Resource-constrained project scheduling: notation, classification, models and methods. Eur. J. Oper. Res. 112 (1999) 3–41. Google Scholar
E.L. Demeulemeester and W.S. Herroelen, Project Scheduling – A Reseach Handbook. Kluwer, Boston (2002).
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.
Elmaghraby, S.E., Activity nets: a guided tour through some recent developments. Eur. J. Oper. Res. 82 (1995) 383–408. Google Scholar
F. Glover and M. Laguna, Tabu Search. Kluwer, Norwell (1997).
Hartmann, S. and Briskorn, D., A survey of variants and extensions of the resource-constrained project scheduling problem. Eur. J. Oper. Res. 207 (2010) 1–14. Google Scholar
Herroelen, W.S., Van Dommelen, P. and Demeulemeester, E.L., Project network models with discounted cash flows: a guided tour through recent developments. Eur. J. Oper. Res. 100 (1997) 97–121. Google Scholar
Herroelen, W.S., De Reyck, B. and Demeulemeester, E.L., Resource-constrained project scheduling: a survey of recent developments. Comput. Oper. Res. 25 (1998) 279–302. Google Scholar
Icmeli, O., Erengçüand, S.S. Zappe, C.J., Project scheduling problems: a survey. Inter. J. Oper. Production Manag. 13 (1993) 80–91. Google Scholar
Józefowska, J., Mika, M., Różycki, R., G., Waligóra, and J., Wȩglarz Simulated annealing for multi-mode resource-constrained project scheduling problem. Annal. Oper. Res. 102 (2001) 137–155. Google Scholar
Józefowska, J., Mika, M., Różycki, R., Waligóra, G. and Wȩglarz, J., A heuristic approach to allocating the continuous resource in discrete-continuous scheduling problems to minimize the makespan. J. Schedul. 5 (2002) 487–499. Google Scholar
Józefowska, J., Waligóra, G. and Wȩglarz, J., (2002) Tabu list management methods for a discrete-continuous scheduling problem, Eur. J. Oper. Res. 137 288–302. Google Scholar
Józefowska, J. and Wȩglarz, J., (1998) On a methodology for discrete-continuous scheduling, Eur. J. Oper. Res. 107 338–353. Google Scholar
A. Kimms, Mathematical Programming and Financial Objectives for Scheduling Projects. Kluwer, Dordrecht (2012).
Kolisch, R., and Hartmann, S., (2000) Experimental evaluation of state-of-the-art heuristics for the resource-constrained project scheduling problem. Eur. J. Oper. Res. 127 (2001) 394–407. Google Scholar
Kolisch, R. and Hartmann, S., Experimental investigation of heuristics for resource-constrained project scheduling: An update. Eur. J. Oper. Res. 174 (2006) 23–37. Google Scholar
Kolisch, R. and Padman, R., An integrated survey of deterministic project scheduling. OMEGA Int. J. Manag. Sci. 29 (2001) 249–272. Google Scholar
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).
Mika, M., Waligóra, G. and Wȩglarz, J., 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. Google Scholar
Mika, M., Waligóra, G. and Wȩglarz, J., Tabu search for multi-mode resource-constrained project scheduling with schedule-dependent setup times. Eur. J. Oper. Res. 187 (2008) 1238–1250. Google Scholar
Özdamar, L. and Ulusoy, G., A survey on the resource-constrained project scheduling problem. IIE Trans. 27 (1995) 574–586. Google Scholar
Skorin-Kapov, J., Tabu search applied to the quadratic assignment problem. ORSA J. Comput. 2 (1990) 33–45. Google Scholar
Ulusoy, G., Sivrikaya-Şerifoğlu, F. 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. Google Scholar
P.J.M. Van Laarhoven and E.H.L. Aarts. Simulated Annealing: Theory Appl., Reidel, Dordrecht (1987).
Waligóra, G., Discrete-continuous project scheduling with discounted cash flows – a tabu search approach. Comput. Oper. Res. 35 (2008) 2141–2153. Google Scholar
Waligóra, G., Tabu search for discrete-continuous scheduling problems with heuristic continuous resource allocation. Eur. J. Oper. Res. 193 (2009) 849–856. Google Scholar
Waligóra, G., Heuristic approaches to discrete-continuous project scheduling problems to minimize the makespan, Comput. Optim. Appl. 48 (2011) 399–421. Google Scholar
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.
Wȩglarz, J. Time-optimal control of resource allocation in a complex of operations framework. IEEE Trans. Systems, Man and Cybernetics 6 (1976) 783–788. Google Scholar
Wȩglarz, J., Multiprocessor scheduling with memory allocation – a deterministic approach. IEEE Trans. Comput. 29 (1980) 703–709. Google Scholar
Wȩglarz, J., Józefowska, J., Mika, M. and Waligóra, G., Project scheduling with finite or infinite number of activity processing modes – a survey, Eur. J. Oper. Res. 208 (2011) 177–205. Google Scholar