MILP formulations for single- and multi-mode resource-constrained project scheduling problems

Abstract

This work presents new mixed-integer linear programming models for the deterministic single- and multi-mode resource constrained project scheduling problem with renewable and non-renewable resources. The modeling approach relies on the Resource-Task Network (RTN) representation, a network representation technique used in process scheduling problems, based on continuous time models. First, we propose new RTN-based network representation methods, and then we efficiently transform them into mathematical formulations including a set of constraints describing precedence relations and different types of resources. Finally, the applicability of the proposed formulations is illustrated using several example problems under the most commonly addressed objective, the makespan minimization.

Introduction

Project scheduling involves the construction of a precedence and resource feasible time schedule which identifies the starting and completion times of activities, under a specific objective. A project consists of a set of interconnected activities and resources, logically linked. These activities usually have to be performed for a successful project completion. However, there may exist alternatives for some, which vary in aspects such as duration, cost and required set of resources. For instance, only one of two activities must be performed to enable the start of their successor (e.g. the activity “heating food” must be preceded by one of the activities “oven on” or “microwave on”). Since, resources are usually limited and impose restrictions to project scheduling, they must be included in the project description. Logical links and precedence constraints for activities must also be incorporated.

Most resource-constrained project scheduling problems (RCPSPs) assume a single execution mode per activity, with specific time and resource requirements. Other problems include activities with various possible execution modes. Such problems are called multi-mode resource-constrained project scheduling problems (MRCPSPs), where the mode determines the duration of the activity and the resource requirements.

Slowinski (1980) categorized resources used by project activities as renewable, non-renewable, and doubly constrained. Renewable resources are periodically renewed, but their quantity is limited over each time period and may differ from one period to the next. Some examples are manpower, machines, equipment, power and fuel flow. For non-renewable resources, constraints on availability only concern total consumption over the whole period of project duration and not at each time period. Raw materials are a typical example of non-renewable resources, since they are available at a specific quantity for a project. Doubly constrained resource quantities are both per period and per project constrained. Money is an example of such resource, since there is usually a specific total budget for the entire project, as well as a limited cash flow per period, according to progress. As formally shown by Talbot (1982), each doubly constrained resource can be represented by one renewable and one non-renewable resource, respectively. Partially (non-)renewable resources, introduced by Böttcher, Drexl, and Kolisch (1996) limit the utilisation of resources within a subset of the planning horizon. Essentially, partially (non-)renewable resources can be viewed as a generic resource concept in project scheduling, as they include both renewable and non-renewable (and, hence doubly constrained) resources. An example is that of a planning horizon of a month with workers whose weekly working time is limited by their contract. It has been shown by Böttcher, Drexl, Kolisch, and Salewski (1999) that both renewable and non-renewable resource categories can be depicted by partially renewable resources.

Two representations have been commonly used to capture project networks, the Activity-on-Arc (AoA), which is event-based, and the Activity-on-Node (AoN), which is activity based. An Activity-on-Arc (AoA) diagram is based on the idea that each activity is a transition between two events; its beginning and its end. Each activity is represented as an arc which starts and finishes at a node (drawn as a circle). Each node represents an event, (a point of zero time duration) which signifies the completion of all activities leading into it and the beginning of all activities pointing out. Activity-on-Node (AoN), also known as precedence diagramming method, is a network representation for activity sequencing. Activity sequence diagrams use boxes or rectangles to represent the activities which are called nodes. The nodes are connected with other nodes by arrows, which show the dependencies between the connected activities. To construct an AoN network, we must draw one node for each activity and an arrow from all nodes i to nodes j, if activity i precedes activity j. The AoN has certain advantages over the AoA, since it represents activity interdependencies in a more natural way, it is easier to understand, even for inexperienced users, and easier to review when a change occurs in the network. A more thorough comparison of the two methods can be found in Kolisch and Padman (2001).

Blazewicz, Lenstra, and Rinnooy Kan (1983) have shown that the RCPSP is an NP-hard problem. When the solution has to additionally determine the assignment of modes (MRCPSP), further complexity is added since the solution search space is enlarged. Due to the high degree of complexity of RCPSPs and MRCPSPs, numerous heuristic and metaheuristic methods for them have been proposed in the literature. Although, heuristics may produce good solutions with few computational requirements and in a reasonable computation time, they ignore whether the solution can be proven to be correct. Contrary to exact algorithms which always produce an optimal solution. As this work focuses on exact mixed-integer linear programming (MILP) formulations for the RCPSP and MRCPSP, we refer to Hartmann and Kolisch (2000) and Kolisch and Hartmann (2006) for an elaborate study on state-of-the-art heuristic and metaheuristic methods. In our review we will examine exact state-of-the-art solution methods.

