×

zbMATH — the first resource for mathematics

Robust optimization models for project scheduling with resource availability cost. (English) Zbl 1154.90504
Summary: We address a project scheduling problem with resource availability cost for which the activity durations are uncertain. The problem is formulated within the robust optimization framework, where uncertainty is modeled via a set of scenarios. The proposed solution method is based on the scatter search methodology and employs advanced strategies, such as dynamic updating of the reference set, a frequency-based memory mechanism, and path relinking. A multistart heuristic was also developed and comparative results are reported. The tradeoffs for risk-averse decision makers are discussed.

MSC:
90B35 Deterministic scheduling theory in operations research
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Brucker, P., A. Drexl, R. Mohring, K. Neumann, and E. Pesch, ”Resource-constrained project scheduling: Notation, classification, models and methods,” European Journal of Operational Research, 112, 3–41 (1999). · Zbl 0937.90030
[2] Daniels, R. L. and P. Kouvelis, ”Robust scheduling to hedge against processing time uncertainty in single-stage production,” Management Science, 41, 363–376 (1995). · Zbl 0832.90050
[3] Demeulemeester, E., ”Minimizing resource availability costs in time-limited project networks,” Management Science, 41, 1590–1598 (1995). · Zbl 0861.90071
[4] Dorndorf, U., E. Pesch, and T. Phan-Huy, ”A branch-and-bound algorithm for the resource-constrained project scheduling problem,” Mathematical Methods of Operations Research, 52, 413–439 (2000a). · Zbl 1023.90024
[5] Dorndorf, U., E. Pesch, and T. Phan-Huy, ”A time oriented branch-and-bound algorithm for resource-constrained project scheduling with generalized precedence constraints,” Management Science, 46, 1365–1384 (2000b). · Zbl 1232.90208
[6] Drexl, A. and A. Kimms, ”Optimization guided lower and upper bounds for the resource investment problem,” Journal of the Operational Research Society, 52, 340–351 (2001). · Zbl 1131.90378
[7] Escudero, L. F., P. V. Kamesan, A. J. King, and R. J.-B. Wets, ”Production planning via scenario modeling,” Annals of Operations Research, 43, 311–335 (1993). · Zbl 0784.90033
[8] Escudero, L., F. J. Quintana, and J. Salmerón, ”CORO, A modeling and an algorithmic framework fo oil supply, transformation and distribution optimization under uncertainty,” European Journal of Operational Research, 114, 638–656 (1999). · Zbl 0938.90019
[9] Glover, F., ”Heuristics for integer programming using surrogate constraints,” Decision Sciences, 8, 156–166 (1977).
[10] Glover, F., ”A template for scatter search and path relinking,” in Hao, J. K., Lutton, E., Ronald, E., Schoenauer, M., Snyers, D. (Eds.), Lecture Notes in Computer Science, vol. 1363, Springer, Berlin (1998) pp. 13–54.
[11] Golenko-Ginzburg, D. and A. Gonik, ”Stochastic network project scheduling with non-consumable limited resources,” International Journal of Production Economics, 48, 29–37 (1997). · Zbl 1017.90512
[12] Golenko-Ginzburg, D. and A. Gonik, ”A heuristic for network project scheduling with random activity durations depending on the resource allocation,” International Journal of Production Economics, 55, 149–162 (1998).
[13] Gonzalez-Velarde, J. L. and M. Laguna, ”A Benders-based heuristic for the robust capacitated international sourcing problem,” IIE Transactions, 36, 1125–1133 (2004).
[14] Gutierrez, G. J. and P. Kouvelis, ”A robustness approach to international sourcing,” Annals of Operations Research, 59, 165–193 (1995). · Zbl 0836.90025
[15] Hartmann, S. and R. Kolisch, ”Experimental evaluation of state-of-the-art heuristics for the resource-constrained project scheduling problem,” European Journal of Operational Research, 127, 394–407 (2000). · Zbl 0985.90036
[16] Herroelen, W., B. De Reyck, and E. Demeulemeester, ”Resource-constrained project scheduling: A survey of recent developments,” Computers & Operations Research, 25, 279–302 (1998). · Zbl 1040.90525
[17] Igelmund, G. and Radermacher, F. J., ”Algorithmic approaches to preselective strategies for stochastic scheduling problems,” Networks, 13, 29–48 (1983). · Zbl 0504.90040
[18] Kolisch, R. and S. Hartmann, ”Heuristic algorithms for the resource-constrained project scheduling problem: Classification and computational analysis,” in Weglarz, J. (Ed.), Project Scheduling: Recent Models, Algorithms, and Applications, Kluwer Academic, Boston (1998) pp. 147–178.
[19] Kolisch, R. and A. Sprecher, ”PSPLIB– A project scheduling library,” European Journal of Operational Research, 96, 205–216 (1996). · Zbl 0947.90587
[20] Laguna, M., ”Applying robust optimization to capacity expansion of one location in telecommunications with demand uncertainty,” Management Science, 44, S101–S110 (1998). · Zbl 0989.90017
[21] Laguna, M., P. Lino, A. Pérez, S. Quintanilla, and V. Valls, ”Minimizing weighted tardiness of jobs with stochastic interruptions in parallel machines,” European Journal of Operational Research, 127(2), 444–457 (2000). · Zbl 0990.90031
[22] Laguna, M. and R. Martí, Scatter Search: Methodology and Implementations in C, Kluwer Academic, Boston (2003).
[23] Malcolm, S. and S. Zenios, ”Robust optimization for power capacity expansion planning,” Journal of the Operational Research Society, 45, 1040–1049 (1994). · Zbl 0815.90108
[24] Markowitz, H., Portfolio selection, efficiency diversification of investments. Cowles Foundation Monograph 16. Yales University Press, New Haven, CT (2nd edn., Basil Blackwell, Cambridge, MA, 1991) (1959).
[25] Martí, R., M. Laguna, and F. Glover, ”Principles of scatter search,” European Journal of Operational Research, 169(2), 359–372 (2005). · Zbl 1079.90178
[26] Möhring, R. H., ”Minimizing costs of resource requirements in project networks subject to a fixed completion time,” Operations Research, 32, 89–120 (1984). · Zbl 0531.90049
[27] Möhring, R. H. and F. Stork, ”Linear preselective policies for stochastic project scheduling,” Mathematical Methods of Operations Research, 52(3), 501–515 (2000). · Zbl 1023.90033
[28] Mulvey, J. M., R. J. Vanderbei, and S. A. Zenios, ”Robust optimization of large-scale systems,” Operations Research, 43, 264–281 (1995). · Zbl 0832.90084
[29] Radermacher, F. J., ”Scheduling of project networks,” Annals of Operations Research, 4, 227–252 (1985). · Zbl 0693.90046
[30] Rangaswamy, B., Multiple Resource Planning and Allocation in Resource-Constrained Project Networks, Ph.D. Thesis. University of Colorado at Boulder (1998).
[31] Stork, F., Branch-and-Bound Algorithms for Stochastic Resource-Constrained Project Scheduling, Technical Rep. 702-2000. Combinatorial Optimization & Graph Algorithms Group, Technische Universität Berlin (2000).
[32] Tormos, P. and A. Lova, ”An efficient multi-pass heuristics for project scheduling with constrained resources,” International Journal of Production Research, 41, 1071–1086 (2003). · Zbl 1038.90038
[33] Tsai, Y.-W. and D. D. Gemmill, ”Using tabu search to schedule activities of stochastic resource-constrained projects,” European Journal of Operational Research, 111, 129–141 (1998). · Zbl 0948.90072
[34] Valls, V., M. Laguna, P. Lino, A. Pérez, and S. Quintanilla, ”Project scheduling with stochastic activity interruptions,” in Werglarz, J. (Ed.), Project Scheduling: Recent Models, Algorithms and Applications, Kluwer Academic, Boston (1998) pp. 333–353.
[35] Yamashita, D. S., V. A. Armentano, and M. Laguna, ”Scatter search for project scheduling with resource availability cost, Special Issue on Scatter Search,” European Journal of Operational Research, 169, 623–637 (2006). · Zbl 1079.90066
[36] Yu, C.-S. and H.-L. Li, ”A robust optimization model for stochastic logistic problems,” International Journal of Production Economics, 64, 385–397 (2000).
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.