The preemptive Multimode resource investment problem is investigated. The Objective is to minimize the total renewable/nonrenewable resource costs and earliness-tardiness costs by a given project deadline and due dates for activities. In this problem setting preemption is allowed with no setup cost or time. The project contains activities interrelated by finish-start type precedence relations with a time lag of zero, which require a set of renewable and nonrenewable resources. The problem formed in this way is an NP-hard. A mixed integer programming formulation is proposed for the problem and parameters tuned genetic algorithm (GA) is proposed to solve it. To evaluate the performance of the proposed algorithm, 120 test problems are used. Comparative statistical results reveal that the proposed GA is efficient and effective in terms of the objective function and computational times. 1. Introduction The resource constrained project scheduling problem (RCPSP) is a known combinatorial optimization problem which is NP-hard [1]. The objective of RCPSP is to minimize the makespan of the project while the renewable resources availabilities are considered given. In the literature there are several exact methods and heuristics that solve the RCPSP [2–9]. In the multimode version of the RCPSP (MRCPSP), each activity can be performed in one out of a set of modes, with a specific activity duration and resource requirements. The problem involves the selection of a mode for each activity and the determination of the activity start or finish times such that project makespan is minimized. However, the precedence and resource constraints should be satisfied. MRCPSP is also NP-hard as generalization of the RCPSP. In recent years several algorithms have been proposed to solve MRCPSP [10–20]. The resource investment problem (RIP) is a close variant of RCPSP. This problem consists of determination of the activities start times and renewable resources availabilities such that the total cost of the resources is minimized subject to a given project deadline. In RIP, project’s makespan is not forgotten but it is controlled with a predetermined deadline as a constraint. This problem was introduced by M？hring [21]. He showed that the problem is NP-hard. Rangaswamy [22] proposed a B&B for the RIP and applied it to the same instance set used by Demeulemeester [23]. Drexl and Kimms proposed two lower bound procedures for the RIP based on Lagrangian relaxation and column generation methods [24]. Other exact procedures are proposed by Demeulemeester [23] and Rodrigues and Yamashita
References
[1]
J. Blazewicz, J. K. Lenstra, and A. H. Rinnooy Kan, “Scheduling subject to resource constraints: classification and complexity,” Discrete Applied Mathematics, vol. 5, no. 1, pp. 11–24, 1983.
[2]
R. Kolisch and S. Hartmann, “Experimental investigation of heuristics for resource-constrained project scheduling: an update,” European Journal of Operational Research, vol. 174, no. 1, pp. 23–37, 2006.
[3]
H. Zhang, H. Li, and C. M. Tam, “Particle swarm optimization for resource-constrained project scheduling,” International Journal of Project Management, vol. 24, no. 1, pp. 83–92, 2006.
[4]
J. R. Montoya-Torres, E. Gutierrez-Franco, and C. Pirachicán-Mayorga, “Project scheduling with limited resources using a genetic algorithm,” International Journal of Project Management, vol. 28, no. 6, pp. 619–628, 2010.
[5]
S. Hartmann and D. Briskorn, “A survey of variants and extensions of the resource-constrained project scheduling problem,” European Journal of Operational Research, vol. 207, no. 1, pp. 1–14, 2010.
[6]
A. Agarwal, S. Colak, and S. Erenguc, “A neurogenetic approach for the resource-constrained project scheduling problem,” Computers & Operations Research, vol. 38, no. 1, pp. 44–50, 2011.
[7]
C. Fang and L. Wang, “An effective shuffled frog-leaping algorithm for resource-constrained project scheduling problem,” Computers & Operations Research, vol. 39, no. 5, pp. 890–901, 2012.
[8]
O. Koné, “New approaches for solving the resource-constrained project scheduling problem,” 4OR, vol. 10, no. 1, pp. 105–106, 2012.
[9]
D. C. Paraskevopoulos, C. D. Tarantilis, and G. Ioannou, “Solving project scheduling problems with resource constraints via an event list-based evolutionary algorithm,” Expert Systems with Applications, vol. 39, no. 4, pp. 3983–3994, 2012.
[10]
G. Zhu, J. F. Bard, and G. Yu, “A branch-and-cut procedure for the multimode resource-constrained project-scheduling problem,” INFORMS Journal on Computing, vol. 18, no. 3, pp. 377–390, 2006.
[11]
H. Zhang, C. M. Tam, and H. Li, “Multimode project scheduling based on particle swarm optimization,” Computer-Aided Civil and Infrastructure Engineering, vol. 21, no. 2, pp. 93–103, 2006.
[12]
A. Lova, P. Tormos, and F. Barber, “Multi-mode resource constrained project scheduling: scheduling schemes, priority rules and mode selection rules,” Inteligencia Artificial, vol. 10, no. 30, pp. 69–86, 2006.
[13]
B. Jarboui, N. Damak, P. Siarry, and A. Rebai, “A combinatorial particle swarm optimization for solving multi-mode resource-constrained project scheduling problems,” Applied Mathematics and Computation, vol. 195, no. 1, pp. 299–308, 2008.
[14]
M. Ranjbar, B. de Reyck, and F. Kianfar, “A hybrid scatter search for the discrete time/resource trade-off problem in project scheduling,” European Journal of Operational Research, vol. 193, no. 1, pp. 35–48, 2009.
[15]
A. Lova, P. Tormos, M. Cervantes, and F. Barber, “An efficient hybrid genetic algorithm for scheduling projects with resource constraints and multiple execution modes,” International Journal of Production Economics, vol. 117, no. 2, pp. 302–316, 2009.
[16]
J. Coelho and M. Vanhoucke, “Multi-mode resource-constrained project scheduling using RCPSP and SAT solvers,” European Journal of Operational Research, vol. 213, no. 1, pp. 73–82, 2011.
[17]
M. Ranjbar, “An optimal NPV project scheduling with fixed work content and payment on milestones,” International Journal of Industrial Engineering & Production Research, vol. 22, no. 3, pp. 181–186, 2011.
[18]
A. Barrios, F. Ballestin, and V. Valls, “A double genetic algorithm for the MRCPSP/max,” Computers & Operations Research, vol. 38, no. 1, pp. 33–43, 2011.
[19]
B. Afshar-Nadjafi, A. Rahimi, and H. Karimi, “A genetic algorithm for mode identity and the resource constrained project scheduling problem,” Scientia Iranica, vol. 20, no. 3, pp. 824–831, 2013.
[20]
E. N. Afruzi, E. Roghanian, A. A. Najafi, and M. Mazinani, “A multi-mode resource-constrained discrete time-cost tradeoff problem solving using an adjusted fuzzy dominance genetic algorithm,” Scientia Iranica, vol. 20, no. 3, pp. 931–944, 2013.
[21]
R. H. M？hring, “Minimizing costs of resource requirements in project networks subject to a fixed completion time,” Operations Research, vol. 32, no. 1, pp. 89–120, 1984.
[22]
B. Rangaswamy, Multiple resource planning and allocation in resource- constrained project networks [Ph.D. thesis], Graduate School of Business, University of Colorado, 1998.
[23]
E. Demeulemeester, “Minimizing resource availability costs in time-limited project networks,” Management Science, vol. 41, no. 10, pp. 1590–1598, 1995.
[24]
A. Drexl and A. Kimms, “Optimization guided lower and upper bounds for the resource investment problem,” Journal of the Operational Research Society, vol. 52, no. 3, pp. 340–351, 2001.
[25]
S. B. Rodrigues and D. S. Yamashita, “An exact algorithm for minimizing resource availability costs in project scheduling,” European Journal of Operational Research, vol. 206, no. 3, pp. 562–568, 2010.
[26]
D. S. Yamashita, V. Amaral Armentano, and M. Laguna, “Scatter search for project scheduling with resource availability cost,” European Journal of Operational Research, vol. 169, no. 2, pp. 623–637, 2006.
[27]
S. Shadrokh and F. Kianfar, “A genetic algorithm for resource investment project scheduling problem, tardiness permitted with penalty,” European Journal of Operational Research, vol. 181, no. 1, pp. 86–101, 2007.
[28]
M. Ranjbar, F. Kianfar, and S. Shadrokh, “Solving the resource availability cost problem in project scheduling by path relinking and genetic algorithm,” Applied Mathematics and Computation, vol. 196, no. 2, pp. 879–888, 2008.
[29]
V. Van Peteghem and M. Vanhoucke, “An artificial immune system algorithm for the resource availability cost problem,” Flexible Services and Manufacturing Journal, vol. 25, no. 1-2, pp. 122–144, 2013.
[30]
L. Kaplan, Resource constrained project scheduling with preemption of jobs [Ph.D. thesis], University of Michigan, Ann Arbor, Mich, USA, 1988.
[31]
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.
[32]
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.
[33]
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.
[34]
J. Damay, A. Quilliot, and E. Sanlaville, “Linear programming based algorithms for preemptive and non-preemptive RCPSP,” European Journal of Operational Research, vol. 182, no. 3, pp. 1012–1022, 2007.
[35]
J. Buddhakulsomsiri and D. S. Kim, “Properties of multi-mode resource-constrained project scheduling problems with resource vacations and activity splitting,” European Journal of Operational Research, vol. 175, no. 1, pp. 279–295, 2006.
[36]
V. Van Peteghem and M. Vanhoucke, “A genetic algorithm for the preemptive and non-preemptive multi-mode resource-constrained project scheduling problem,” European Journal of Operational Research, vol. 201, no. 2, pp. 409–418, 2010.
[37]
M. Vanhoucke, E. Demeulemeester, and W. Herroelen, “An exact procedure for the resouce-constrained weighted earliness-tardiness project scheduling problem,” Annals of Operations Research, vol. 102, pp. 179–196, 2001.
[38]
Y. Khoshjahan, A. A. Najafi, and B. Afshar-Nadjafi, “Resource constrained project scheduling problem with discounted earliness-tardiness penalties: mathematical modeling and solving procedure,” Computers and Industrial Engineering, vol. 66, no. 2, pp. 293–300, 2013.
[39]
N. Runge and F. Sourd, “A new model for the preemptive earliness-tardiness scheduling problem,” Computers & Operations Research, vol. 36, no. 7, pp. 2242–2249, 2009.
[40]
B. Afshar Nadjafi and S. Shadrokh, “A branch and bound algorithm for the weighted earliness-tardiness project scheduling problem with generalized precedence relations,” Scientia Iranica, vol. 16, no. 1 E, pp. 55–64, 2009.
[41]
K. Bülbül, P. Kaminsky, and C. Yano, “Preemption in single machine earliness/tardiness scheduling,” Journal of Scheduling, vol. 10, no. 4-5, pp. 271–292, 2007.
[42]
P. Baptiste, J. Carlier, A. Kononov, M. Queyranne, S. Sevastyanov, and M. Sviridenko, “Structural properties of optimal preemptive schedules,” Diskretnyi Analizi Issledovanie Operatsii, vol. 16, no. 1, pp. 3–36, 2009.
[43]
P. Baptiste, J. Carlier, A. Kononov, M. Queyranne, S. Sevastyanov, and M. Sviridenko, “Properties of optimal schedules in preemptive shop scheduling,” Discrete Applied Mathematics, vol. 159, no. 5, pp. 272–280, 2011.
[44]
A. Sprecher, S. Hartmann, and A. Drexl, “An exact algorithm for project scheduling with multiple modes,” OR Spektrum. Quantitative Approaches in Management, vol. 19, no. 3, pp. 195–203, 1997.
[45]
S. Hartmann and R. Kolisch, “Experimental evaluation of state-of-the-art heuristics for the resource-constrained project scheduling problem,” European Journal of Operational Research, vol. 127, no. 2, pp. 394–407, 2000.
[46]
G. Taguchi, Introduction to Quality Engineering, Asian Productivity Organization, Tokyo, Japan, 1986.
[47]
A. Drexl, R. Nissen, J. H. Patterson, and F. Salewski, “ProGen/x—an instance generator for resource constrained project scheduling problems with partially renewable resources and further extensions,” European Journal of Operational Research, vol. 125, pp. 59–72, 2000.