According to Herroelen (2005) computational results indicate that many of the 60-activity and most of the 90- and 120-activity instances from PSPLIB (Kolisch & Sprecher, 1996) are still beyond the solution capabilities of exact methods. Even recent papers using MILP models, such as Koné, Artigues, Lopez, and Mongeau (2011) deal with up to 25–35 activities. Pritsker, Watters, and Wolfe (1969) proposed a discrete-time mathematical formulation for multi-project scheduling which can also be used for the single-project case. The MILP model accommodated a wide range of conditions and supported objectives for minimizing the makespan and minimizing the total lateness. No computational results are available for this early study. Christofides, Alvarez-Valdés, and Tamarit (1987) developed a formulation similar to Pritsker et al., named CAT. The two formulations mainly differ in how they formulate the precedence constraints with the precedence constraints formulated by Christofides being disaggregated expressions of Pritsker's. The reported computational results are on randomly generated problems involving up to 25 activities and 3 resources. Two formulations with an exponential number of variables are those of Alvarez-Valdés and Tamarit (1993) and Mingozzi, Maniezzo, Ricciardelli, and Bianco (1998), making them more useful when calculating lower bounds. The first one proposes a continuous-time formulation based on the definition of a set IS of all minimal resource incompatible sets S. A resource incompatible set is a set of activities between which no precedence relation exists, but which would violate the resource constraints, if performed in parallel. The second one by Mingozzi et al. (1998), is a discrete-time formulation based on feasible subsets, that is activities that can be simultaneously executed without violating resource or precedence constraints. Schmidt and Grossmann (1996) proposed a single mode, slot-based continuous-time formulation with no resource constraints for the optimal scheduling of testing tasks in the new product development process of an agricultural chemical or pharmaceutical company. In subsequent work, the focus changed to the development of realistic models that could be solved for large-scale problems. Jain and Grossmann (1999) extended Schmidt's work by including resource constraints, and Maravelias and Grossmann (2004) further extended that model by allowing the allocation of different levels of resources and capacity expansion. On the same problem of scheduling of clinical trials in the pharmaceutical research and development pipeline, Colvin and Maravelias (2008) developed a basic resource-constrained multi-stage stochastic programming formulation (MSSP) model which was extended in Colvin and Maravelias (2009) to account for outlicensing and resource planning including outsourcing. In their recent work, Colvin and Maravelias (2010) focused on the development of new results that lead to smaller MSSP mixed-integer programming (MIP) formulations and the development of a solution algorithm to address problems that cannot be generated using commercial tools. Papageorgiou, Rotstein, and Shah (2001) proposed a MILP model assuming that enough resources are always available. The formulation integrates the selection of both a product development and introduction strategy and a capacity planning and investment strategy. Levis and Papageorgiou (2004) proposed a mathematical model, which is an extension of the previous work, determining both the product portfolio and the multi-site capacity planning in the face of uncertain clinical trials outcomes while taking into account the trading structure of the company. Recently, Koné et al. (2011) introduced two new MILP formulations: the Start/End Event-based (SEE) formulation (a variant of the event-based formulation proposed in Zapata, Hodge, & Reklaitis, 2008), and the On/Off Event-based (OOE) formulation. The variables in such formulations are fewer than in time-indexed ones, since they are not a function of the time horizon. They compared the event-based formulations with three other formulations issued from the literature, two of which (Christofides et al., 1987, Pritsker et al., 1969) use time-indexed variables, and a third formulation (Artigues, Michelon, & Reusser, 2003) that uses sequential variables. The computational results proved that the formulation proposed by Christofides et al. (1987) yields better results for exact solving on traditional test instances, The event-based formulations (more particularly the OOE) and the one by Artigues et al. (2003), have the advantage of solving more easily the instances involving very large scheduling horizons. Finally, their OOE formulation consistently outperformed the SEE on all tested instance sets.

Talbot (1982) proposed a model for multiple resource constraints where activities have multiple modes (MRCPSP). It considers the objective of minimizing the makespan under a given budget, and minimizing the total non-renewable resource consumption under the presence of a project due date. Zhu, Bard, and Ju (2006) proposed a branch-and-cut method based on Christofides et al. formulation (1987) for the MRCPSP, which gave very competitive results on benchmark problems. Sabzehparvar and Seyed-Hosseini (2008) presented a continuous-time formulation for the MRCPSP with Generalized Precedence Relations (MRCPSP-GPR) in which the minimal or maximal time lags between a pair of activities may vary depending on the chosen modes. In a recent paper from the process systems industry, Zapata et al. (2008) developed 3 different MILP models to address large-scale Multi-mode resource constrained multi-project scheduling problems (multi-mode RCMPSP), using continuous divisible resources and continuous time. Each model handles the time domain in a different way.

Project scheduling problems have been studied under various types of objective functions, such as maximizing the Net Present Value (NPV), introduced by Russell (1970), minimizing resource availability costs (Demeulemeester, 1995, Kimms, 1998), and multi-objective scheduling (Bomsdorf and Derigs, 2008, Nabrzyski and Weglarz, 1994). The most popular objective function discussed in the project scheduling literature is undoubtedly the time-based objective of minimizing the project makespan. Most often it is recognized as the most relevant objective in various review papers (Hartmann and Briskorn, 2010, Herroelen, 2005, Kolisch, 1996, Kolisch and Sprecher, 1996).

The main scope of this work is to extend and therefore apply modeling and network representation techniques used in the process industry to RCPSP and MRCPSP problems. The manuscript is organized as follows. In Section 2, a new representation of project scheduling problems based on the RTN concept is presented. In Sections 3 MILP formulation for the single-mode RCPSP, 4 MILP formulation for the MRCPSP, we propose new MILP formulations for RCPSPs and MRCPSPs, including precedence relations, different types of resources, time, and other constraints. Afterwards, the applicability of the proposed formulations to several project scheduling problems is demonstrated in Section 5. Finally, concluding remarks are drawn in Section 6.