An efficient pseudo-polynomial algorithm for finding a lower bound on the makespan for the resource constrained project scheduling problem

DOI10.1016/j.ejor.2018.11.005zbMath1430.90243OpenAlexW2900168008WikidataQ128909106 ScholiaQ128909106MaRDI QIDQ1711441

Olga Battaïa, Dmitry I. Arkhipov, Alexander A. Lazarev

Publication date: 18 January 2019

Published in: European Journal of Operational Research (Search for Journal in Brave)

Full work available at URL: http://oatao.univ-toulouse.fr/21875/1/Arkhipov_21875..pdf

zbMATH Keywords

project schedulingschedulinglower boundsRCPSPpseudo-polynomial algorithms

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35)

Related Items (1)

An evolutionary approach for resource constrained project scheduling with uncertain changes

Uses Software

• PSPLIB
• BL data set

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A note on two problems in connexion with graphs
• Explaining the \texttt{cumulative} propagator
• Mixed satisfiability tests for multiprocessor scheduling with release dates and deadlines.
• Jackson's pseudo-preemptive schedule and cumulative scheduling problems
• Algorithms for propagating resource constraints in AI planning and scheduling: Existing approaches and new results
• A practical use of Jackson's preemptive schedule for solving the job shop problem
• Jackson's pseudo preemptive schedule for the \(Pm/r_i, q_i/C_{\text{max}}\) scheduling problem
• PSPLIB -- a project scheduling problem library
• Adjustment of heads and tails for the job-shop problem
• On linear lower bounds 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
• Project scheduling with resource constraints: A branch and bound approach. Note by Frederik Kaefer
• An improved max-flow-based lower bound for minimizing maximum lateness on identical parallel machines
• Tight LP bounds for resource constrained project scheduling
• Satisfiability tests and time-bound adjustments for cumulative scheduling problems
• Constraint propagation and decomposition techniques for highly disjunctive and highly cumulative project scheduling problems
• An Exact Algorithm for the Resource-Constrained Project Scheduling Problem Based on a New Mathematical Formulation
• Une méthode arborescente pour résoudre les problèmes cumulatifs
• An Algorithm for Solving the Job-Shop Problem
• Ordonnancements. La notion de «parties obligatoires» et son application aux problèmes cumulatifs
• A Computational Study of the Job-Shop Scheduling Problem
• Complexity Results for Multiprocessor Scheduling under Resource Constraints

This page was built for publication: An efficient pseudo-polynomial algorithm for finding a lower bound on the makespan for the resource constrained project scheduling problem