%0 Journal Article
%T A Branch and Bound Approach to Solve the Preemptive Resource Leveling Problem
%A Behrouz Afshar-Nadjafi
%A Zeinab Khalaj
%A Esmaeil Mehdizadeh
%J International Journal of Manufacturing Engineering
%D 2013
%R 10.1155/2013/930920
%X 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
%U http://www.hindawi.com/journals/ijme/2013/930920/