|
Article Excerpt
We consider the problem of minimizing project duration in an environment where each project activity can be executed by a number of different flexible resources. The capabilities of the flexible resources are modeled using a binary activity-resource matrix A called the availability matrix. Activity durations are known deterministically. We develop tight lower bounds and a variety of heuristics accompanied with extensive computational tests regarding their performance. It is shown that our algorithms consistently perform near optimally. Using these heuristics, we perform experiments on the effect of operating flexibility on project duration, where resource flexibility is measured by the number of resources available per activity, and the form of the availability matrix A. Our experiments lead to important managerial guidelines, regarding the role of resource flexibility on project duration. For instance, it is found that when the flexible capabilities of the resources are evenly distributed across the activiti es, small improvements in resource flexibilites provide nearly the same benefits in project duration as a system of fully flexible resources.
(Resource Management; Flexibility; Integer Programming Optimization; Heuristics)
1. Introduction
The Resource-Constrained fob Assignment Problem (RCJAP) involves the scheduling of project activities subject to technological and resource constraints so as to minimize the total project duration. Given are a set P of resources available to process a set J of activities, and the precedence network N which may or may not be connected; the latter case is equivalent to the case of multiple projects. To be executed, each activity in J requires a single unit of resource per time period. However, the specific resource type used to execute the jth activity in J can be any resource from a subset [P.sub.j] [subset or equal to] P of the set of resources. Activity durations are known deterministically and do not depend on the specific resource used to execute any given activity. No preemption is allowed for activities, each resource may execute one activity at a time, and each activity can use at most one resource type. Cast differently, our objective is to exploit the flexibility of assigning activities to alternative resource types s o as to minimize project duration.
A "resource" refers to any mechanism that is capable of playing the role of a supplier, a worker, an automated piece of equipment, or anything else that can execute a task. The tasks are generically called activities. For instance, a piece of automated equipment may be able to perform the necessary drilling and milling operations required for a product. Or, a particular supplier may be able to supply some electrical and mechanical subassemblies required for the manufacture of a new product. Below we cite project management applications of our model as well as related literature.
Audit firms engage in a number of audits, each of which is expected to start and complete at certain dates, and employ auditors with various levels of expertise to execute the audit tasks. Depending on his/her expertise, every auditor is able to execute a subset of the set J of tasks. A typical audit firm is involved with multiple audit engagements, some of which exhibit complex interdependencies. Such business environments are also encountered in internal auditing operations where the auditors carry out interdepartmental tasks. Regardless of the source, efficient scheduling of external as well as internal auditing operations is very important. In this application, audit tasks correspond to activities, the totality of audit engagements correspond to the project network N, auditors are the resources, and [P.sub.j] is the subset of auditors capable of performing audit j. Each audit is assigned precisely one auditor (i.e., a single unit of resource per period), and the amount of time required to process an audit task does not differ substantially from auditor to auditor. The scheduling objectives of an audit manager may be the identification of a feasible schedule, minimization of project duration, or the minimization of auditor salary costs.
Project auditing literature addresses loading and scheduling issues. Loading refers to the amount of workload per auditor. It includes Summers (1972) and Balachandran and Zoltners (1981), who present mathematical programming formulations for assigning auditors to tasks. Level loading objectives are addressed in Bailey et al. (1974) and Balachandran and Steuer (1982). The problem of scheduling auditors to individual audit tasks was first addressed in Chan and Dodin (1986), who presented an integer linear program for developing optimal or near-optimal schedules for a variety of audit-scheduling objectives. Dodin and Chan (1991) extended their seminal work by incorporating delay costs when activities are completed beyond their due date, as well as auditor-dependent durations for the activities. Their objective was to minimize total costs (primarily driven by salaries). Dodin and Elimam (1997) extended the latter model to allow for generalized precedence constraints (see Elmaghraby and Kamburowski 1992) and audit or-dependent setup costs for the activities. The above audit-scheduling research has demonstrated that the resulting mathematical formulations are quite complex, requiring a few hundred constraints and variables for small activity networks. Hence, the size of solvable problems is limited by the state of the art in integer programming. Using several complexity-reduction techniques, the 19-activity network considered in Dodin and Elimam (1997) required 250 constraints and 310 variables.
The paper most related to this research is by Drexl (1991), who considered a version of RCJAP with resource-dependent activity durations and costs with the objective of minimizing total cost. This problem, while less general than the problem considered in the above-mentioned audit-scheduling literature, has several applications in resource management as well as project auditing. An efficient branch-and-bound optimal algorithm is developed that can quickly solve problems with up to 20 activities and 6 resource modes. A heuristic algorithm is developed for larger problems, and its performance is tested on problem sizes of up to 200 activities. Regarding the complexity of this problem, Drexl (1991) shows that a 20-activity instance of his RCJAP formulation requires 497 binary variables and 207 constraints.
The model presented in this article is a special case of Dodin and Elimam (1997), where the cost parameters are chosen to minimize project duration. By incorporating due dates for the entire project or the individual activities, our model can be used by project managers before they commit to due dates requested by customers, or it can be used to determine the range of feasible values for project duration when trying to minimize project cost. These values are very important in reducing the search space of the branch-and-bound tree in Drexl (1991) or the number of variables required in the formulations presented in Dodin and Chan (1991) and Dodin and Elimam (1997).
Another major objective of our research is to identify the effect of operating flexibility on project duration. The notion of operating flexibility is captured by the multiplicity of resource types that may be used to execute each activity. We develop algorithms on how best to take advantage of the processing flexibility for a given set of resources. In case the set of available resources can be selected amongst numerous alternatives, our research points to the most effective portfolio of such resource alternatives. In the context of project auditing, our algorithms provide efficient schedules that take best advantage of the distinct expertise and skill characteristics of the various project auditors. When hiring new auditors to join the existing workforce, our algorithms can be used to identify the type of skills that would be required by the new team member so as to best complement the existing auditors in terms of efficiency. In manufacturing applications, the resources may be machines. The flexibility cha racteristics of these machines vary widely, raising the question of how to manage a system of existing machines so as to best utilize processing flexibility to optimize throughput performance or to select a production system with a portfolio of flexible characteristics capable of delivering high throughput levels.
When the resources of our RCJAP represent processors, the resulting production environment is a special case of Rm/prec, [d.sub.j]/[C.sub.max] in the standard 3-field notation of Lawler et al. (1993) for scheduling problems, where [d.sub.j] denotes the due date of activity j, [C.sub.max] is the makespan, and Rm denotes m unrelated machines.
In the next section we show that our RCJAP subsumes a large number of complex and long-studied problems from the theory of scheduling. Also, we provide a mathematical formulation for RCJAP and discuss its complexity. The rest of the paper is organized as follows. In [section]3 we develop a lower-bounding scheme for RCJAP. In [section]4 we consider heuristic algorithms and provide an example. An extensive computational experiment on the performance of all the algorithms is performed in [section]5. In [section]5.1 we analyze the impact of operating flexibility and project complexity (measured by the complexity of the precedence network) on throughput performance. We conclude...
|
