We study resource constrained project scheduling problem with respect to resource leveling as objective function and allowance of preemption in activities. The branch and bound algorithms proposed in previous researches on resource leveling problem do not consider preemption. So, representing a model for the problem, a branch and bound algorithm is proposed. This algorithm can handle preemption in resource leveling problem. Comparing the resource leveling problem and the preemptive resource leveling problem, it is observed that considering preemption in the problem leads to better results in the objective function. This improvement imposes additional time to solve the problem. Coding the algorithm in MATLAB and checking it on the projects with 8 and 10 activities, results show that the proposed algorithm is efficient. 1. Introduction Increasing international competition enforces utilization of very expensive resources (e.g., heavy machines) by most of the companies. Thus, resource constrained project scheduling problem (RCPSP) has attracted more attention. Several objective functions are studied in RCPSP. Resource leveling is one of them, in which the variation of resource utilization is to be minimized. In addition to resource constraints, minimum and maximum time lags between different activities have to be observed in general. Several studies have been done for RCPSP. The first mathematical formulation of the RCPSP was given by Pritsker et al. [1]. Then, Kaplan [2], Olaguíbel and Goerlich [3], and Klein and Scholl [4] continued their job. In addition, Blazewicz et al. proved that RCPSP is NP-hard [5]. Kastor and Sirakoulis analyzed the effectiveness of three resource leveling problem tools on RCPSP: Primavera p6.0, Microsoft Project 2007, and Open Workbench 1.1.6 [6]. For resource leveling problems with minimum time lags, several exact and heuristic solution procedures have been studied. Exact algorithms contain enumeration, integer programming, or dynamic programming techniques. Tavares represented the effectiveness of resource leveling problem in costs [7]. Ahuja [8], Easa [9], Bandelloni et al. [10], Demeulemeester [11], and Younis and Saad [12] presented exact procedures for resource leveling problem. Nübel developed a branch and bound procedure (BB) upon minimal delaying alternative and disjunction precedence constraints [13]. Demeulemeester and Herroelen proposed a model for project scheduling problem with resource constraints and preemption and a model for resource leveling problem and solved it with some methods, such as BB [14]. Gather et
References
[1]
A. A. B. Pritsker, L. J. Watters, and P. M. Wolfe, “Multi-project scheduling with limited resources: a zero-one programming approach,” Management Science, vol. 16, no. 1, pp. 93–108, 1969.
[2]
L. A. Kaplan, Resource-constrained project scheduling with preemption of jobs [Ph.D. thesis], University of Michigan, 1988.
[3]
R. A.-V. Olaguíbel and J. T. Goerlich, “The project scheduling polyhedron: dimension, facets and lifting theorems,” European Journal of Operational Research, vol. 67, no. 2, pp. 204–220, 1993.
[4]
R. Klein and A. Scholl, “Computing lower bounds by destructive improvement: an application to resource-constrained project scheduling,” European Journal of Operational Research, vol. 112, no. 2, pp. 322–346, 1999.
[5]
J. Blazewicz, J. K. Lenstra, and A. H. G. R. Kan, “Scheduling subject to resource constraints: classification and complexity,” Discrete Applied Mathematics, vol. 5, no. 1, pp. 11–24, 1983.
[6]
A. Kastor and K. Sirakoulis, “The effectiveness of resource levelling tools for Resource Constraint Project Scheduling Problem,” International Journal of Project Management, vol. 27, no. 5, pp. 493–500, 2009.
[7]
L. V. Tavares, “A review of the contribution of Operational Research to Project Management,” European Journal of Operational Research, vol. 136, no. 1, pp. 1–18, 2002.
[8]
H. N. Ahuja, Construction Performance Control By Networks, John Wiley & Sons, 1976.
[9]
S. M. Easa, “RL in construction by optimization,” Journal of Construction Engineering and Management, vol. 115, pp. 302–316, 1989.
[10]
M. Bandelloni, M. Tucci, and R. Rinaldi, “Optimal resource leveling using non-serial dyanamic programming,” European Journal of Operational Research, vol. 78, no. 2, pp. 162–177, 1994.
[11]
E. Demeulemeester, “Minimizing resource availability costs in time-limited project networks,” Management Science, vol. 41, pp. 1590–1598, 1995.
[12]
M. A. Younis and B. Saad, “Optimal resource leveling of multi-resource projects,” Computers and Industrial Engineering, vol. 31, no. 1-2, pp. 1–4, 1996.
[13]
H. Nübel, “A branch-and-bound procedure for the resource investment problem with generalized precedence constraints,” Tech. Rep. WIOR-516, 1998.
[14]
E. Demeulemeester and W. Herroelen, Project Scheduling A Research Handbook, 2002.
[15]
T. Gather, J. Zimmermann, and J.-H. Bartels, “Exact methods for the resource levelling problem,” Journal of Scheduling, vol. 14, no. 6, pp. 557–569, 2011.
[16]
K. Neumann and J. Zimmermann, “Heuristic methods for resource-constrained project scheduling with regular and non-regular objective functions and schedule-dependent time windows,” in Project Scheduling: Recent Models, Algorithms, and Applications, J. Weglarz, Ed., pp. 261–287, Kluwer Academic Publishers, Boston, Mass, USA, 1999.
[17]
K. Neumann and J. Zimmermann, “Procedures for resource leveling and net present value problems in project scheduling with general temporal and resource constraints,” European Journal of Operational Research, vol. 127, no. 2, pp. 425–443, 2000.
[18]
E. Coughlan, M. Lübbecke, and J. Schulz, “A branch-and-price algorithm for multi-mode resource leveling,” in Experimental Algorithms, vol. 6049 of Lecture Notes in Computer Science, pp. 226–238, 2010.
[19]
K. Brinkmann and K. Neumann, “Heuristic procedures for resource-constrained project scheduling with minimal and maximal time lags: the resource-leveling and minimum project duration problems,” Journal of Decision Systems, vol. 5, pp. 129–155, 1996.
[20]
K. Neumann and J. Zimmermann, “Resource levelling for projects with schedule-dependent time windows,” European Journal of Operational Research, vol. 117, no. 3, pp. 591–605, 1999.
[21]
D. Savin, S. Alkass, and P. Fazio, “Construction resource leveling using neural networks,” Canadian Journal of Civil Engineering, vol. 23, no. 4, pp. 917–925, 1996.
[22]
D. Savin, S. Alkass, and P. Fazio, “A procedure for calculating the weight-matrix of a neural network for resource leveling,” Advances in Engineering Software, vol. 28, no. 5, pp. 277–283, 1997.
[23]
J. J. Moder and C. R. Phillips, Project Management with CPM and PERT, Van Nostrand Reinhold, 1970.
[24]
J. J. Moder, C. R. Phillips, and E. W. Davis, Project Management With CPM, PERT and Project Diagramming, Van Nostrand Reinhold, 1983.
[25]
R. B. Harris, Precedence and Arrow Networking Techniques for Construction, John Wiley & Sons, 1978.
[26]
R. B. Harris, “Packing method for resource leveling (pack),” Journal of Construction Engineering and Management, vol. 116, no. 2, pp. 331–350, 1990.
[27]
M. Takamoto, N. Yamada, Y. Kobayashi, H. Nonaka, and S. Okoshi, “Zero-one quadratic programming algorithm for resource leveling of manufacturing process schedules,” Systems and Computers in Japan, vol. 26, no. 10, pp. 68–76, 1995.
[28]
E. L. Demeulemeester and W. S. Herroelen, “An efficient optimal solution procedure for the preemptive resource-constrained project scheduling problem,” European Journal of Operational Research, vol. 90, no. 2, pp. 334–348, 1996.
[29]
J. H. Patterson, R. Slowinski, F. B. Talbot, and J. Weglarz, “An algorithm for a general class of precedence and resource constrained scheduling problems,” Advances in Project Scheduling, vol. 187, pp. 3–28, 1989.
[30]
A. Sprecher, Resource-Constrained Project Scheduling—Exact Methods For the Multi-Mode Case, Lecture Notes in Economics and Mathematical Systems, 1994.
[31]
J. P. Stinson, E. W. Davis, and B. M. Khumawala, “Multiple resource-constrained scheduling using branch-and-bound,” AIIE Trans, vol. 10, no. 3, pp. 252–259, 1978.
[32]
E. Demeulemeester and W. S. Herroelen, “A branch-and-bound procedure for the multiple resource-constrained project scheduling problem,” Management Science, vol. 38, pp. 1803–1818, 1992.
[33]
G. Igelmund and F. J. Radermacher, “Preselective strategies for the optimization of stochastic project networks under resource constraints,” Networks, vol. 13, no. 1, pp. 1–28, 1983.
[34]
B. De Reyck and W. Herroelen, “A branch-and-bound procedure for the resource-constrained project scheduling problem with generalized precedence relations,” European Journal of Operational Research, vol. 111, no. 1, pp. 152–174, 1998.
[35]
B. Afshar-Nadjafi, H. Najjarbashi, and E. Mehdizadeh, “A branch-and-bound procedure for RL in multi-mode resource constraint project scheduling problem,” Research Journal of Recent Sciences, vol. 1, no. 7, pp. 33–38, 2012.
[36]
F. Ballestín, V. Valls, and S. Quintanilla, “Pre-emption in resource-constrained project scheduling,” European Journal of Operational Research, vol. 189, no. 3, pp. 1136–1152, 2008.
[37]
F. Ballestín, V. Valls, and S. Quintanilla, “Scheduling projects with limited number of preemptions,” Computers and Operations Research, vol. 36, no. 11, pp. 2913–2925, 2009.
[38]
M. Vanhoucke and D. Debels, “The impact of various activity assumptions on the lead time and resource utilization of resource-constrained projects,” Computers and Industrial Engineering, vol. 54, no. 1, pp. 140–154, 2008.
