An Exact Algorithm for the Resource-Constrained Project Scheduling Problem Based on a New Mathematical Formulation

DOI10.1287/MNSC.44.5.714zbMath1004.90036OpenAlexW2106622621WikidataQ56874235 ScholiaQ56874235MaRDI QIDQ2783969

Aristide Mingozzi, Salvatore Ricciardelli, Vittorio Maniezzo, Lucio Bianco

Publication date: 16 October 2002

Published in: Management Science (Search for Journal in Brave)

Full work available at URL: https://semanticscholar.org/paper/fc772d8db813eaedcbce07f61b20b6e3138b9d54

zbMATH Keywords

lower boundsresource constraintstree search algorithmbranch-and-bound methodsproject scheduling problem\(0-1\) linear programming

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Deterministic scheduling theory in operations research (90B35) Boolean programming (90C09)

Related Items (86)

Multi-mode resource constrained project scheduling problem along with contractor selection ⋮ Scheduling under a non-reversible energy source: an application of piecewise linear bounding of non-linear demand/cost functions ⋮ A polarized adaptive schedule generation scheme for the resource-constrained project scheduling problem ⋮ A heuristic for optimizing stochastic activity networks with applications to statistical digital circuit sizing ⋮ A purely proactive scheduling procedure for the resource-constrained project scheduling problem with stochastic activity durations ⋮ An effective branch-and-price algorithm for the preemptive resource constrained project scheduling problem based on minimal interval order enumeration ⋮ Models and solution procedures for the resource-constrained project scheduling problem with general temporal constraints and calendars ⋮ Heuristic algorithms for visiting the customers in a rolling schedule environment ⋮ Computing redundant resources for the resource constrained project scheduling problem ⋮ Branch-and-Cut-and-Price algorithms for the preemptive RCPSP ⋮ Solving resource-constrained project scheduling problems: conceptual validation of FLP formulation and efficient permutation-based ABC computation ⋮ An exact composite lower bound strategy for the resource-constrained project scheduling problem ⋮ A filter-and-fan approach with adaptive neighborhood switching for resource-constrained project scheduling ⋮ An evolutionary algorithm based hyper-heuristic framework for the set packing problem ⋮ An exact algorithm for project scheduling with multiple modes ⋮ Genetic algorithm for the resource-constrained project scheduling problem ⋮ Formulating and solving a multi-mode resource-collaboration and constrained scheduling problem (MRCCSP) ⋮ A biased random-key genetic algorithm for the project scheduling problem with flexible resources ⋮ A polyhedral study of event-based models for the resource-constrained project scheduling problem ⋮ A project scheduling problem with periodically aggregated resource-constraints ⋮ Linear programming based algorithms for preemptive and non-preemptive RCPSP ⋮ A preemptive bound for the resource constrained project scheduling problem ⋮ Matheuristics: survey and synthesis ⋮ Integrated time–cost tradeoff and resources leveling problems with allowed activity splitting ⋮ Linear integer programming model as mathematical ware for an optimal flow production planning system at operational scheduling stage ⋮ Project scheduling with finite or infinite number of activity processing modes -- a survey ⋮ Modeling frameworks for the multi‐skill resource‐constrained project scheduling problem: a theoretical and empirical comparison ⋮ New concepts for activity float in resource-constrained project management ⋮ A prediction model for ranking branch-and-bound procedures for the resource-constrained project scheduling problem ⋮ A new efficient simulated annealing algorithm for the resource-constrained project scheduling problem and its multiple mode version. ⋮ Resource-constrained project scheduling: A critical activity reordering heuristic ⋮ Lower bounds for resource-constrained project scheduling problems. ⋮ On linear lower bounds for the resource constrained project scheduling problem. ⋮ A branch-and-bound algorithm for the unit-capacity resource constrained project scheduling problem with transfer times ⋮ Resource-constrained project scheduling: A survey of recent developments. ⋮ A Boolean satisfiability approach to the resource-constrained project scheduling problem ⋮ Robust energy planning in buildings with energy and comfort costs ⋮ The Resource Constrained Project Scheduling Problem: A theoretical comparison between a recent formulation and the main time indexed linear programming based approaches ⋮ Tight complexity analysis of the relocation problem with arbitrary release dates ⋮ Project scheduling with flexible resources: formulation and inequalities ⋮ An efficient pseudo-polynomial algorithm for finding a lower bound on the makespan for the resource constrained project scheduling problem ⋮ GRASP for set packing problems. ⋮ Strong valid inequalities for the resource-constrained scheduling problem with uniform resource requirements ⋮ Methods to solve multi-skill project scheduling problem ⋮ New representation to reduce the search space for the resource-constrained project scheduling problem ⋮ An iterated local search algorithm for a place scheduling problem ⋮ On the strength of time-indexed formulations for the resource-constrained project scheduling problem ⋮ Branch-and-price approach for the multi-skill project scheduling problem ⋮ A constraint programming approach for the resource-constrained project scheduling problem ⋮ Solving the resource-constrained project scheduling problem using filter-and-fan approach ⋮ A random key based genetic algorithm for the resource constrained project scheduling problem ⋮ Revenue sharing for resource reallocation among project activity contractors ⋮ Towards merging binary integer programming techniques with genetic algorithms ⋮ Scheduling and constraint propagation ⋮ A dual ascent heuristic for obtaining a lower bound of the generalized set partitioning problem with convexity constraints ⋮ Finding the shortest path with honey-bee mating optimization algorithm in project management problems with constrained/unconstrained resources ⋮ Event-based MILP models for resource-constrained project scheduling problems ⋮ A neurogenetic approach for the resource-constrained project scheduling problem ⋮ Justification and RCPSP: a technique that pays ⋮ Benders decomposition, Lagrangean relaxation and metaheuristic design ⋮ Polyhedral Reformulation of a Scheduling Problem And Related Theoretical Results ⋮ A Branch-and-Bound method for solving Multi-Skill Project Scheduling Problem ⋮ Revenue sharing for resource transfer among projects ⋮ Hybridization of GRASP metaheuristic with data mining techniques ⋮ A satisfiability and workload-based exact method for the resource constrained project scheduling problem with generalized precedence constraints ⋮ On project scheduling problem ⋮ Preemptive scheduling and antichain polyhedra ⋮ Project selection, scheduling and resource allocation with time dependent returns ⋮ Probability mechanism based particle swarm optimization algorithm and its application in resource-constrained project scheduling problems ⋮ Resource-constrained project scheduling: Notation, classification, models, and methods ⋮ Approximability results for the resource-constrained project scheduling problem with a single type of resources ⋮ Computing lower bounds by destructive improvement: An application to resource-constrained project scheduling ⋮ On some implementations of solving the resource constrained project scheduling problems ⋮ PSPLIB -- a project scheduling problem library ⋮ Polyhedral Results and Branch-and-Cut for the Resource Loading Problem ⋮ A tree search heuristic for the resource constrained project scheduling problem with transfer times ⋮ Activity list representation for a generalization of the resource-constrained project scheduling problem ⋮ A branch and bound algorithm for the resource-constrained project scheduling problem ⋮ Bidirectional planning: Improving priority rule-based heuristics for scheduling resource-constrained projects ⋮ A hybrid scatter search/electromagnetism meta-heuristic for project scheduling ⋮ Strong bounds for resource constrained project scheduling: preprocessing and cutting planes ⋮ A linear programming and constraint propagation-based lower bound for the RCPSP ⋮ A new LP-based lower bound for the cumulative scheduling problem ⋮ Dynamic node packing ⋮ Complexity of the scheduling language RSV ⋮ A hybrid evolutionary approach for set packing problem

This page was built for publication: An Exact Algorithm for the Resource-Constrained Project Scheduling Problem Based on a New Mathematical Formulation