Elsevier

Automation in Construction

Volume 20, Issue 8, December 2011, Pages 1110-1119
Automation in Construction

Optimizing project selection and scheduling problems with time-dependent resource constraints

https://doi.org/10.1016/j.autcon.2011.04.012Get rights and content

Abstract

This study presents an optimization model using constraint programming (CP) for project selection and scheduling problems with time-dependent resource constraints. A generic model is proposed to maximize the total profit of selected projects for construction and R&D departments given scheduling problems with various resource constraints during specified time intervals, including consumed and renewable resource limitations. Due to different periodical procurement strategies and annual budget concerns, this research considers various practical limitations for scheduling and allocating resources, such as budget limitations and resource constraints. For additional practicality, the optimization model integrates a project selection mechanism, scheduling precedence, and relationships between projects. To illustrate the model capabilities for solving project selection and scheduling problems, the current study presents two scenarios for maximizing profit, including fifteen candidate projects with time-dependent resource constraints. Analysis results demonstrate that the proposed model allows planners to determine an optimal portfolio with specified resource constraints according to various time intervals, and benefits decision-making for project selection and scheduling.

Research highlights

► An optimization model is developed for project selection and scheduling problems with time-dependent resource constraints. ► The proposed model aims to maximize total profit of selected projects for construction or R&D departments. ► Both consumed and renewable resources are integrated into the optimization model, and relevant constraints are considered. ► Constraint programming (CP) is employed to search an optimal solution efficiently for the problem domain. ► Two scenarios with fifteen candidate projects are conducted and analyzed to demonstrate the model capability.

Introduction

Project selection and scheduling problems have recently received significant attention and played a vital role for organizations, including public sector construction projects and private sector R&D projects. The problem is a process of collecting and analyzing project information for project selection under a company's strategies and requirements, and thereby scheduling work within a specified time horizon. Project selection and scheduling is a complicated decision-making behavior and is affected by many factors [1], such as market conditions, availability of materials, government regulations, etc. In practice, construction projects in the public sector or R&D plans in private companies are always constrained by limited time and money. Hence, planners face difficult decisions in selecting and scheduling a set of projects, and simultaneously allocating various financial or material resources within a specified time horizon. For example, Chen and Askin [2] indicated that only 26% of IT projects are completed on time and within budget. However, most previous research only focused on the selection of available projects, or scheduling projects at hand to meet objectives given budget limitations. Numerous studies have addressed project selection problems in the engineering and IT industries [3], and the models have evolved from mathematical programming to flexible heuristic methods, such as the fuzzy-stochastic technique. Some studies have considered a project scheduling mechanism as part of the selection model criteria [2], [4], [5], [6], [7], [8], [9], [10], [11], yet none have considered time-dependent resource constraints nor fully explored resource allocation problems arising from procurement behaviors. Consequently, prior work has focused on the project selection problem rather than resulting scheduling issues, and has rarely considered the implications of various procurement strategies and annual budget concerns for resource assignment.

