Abstract.
In this paper we study a resource constrained project scheduling problem in which the resource usage of each activity may vary over time proportionally to its varying intensity. We formalize the problem by means of a mixed integer-linear program, prove that feasible solution existence is NP-complete in the strong sense and propose a branch-and-cut algorithm for finding optimal solutions. To this end, we provide a complete description of the polytope of feasible intensity assignments to two variable-intensity activities connected by a precedence constraint along with a fast separation algorithm. A computational evaluation confirms the effectiveness of our method on various benchmark instances.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Ahuja, R.K., Magnanti, T.L., Orlin, J.B.: Network Flows. Prentice Hall, Englewood Cliffs, New Jersey, 1993
Blazewicz, J., Ecker, K.H., Pesch, E., Schmidt, G., Weglarz, J.: Scheduling Computer and Manufacturing Processes. 2nd edition, Springer-Verlag, Berlin, Heidelberg, New-York, 2001
Brucker, P., Drexl, A., Möhring, R., Neumann, K., Pesch, E.: Resource-constrained project scheduling: Notation, classification, models and methods. Eur. Jour. Ops. Res. 112, 3–41 (1999)
Coelho, J.: Personal communication. 2003
De Boer, R.: Resource-Constrained Multi-Project Management - A Hierarchical Decision Support System. Ph.D. thesis, Twente University Press, The Netherlands, 1998
Demeulemeester, E.L., Herroelen, W.S.: Project Scheduling: A Research Handbook. Kluwer Academic Publ., International series in operations research and management science 49, 2002
Ford, L.R., Fulkerson, D.R.: Maximal flow through a network. Canadian J. Math. 8, 399–404 (1956)
Garey, M.R., Johnson, D.S.: Computers and Intractability: A guide to the Theory of NP-Completeness. W. H. Freeman and Co., San Francisco, 1979
Gonzalez, T., Sahni, S.: Flowshop and jobshop schedules: Complexity and approximation. Oper. Res. 26/1, 36–52 (1978)
Graham, R.L., Lawler, E.L., Lenstra, J.K., Rinnooy Kan, A.H.G.: Optimization and approximation in deterministic sequencing and scheduling theory: a survey. Ann. Discrete Math. 5, 287–326 (1979)
Hans, E.W.: Resource loading by branch-and-price techniques. Ph.D. thesis, Twente University Press, The Netherlands, 2001
Hans, E.W.: Personal communication. 2003
Herroelen, W.S., De Reyck, B., Demeulemeester, E.L.: Resource-constrained project scheduling: a survey of recent developments. Comput. Ops. Res. 25/4, 279–302 (1998)
Hoffman, A.J., Kruskal, J.B.: Integral boundary points of convex polyhedra. In: H.W. Kuhn, A.W. Tucker (eds.), Linear Inequalities and Related Systems, Princeton University Press, Princeton, 1956, pp. 233–246
ILOG: ILOG CPLEX 7.5, User’s manual. ILOG S.A, Gentilly, France, 2001
Jünger, M., Reinelt, G., Thienel, S.: Practical problem solving with cutting plane algorithms in combinatorial optimization. DIMACS Ser. in Discr. Math. and Theor. Comput. Sci. 20, 111–152 (1995)
Kolisch, R., Sprecher, A., Drexl, A.: Characterization and generation of a general class of resource-constrained project scheduling problems. Technical Report, 301, University of Kiel, Germany, 1992
Kolisch, R., Sprecher, A.: PSPLIB – a project scheduling library. Eur. Jour. Ops. Res. 96, 205–216 (1997)
Leachman, R.C., Dincerler, A., Kim, S.: Resource constrained scheduling of projects with variable-intensity activities. IIE Trans. 22/1, 31–40 (1990)
Nemhauser, G.L., Wolsey, L.A.: Integer and Combinatorial Optimization. John Wiley & Sons, New York, 1988
Padberg, M.W., Van Roy, T.J., Wolsey, L.A.: Valid linear inequalities for fixed charge problems. Oper. Res. 33/4, 842–861 (1985)
Padberg, M.W., Rinaldi, G.: Optimization of a 532 city symmetric traveling salesman problem by branch and cut. Oper. Res. Lett. 6, 1–7 (1987)
Schrijver, A.: Theory of linear and integer programming. John Wiley & Sons, Chicester, 1986
Tavares, L.V.: Advanced models for project management. Kluwer Academic Publishers, 1998, pp. 177–216
Tavares, L.V.: A review of the contribution of operational research to project management. Eur. Jour. Ops. Res. 136, 1–18 (2002)
Weglarz, J.: Project scheduling with continuously-divisible doubly constrained resources. Management Science 27/9, 1040–1053 (1981)
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Kis, T. A branch-and-cut algorithm for scheduling of projects with variable-intensity activities. Math. Program. 103, 515–539 (2005). https://doi.org/10.1007/s10107-004-0551-6
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10107-004-0551-6