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

Grzegorz Waligóra

RAIRO - Operations Research - Recherche Opérationnelle (2014)

  • Volume: 48, Issue: 1, page 1-24
  • ISSN: 0399-0559

Abstract

top
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.

How to cite

top

Waligóra, Grzegorz. "Simulated Annealing and Tabu Search for Discrete-Continuous Project Scheduling with Discounted Cash Flows." RAIRO - Operations Research - Recherche Opérationnelle 48.1 (2014): 1-24. <http://eudml.org/doc/275017>.

@article{Waligóra2014,
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.},
author = {Waligóra, Grzegorz},
journal = {RAIRO - Operations Research - Recherche Opérationnelle},
keywords = {discrete-continuous project scheduling; discounted cash flows; net present value; payment models; nonlinear programming; metaheuristics; simulated annealing; tabu search},
language = {eng},
number = {1},
pages = {1-24},
publisher = {EDP-Sciences},
title = {Simulated Annealing and Tabu Search for Discrete-Continuous Project Scheduling with Discounted Cash Flows},
url = {http://eudml.org/doc/275017},
volume = {48},
year = {2014},
}

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
PB - EDP-Sciences
VL - 48
IS - 1
SP - 1
EP - 24
AB - 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.
LA - eng
KW - discrete-continuous project scheduling; discounted cash flows; net present value; payment models; nonlinear programming; metaheuristics; simulated annealing; tabu search
UR - http://eudml.org/doc/275017
ER -

References

top
  1. [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). Zbl0905.90140MR983115
  2. [2] L.A. Belady and C.J. Kuehner, Dynamic space sharing in computer systems. Commun. ACM12 (1968) 282–288. Zbl0175.16404
  3. [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. Zbl0937.90030
  4. [4] E.L. Demeulemeester and W.S. Herroelen, Project Scheduling – A Reseach Handbook. Kluwer, Boston (2002). Zbl1059.90068
  5. [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. [6] S.E. Elmaghraby, Activity nets: a guided tour through some recent developments. Eur. J. Oper. Res.82 (1995) 383–408. Zbl0910.90175
  7. [7] F. Glover and M. Laguna, Tabu Search. Kluwer, Norwell (1997). Zbl0930.90083MR1665424
  8. [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. Zbl1205.90123MR2659413
  9. [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. Zbl0947.90583
  10. [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. Zbl1040.90525MR1660879
  11. [11] O. Icmeli, S.S. ErengçüandC.J. Zappe, Project scheduling problems: a survey. Inter. J. Oper. Production Manag. 13 (1993) 80–91. 
  12. [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. Zbl0990.90513
  13. [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. Zbl1029.90030
  14. [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. Zbl1030.90035
  15. [15] J. Józefowska and J. Wȩglarz, (1998) On a methodology for discrete-continuous scheduling, Eur. J. Oper. Res. 107 338–353. Zbl0943.90033
  16. [16] A. Kimms, Mathematical Programming and Financial Objectives for Scheduling Projects. Kluwer, Dordrecht (2012). Zbl1123.90024
  17. [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. Zbl0985.90036
  18. [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. Zbl1116.90047
  19. [19] R. Kolisch and R. Padman, An integrated survey of deterministic project scheduling. OMEGA Int. J. Manag. Sci.29 (2001) 249–272. 
  20. [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. [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. Zbl1061.90048MR2114753
  22. [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. Zbl1137.90508
  23. [23] L. Özdamar and G. Ulusoy, A survey on the resource-constrained project scheduling problem. IIE Trans.27 (1995) 574–586. 
  24. [24] J. Skorin-Kapov, Tabu search applied to the quadratic assignment problem. ORSA J. Comput.2 (1990) 33–45. Zbl0752.90054
  25. [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. Zbl0990.90509MR1854427
  26. [26] P.J.M. Van Laarhoven and E.H.L. Aarts. Simulated Annealing: Theory Appl., Reidel, Dordrecht (1987). Zbl0643.65028
  27. [27] G. Waligóra, Discrete-continuous project scheduling with discounted cash flows – a tabu search approach. Comput. Oper. Res.35 (2008) 2141–2153. Zbl1177.90189MR2585214
  28. [28] G. Waligóra, Tabu search for discrete-continuous scheduling problems with heuristic continuous resource allocation. Eur. J. Oper. Res.193 (2009) 849–856. Zbl1279.90073
  29. [29] G. Waligóra, Heuristic approaches to discrete-continuous project scheduling problems to minimize the makespan, Comput. Optim. Appl.48 (2011) 399–421. Zbl1219.90070MR2783433
  30. [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. Zbl1296.90061
  31. [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. Zbl0336.49022MR446478
  32. [32] J. Wȩglarz, Multiprocessor scheduling with memory allocation – a deterministic approach. IEEE Trans. Comput.29 (1980) 703–709. Zbl0441.68034MR582134
  33. [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. Zbl1208.90082MR2746841

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.