Resource constrained project scheduling problems (RCPSP) have been extensively studied for decades, and various solution approaches have been surveyed and classified by previous research [12], [13]. Since the same resources are usually required simultaneously, resource allocation plays a vital role in resolving the RCPSP. Resources are used in accordance with activity requirements and implementation times, and availability is normally restricted during the execution phase of projects. Hence, recent studies have addressed various RCPSP issues using different techniques to clarify the importance of resource allocation. For example, Trautmann and Baumann [14] examined the capabilities of various project management software packages for handling resource-allocation problems, and provide a table to assist managers in choosing appropriate software and priority rules. Kastor and Sirakoulis [15] analyzed the effectiveness of resource leveling tools in three software packages, including Primavera P6.0, Microsoft Project 2007, and Open Workbench 1.1.6., testing these products on real construction projects. Liu and Wang [16] focused on the financial elements and cash flow of the RCPSP, using constraint programming (CP) to maximize project profit. Liu and Shih [17] employed TOC (Theory of Constraints) to propose a framework of integrated resource constraints on a schedule, and introduced the concept of the critical resource chain in project scheduling. Chen and Shahandashti [18] proposed a hybrid of a genetic algorithm and simulated annealing (GA–SA Hybrid) for multi-project scheduling problems with multiple resource constraints, and compared the optimized result with the simulated annealing method (MSA), genetic algorithm (GA), and simulated annealing (SA). Lova et al. [19] developed a hybrid Genetic Algorithm (MM-HGA) to solve multi-mode resource-constrained project scheduling problems (MRCPSP), and Lo et al. [20] presented a modified ant colony optimization (ACO) approach for resource-constrained multiprocessor scheduling problems. Xu et al. [21] integrated justification and rollout into priority rule heuristics to solve the RCPSP, and Elloumi and Fortemps [22] applied a hybrid rank-based evolutionary algorithm to deal with the multi-mode RCPSP. Moreover, Chen and Weng [23] introduced a two-phase GA model for RCPSP, and presented a GA-based time-cost trade-off analysis. El-Rayes and Jun developed [24] two resource leveling metrics to minimize the negative impact of resource limitations for construction productivity and costs, and measured the total amount of desirable and undesirable resources. Christodoulou et al. [25] established an entropy-based scheduling method for resource-constrained construction projects, and forecasted a project's development by measuring the degree of disorder in the system. Later, Christodoulou et al. [26] proposed an entropy-maximization method to revisit the minimum moment method for resource leveling, using the general theory of entropy and its principal properties (subadditivity and maximality). Furthermore, Christodoulou [27] used ant colony optimization (ACO) to schedule resource-constrained construction projects, and employed the ACO artificial agent to examine the effects of resource availability for project critical paths and completion times. As a result of above research review various techniques have been developed to raise the efficiency of resource utilization. However, little research has closely considered periodical procurement strategies and outsourcing behaviors for resources, and time-dependent resource constraints are therefore not engaged.

This study thus integrates project selection and scheduling issues, and deliberates time-dependent resource constraints to formulate a profit-optimization model using constraint programming (CP). The proposed model maximizes total profit from selected projects as the objective function, and considers various resource constraints with time intervals, including consumed and renewable resource limitations. In this study, available budget is defined as consumed resource, and equipment/machine is regarded as renewable resource. The model integrates a project selection mechanism, scheduling precedence, and relationships between projects. Furthermore, due to the presence of different periodical procurement strategies and annual budget concerns, this study considers the various practical limitations for scheduling and resource allocation, such as budget limitations and resource constraints. Given high degree of complexity in the RCPSP, CP is employed for model building and solution seeking.

The following section describes the algorithm for CP techniques and CP optimization processes for the problem domain. Section 3 formulates the optimization model to guide resource allocation for project selection and scheduling. Section 4 briefly provides a hypothetical case and illustrates the results of scenario analysis. Finally, Section 5 finishes with conclusions and suggestions for future work.

Section snippets

Constraint programming

Constraint programming (CP) is a computer implementation designed for solving constraint satisfaction problems (CSPs) [28] which are generally regarded as combinatorial problems [29]. In CP, consistency techniques and systematic search strategies are critical for problem solving [30], [31]. Consistency techniques form an approach to solving CSPs, based on removing inconsistent values from variables' domains until the solution for improving search efficiency is obtained [31]. Moreover, CP

Objective

According to prior research [2], [19], [20], [21], [22], [23], [24], [25], [26], the objective always includes maximization of total profit or benefits from competing projects. The proposed model thus assumes that profits are calculated by individual candidate project, and sets the objective as maximizing the summarized profit of the selected projects. The objective function is illustrated as Eq. (1), designating profit (Bi) for each candidate project. A binary variable (xi) for project

Scenario analysis

This work employs a hypothetical example including fifteen candidate projects to demonstrate the application of the proposed optimization model. Table 1 lists the sample data, including project costs, duration, expected profit, and planned time horizon. A time horizon of two years (720 days) is planned for the completion of all selected projects, with 360 days in one year for work execution. Table 1 also presents the relationships between projects, such as interdependency, mutual exclusivity, and

