On linear lower bounds for the resource constrained project scheduling problem.
From MaRDI portal
In the paper lower bounds for the resource-constrained project scheduling problem minimizing the makespan are proposed. These bounds depend linearly on the processing times of the activities. After showing that several bounds from the literature belong to this class of bounds, two new approaches are presented. The first is based on a general linear programming scheme, the second uses the concept of redundant resources. Computational results are presented for the PSPLIB benchmark instances of \textit{R. Kolisch, A. Sprecher} and \textit{A. Drexl} [Manage. Sci. 41, 1693--1703 (1995; Zbl 0870.90070)] showing the effectiveness of the proposed procedures.
Recommendations
- Tight LP bounds for resource constrained project scheduling
- scientific article; zbMATH DE number 5132358
- A linear programming and constraint propagation-based lower bound for the RCPSP
- On some implementations of solving the resource constrained project scheduling problems
- Lower bounds for resource-constrained project scheduling problems.
Cites work
- A branch and bound algorithm for the resource-constrained project scheduling problem
- A linear programming and constraint propagation-based lower bound for the RCPSP
- A new LP-based lower bound for the cumulative scheduling problem
- An efficient optimal solution procedure for the preemptive resource-constrained project scheduling problem
- An exact algorithm for the resource-constrained project scheduling problem based on a new mathematical formulation
- Computing lower bounds by destructive improvement: An application to resource-constrained project scheduling
- Constraint propagation and decomposition techniques for highly disjunctive and highly cumulative project scheduling problems
- scientific article; zbMATH DE number 4095196 (Why is no real title available?)
- scientific article; zbMATH DE number 1187157 (Why is no real title available?)
- scientific article; zbMATH DE number 2080263 (Why is no real title available?)
- scientific article; zbMATH DE number 1405789 (Why is no real title available?)
- scientific article; zbMATH DE number 279273 (Why is no real title available?)
- Lower bounds and reduction procedures for the bin packing problem
- New Benchmark Results for the Resource-Constrained Project Scheduling Problem
- Optimal Solution of Scheduling Problems Using Lagrange Multipliers: Part I
- Ordonnancements. La notion de «parties obligatoires» et son application aux problèmes cumulatifs
- Project scheduling with resource constraints: A branch and bound approach. Note by Frederik Kaefer
- PSPLIB -- a project scheduling problem library
- Satisfiability tests and time-bound adjustments for cumulative scheduling problems
- Scheduling subject to resource constraints: Classification and complexity
- Une méthode arborescente pour résoudre les problèmes cumulatifs
- Worst-Case Performance Bounds for Simple One-Dimensional Packing Algorithms
Cited in
(36)- Lower bounds for resource-constrained project scheduling problems.
- A linear programming and constraint propagation-based lower bound for the RCPSP
- A new LP-based lower bound for the cumulative scheduling problem
- An exact composite lower bound strategy for the resource-constrained project scheduling problem
- Redundant cumulative constraints to compute preemptive bounds
- Lower bounds for the event scheduling problem with consumption and production of resources
- An efficient pseudo-polynomial algorithm for finding a lower bound on the makespan for the resource constrained project scheduling problem
- Enhanced energetic reasoning-based lower bounds for the resource constrained project scheduling problem
- Tight LP bounds for resource constrained project scheduling
- A polyhedral study of event-based models for the resource-constrained project scheduling problem
- A project scheduling problem with periodically aggregated resource-constraints
- Horizontally elastic edge-finder algorithm for cumulative resource constraint revisited
- An effective branch-and-price algorithm for the preemptive resource constrained project scheduling problem based on minimal interval order enumeration
- THE LEXICO-BOUNDED FLOW ALGORITHM FOR SOLVING THE MINIMUM COST PROJECT SCHEDULING PROBLEM WITH AN ADDITIONAL LINEAR CONSTRAINT
- scientific article; zbMATH DE number 5132358 (Why is no real title available?)
- A Column Generation Based Destructive Lower Bound for Resource Constrained Project Scheduling Problems
- A preemptive bound for the resource constrained project scheduling problem
- Project scheduling with flexible resources: formulation and inequalities
- Providing lower bounds for the multi-mode resource-constrained project scheduling problem
- scientific article; zbMATH DE number 1405789 (Why is no real title available?)
- Lower bounds for a multi-skill project scheduling problem
- Approaches to solving RCPSP using relaxed problem with consumable resources
- Principles and Practice of Constraint Programming – CP 2004
- A binary search algorithm for the general coupled task scheduling problem
- Constraint propagation on GPU: a case study for the cumulative constraint
- A survey of dual-feasible and superadditive functions
- New concepts for activity float in resource-constrained project management
- Fifty years of research on resource-constrained project scheduling explored from different perspectives
- Quadratic horizontally elastic not-first/not-last filtering algorithm for cumulative constraint
- Constraint propagation on GPU: a case study for the cumulative constraint
- Event-based MILP models for resource-constrained project scheduling problems
- A new lower bound for the resource-constrained project scheduling problem with generalized precedence relations
- Improved energetic reasoning checker for cumulative constraint with profile
- Approximability results for the resource-constrained project scheduling problem with a single type of resources
- Minimizing the completion time of a project under resource constraints and feeding precedence relations: a Lagrangian relaxation based lower bound
- Computing redundant resources for the resource constrained project scheduling problem
This page was built for publication: On linear lower bounds for the resource constrained project scheduling problem.
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1399576)
