Article Preview
TopIntroduction
A project is a set of interrelated activities to be executed over a fixed period to create a unique product or service. Project management aims to find effective and efficient ways for planning, organizing, directing, scheduling and controlling the resources. Wide application areas of project management attract the operational researchers for modelling and solving various problems. Dating back to 1950s, problem natures, methodologies and solution approaches have been changing for new practical problems.
As an important step of project management, project scheduling defines the start and finish times of the project activities. Depending on the resource needs and types, various project scheduling problems can be defined and studied. The earliest method in this area is the critical path method (CPM) that finds the critical path through the earliest and latest start and finish times for each activity without making the project longer for an unlimited resource availability case.
CPM’s assumption of unlimited availability of resources hardly holds in real life. In the presence of resource constraints, resource constrained project scheduling problems (RCPSP) are presented. Even though new resource types have been introduced recently, basic categories are renewable and non-renewable resources. Renewable resources are temporarily available for some time periods. They can be dedicated to some activities when they are available and they can be used again after completion of these activities. Labor, machine, equipment can be examples of renewable resources. Non-renewable resources are consumed with usage. The availability of a non-renewable resource is limited with its capacity for the entire project. It is common to assume that non-renewable resources are released as a lump sum at the beginning of the project, but they can be also released in a progressive way throughout the project. A budget of the project can be an example of non-renewable resources. Recently, other resource types such as doubly constrained, partially renewable which have some features of renewable and non-renewable resources are introduced. Chaleshtarti and Shadrokh (2014) propose exact solution approaches for a RCPSP with both renewable and non-renewable resources. For problem instances that cannot be solved optimally, Kolisch and Hartmann (2005) summarize a large number of heuristics for the RCPSP. For a comprehensive review of the RCPS problems with their variants and extensions the reader is referred to Kolisch and Padman (2001), and Hartmann and Briskorn (2010).
A generalization of RCPSP is the multi-mode RCPSP (MRCPSP). In the MRCPS problems each activity can be executed in one of the several modes, where a mode is defined by a processing time and a resource requirement amount. For the minimum project completion time MRCPSP, some noteworthy optimization studies are due to Talbot (1982), Sprecher, Hartmann, and Drexl (1997), Demeulemeester, De Reyck, and Herroelen (2000) and Hafizoglu and Azizoglu (2010). Alcaraz, Maroto, and Ruiz (2003), Ranjbar and Kianfar (2007), Van Peteghem and Vanhoucke (2009), Jozefowska, Mika, Rozycki, Waligora, and Weglarz (2001) and Ranjbar, De Reyck, and Kianfar (2009) present approximation studies. For the extensive review of the MRCPS problems we refer the reader to Weglarz, Jozefowska, Mika, and Waligora (2011).
In this study, we assume that there is a single non-renewable resource that is released at specified times and specified quantities in a progressive way. Resource units are consumed when the activities are completed. There are several modes, i.e., time/resource pairs for each non-dummy activity. Our decision is to select a mode for each activity to minimize the project completion time without violating resource availability constraints.