Conclusion

This study considers various time-dependent resource constraints, and integrates selection and scheduling mechanisms to deal with complicated combinatorial problems in the field of project management. Using constraint programming (CP), a novel profit optimization model is established for solving project selection and scheduling problems. Consumed and renewable resources are also engaged in the model to assist planners in optimizing overall profit while satisfying various resource constraints.

References (48)

  • S. Elloumi et al.

    A hybrid rank-based evolutionary algorithm applied to multi-mode resource-constrained project scheduling problem

    European Journal of Operational Research

    (2010)
  • P.H. Chen et al.

    A two-phase GA model for resource-constrained project scheduling

    Automation in Construction

    (2009)
  • S. Christodoulou et al.

    Entropy-based scheduling of resource-constrained construction projects

    Automation in Construction

    (2009)
  • S.C. Brailsford et al.

    Constraint satisfaction problem: algorithms and applications

    European Journal of Operational Research

    (1999)
  • G.E. Khayat et al.

    Integrated production and material handling scheduling using mathematical programming and constraint programming

    European Journal of Operational Research

    (2006)
  • J. Rodriguez

    A constraint programming model for real-time train scheduling at junctions

    Transportation Research Part B: Methodological

    (2007)
  • S.M. Wang et al.

    Resource portfolio planning of make-to-stock products using a constraint programming-based genetic algorithm

    Omega

    (2007)
  • A. Garrido et al.

    Planning and scheduling in an e-learning environment. A constraint-programming-based approach

    Engineering Applications of Artificial Intelligence

    (2008)
  • P.E. Hladik et al.

    Solving a real-time allocation problem with constraint programming

    Journal of Systems and Software

    (2008)
  • Z.A. Banaszak et al.

    Constraint programming for project-driven manufacturing

    International Journal of Production Economics

    (2009)
  • L.J. Zeballos

    A constraint programming approach to tool allocation and production scheduling in flexible manufacturing systems

    Robotics and Computer-Integrated Manufacturing

    (2010)
  • L.J. Zeballos et al.

    A constraint programming model for the scheduling of flexible manufacturing systems with machine and tool limitations

    Engineering Applications of Artificial Intelligence

    (2010)
  • S.S. Liu et al.

    Optimization model for resource assignment problems of linear construction projects

    Automation in Construction

    (2007)
  • J.F. Bard et al.

    An interactive approach to R&D project selection and termination

    IEEE Transactions on Engineering Management

    (1988)
  • Cited by (71)

    • An updated survey of variants and extensions of the resource-constrained project scheduling problem

      2022, European Journal of Operational Research
      Citation Excerpt :

      Further constraints consider complementary projects (a set of related projects can only be selected as a whole) and mutually exclusive projects (at most one out of a set of projects can be selected). Liu and Wang (2011) tackle a similar model which also includes precedence relations between projects. The only resource is a budget for project costs.

    • A novel mathematical programming model for multi-mode project portfolio selection and scheduling with flexible resources and due dates under interval-valued fuzzy random uncertainty

      2021, Expert Systems with Applications
      Citation Excerpt :

      The validity of model is evaluated through different perspectives that are prevalent in the literature. For instance, Liu and Wang (2011) proved the validation of their proposed model through two scenarios. They considered the resource constraints as two budget and renewable resource constraints and evaluated them separately.

    • A comprehensive mathematical model for resource-constrained multi-objective project portfolio selection and scheduling considering sustainability and projects splitting

      2020, Journal of Cleaner Production
      Citation Excerpt :

      proposed a multi-objective algorithm to select and schedule projects. They presented two objective functions for total expected benefit maximization of selected projects and minimization of the allocated resource absolute variation between each consecutive period of time (Liu and Wang, 2011). presented an optimization model for project selection and scheduling problems with time-dependent resource constraints.

    View all citing articles on Scopus
    1

    Tel.: + 886 5 5342601x4724; fax: + 886 5 5312049.

    View full text