×

Order-based neighborhoods for project scheduling with nonregular objective functions. (English) Zbl 1040.90018

The resource-constrained project scheduling problem with general temporal constraints (minimal and maximal time-lags) and nonregular objective functions is studied. It is shown that for certain objective functions the search for an optimal solution can be restricted to special types of schedules. Based on these results appropriate neighborhoods (based on spanning trees of order networks) are developed, which are shown to be weakly connected.

MSC:

90B35 Deterministic scheduling theory in operations research
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Aarts, E.; Lenstra, J. K., Local Search in Combinatorial Optimization (1997), Wiley: Wiley Chichester · Zbl 0869.00019
[2] Ahuja, R. K.; Magnanti, T. L.; Orlin, J. B., Network Flows (1993), Prentice Hall: Prentice Hall Englewood Cliffs · Zbl 1201.90001
[3] Baar, T.; Brucker, P.; Knust, S., Tabu-search algorithms and lower bounds for the resource-constrained project scheduling problem, (Voss, S.; Martello, S.; Osman, I.; Roucairol, C., Meta-Heuristics: Advances and Trends in Local Search Paradigms for Optimization (1998), Kluwer: Kluwer Boston), 1-18 · Zbl 1074.90563
[4] Bandelloni, M.; Tucci, M.; Rinaldi, R., Optimal resource leveling using non-serial dynamic programming, European Journal of Operational Research, 78, 162-177 (1994) · Zbl 0812.90062
[5] Bartusch, M.; Möhring, R. H.; Radermacher, F. J., Scheduling project networks with resource constraints and time windows, Annals of Operations Research, 16, 201-240 (1988) · Zbl 0693.90047
[6] Bouleimen, K., Lecocq, H., 1998. A new efficient simulated annealing algorithm for the resource-constrained project scheduling problem, Technical Report, Service de Robotique et Automatisation, University of Liège; Bouleimen, K., Lecocq, H., 1998. A new efficient simulated annealing algorithm for the resource-constrained project scheduling problem, Technical Report, Service de Robotique et Automatisation, University of Liège · Zbl 1040.90015
[7] Brucker, P.; Drexl, A.; Möhring, R. H.; Neumann, K.; Pesch, E., Resource-constrained project scheduling: notation, classification, models, and methods, European Journal of Operational Research, 112, 3-41 (1999) · Zbl 0937.90030
[8] Cho, J. H.; Kim, Y. D., A simulated annealing algorithm for resource constrained project scheduling problems, Journal of the Operational Research Society, 48, 736-744 (1997) · Zbl 0881.90069
[9] Demeulemeester, E., Minimizing resource availability costs in time-limited project networks, Management Science, 41, 1590-1598 (1995) · Zbl 0861.90071
[10] De Reyck, B.; Herroelen, W., An optimal procedure for the resource-constrained project scheduling problem with discounted cash flows and generalized precedence relations, Computers and Operations Research, 25, 1-17 (1998) · Zbl 0909.90175
[11] Easa, S. M., Resource leveling in construction by optimization, Journal of Construction Engineering and Management, 115, 302-316 (1989)
[12] Franck, B.; Neumann, K.; Schwindt, C., Truncated branch-and-bound, schedule-construction, and schedule-improvement procedures for resource-constrained project scheduling, OR Spektrum, 23, 297-324 (2001) · Zbl 0989.90060
[13] Herroelen, W.; van Dommelen, P.; Demeulemeester, E. L., Project network models with discounted cash flows: a guided tour through recent developments, European Journal of Operational Research, 100, 97-121 (1997) · Zbl 0947.90583
[14] Herroelen, W.; Demeulemeester, E.; De Reyck, B., A classification scheme for project scheduling, (Wȩglarz, J., Project Scheduling: Recent Models, Algorithms and Applications (1999), Kluwer: Kluwer Boston), 1-26
[15] Icmeli, O.; Erengüç, S. S., A tabu search procedure for the resource-constrained project scheduling problem with discounted cash flows, Computers and Operations Research, 21, 841-853 (1994) · Zbl 0812.90065
[16] Icmeli, O.; Erengüç, S. S., A branch and bound procedure for the resource-constrained project scheduling problem with discounted cash flows, Management Science, 42, 1395-1408 (1996) · Zbl 0880.90074
[17] Kolisch, R.; Hartmann, S., Heuristic algorithms for the resource-constrained project scheduling problem: classification and computational analysis, (Wȩglarz, J., Project Scheduling: Recent Models, Algorithms and Applications (1999), Kluwer: Kluwer Boston), 147-178
[18] Lee, J. K.; Kim, Y. D., Search heuristics for resource constrained project scheduling, Journal of the Operational Research Society, 47, 678-689 (1996) · Zbl 0863.90090
[19] Leon, V. J.; Balakrishnan, R., Strength and adaptability of problem-space based neighborhoods for resource-constrained scheduling, OR Spektrum, 17, 173-182 (1995) · Zbl 0842.90062
[20] Mayer, H., Projektplanung bei beschränkten Ressourcen: Effiziente Lösungsverfahren zur Kapitalwertmaximierung (1998), Peter Lang: Peter Lang Frankfurt a.M
[21] Naphade, K. S.; Wu, S. D.; Storer, R. H., Problem space search algorithms for resource-constrained project scheduling, Annals of Operations Research, 70, 307-326 (1997) · Zbl 0893.90093
[22] Neumann, K.; Schwindt, C., Activity-on-node networks with minimal and maximal time-lags and their application to make-to-order production, OR Spektrum, 19, 205-217 (1997) · Zbl 0885.90058
[23] Neumann, K.; Zimmermann, J., Heuristic methods for resource-constrained project scheduling with regular and nonregular objective functions and schedule-dependent time windows, (Wȩglarz, J., Project Scheduling: Recent Models, Algorithms and Applications (1999), Kluwer: Kluwer Boston), 261-287
[24] Neumann, K.; Zimmermann, J., Resource levelling for projects with schedule-dependent time windows, European Journal of Operational Research, 117, 591-605 (1999) · Zbl 0937.90034
[25] Neumann, K.; Zimmermann, J., Procedures for resource levelling and net present value problems in project scheduling with general temporal and resource constraints, European Journal of Operational Research, 127, 425-443 (2000) · Zbl 0990.90058
[26] Neumann, K., Zimmermann, J., 2003. Exact and truncated branch-and-bound procedures for resource-constrained project scheduling with discounted cash flows and general temporal constraints. Central European Journal of Operations Research, to appear; Neumann, K., Zimmermann, J., 2003. Exact and truncated branch-and-bound procedures for resource-constrained project scheduling with discounted cash flows and general temporal constraints. Central European Journal of Operations Research, to appear · Zbl 1054.90039
[27] Neumann, K.; Nübel, H.; Schwindt, C., Active and stable project scheduling, Mathematical Methods of Operations Research, 52, 441-465 (2000) · Zbl 1023.90029
[28] Neumann, K., Schwindt, C., Zimmermann, J., 2002. Project Scheduling with Time Windows and Scarce Resources. Lecture Notes in Economics and Mathematical Systems, vol. 508. Springer, Berlin; Neumann, K., Schwindt, C., Zimmermann, J., 2002. Project Scheduling with Time Windows and Scarce Resources. Lecture Notes in Economics and Mathematical Systems, vol. 508. Springer, Berlin · Zbl 0986.90013
[29] Nübel, H., 1999. A branch-and-bound procedure for the resource investment problem subject to temporal constraints. Technical Report WIOR-574, University of Karl-sruhe; Nübel, H., 1999. A branch-and-bound procedure for the resource investment problem subject to temporal constraints. Technical Report WIOR-574, University of Karl-sruhe
[30] Pinson, E., Prins, C., Rullier, F., 1994. Using tabu search for solving the resource-constrained project scheduling problem. In: Proceedings of the Fourth International Workshop on Project Management and Scheduling, Leuven, pp. 102-106; Pinson, E., Prins, C., Rullier, F., 1994. Using tabu search for solving the resource-constrained project scheduling problem. In: Proceedings of the Fourth International Workshop on Project Management and Scheduling, Leuven, pp. 102-106
[31] Russell, A. H., Cash flows in networks, Management Science, 16, 357-373 (1970) · Zbl 0187.18201
[32] Sampson, S. E.; Weiss, E. N., Local search techniques for the generalized resource constrained project scheduling problem, Naval Research Logistics, 40, 665-675 (1993) · Zbl 0776.90039
[33] Schwindt, C., Minimizing earliness-tardiness costs of resource-constrained projects, (Inderfurth, K.; Schwödiauer, G.; Domschke, W.; Juhnke, F.; Kleinschmidt, P.; Wäscher, G., Operations Research Proceedings 1999 (2000), Springer: Springer Berlin), 402-407 · Zbl 1015.90043
[34] Schwindt, C.; Zimmermann, J., A steepest ascent approach to maximizing the net present value of projects, Mathematical Methods of Operations Research, 53, 435-450 (2001) · Zbl 1037.90034
[35] Yang, K. K.; Tay, L. C.; Sum, C. C., A comparison of stochastic scheduling rules for maximizing project net present value, European Journal of Operational Research, 85, 327-339 (1995) · Zbl 0912.90184
[36] Zhu, D.; Padman, R., A metaheuristic scheduling procedure for resource-constrained projects with cash flows, Naval Research Logistics, 46, 912-927 (1999) · Zbl 0959.90025
[37] Zimmermann, J., Project scheduling with discounted cash flows and general temporal constraints, (Inderfurth, K.; Schwödiauer, G.; Domschke, W.; Juhnke, F.; Klein-schmidt, P.; Wäscher, G., Operations Research Proceedings 1999 (2000), Springer: Springer Berlin), 419-424 · Zbl 1015.90045
[38] Zimmermann, J., Ablauforientiertes Projektmanagement: Modelle, Verfahren und Anwendungen (2001), Gabler: Gabler Wiesbaden
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.