Multiprocessor scheduling under precedence constraints: polyhedral results

DOI10.1016/J.DAM.2004.07.009MaRDI QIDQ2489902zbMATH OpenOpenAlexFDO

Authors Pablo Coll, Celso C. Ribeiro, Cid Carvalho de Souza

Publication date 28 April 2006

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.dam.2004.07.009

zbMATH Keywords

SchedulingValid inequalitiesMultiprocessorsPrecedence constraintsPolyhedral combinatoricsOrder polytopes

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57)

Recommendations

• scientific article; zbMATH DE number 962288
• Single-Machine Scheduling Polyhedra with Precedence Constraints
• ILP formulations for scheduling ordered tasks on a bounded number of processors
• A new formulation for scheduling unrelated processor under precedence constraints
• A relation between multiprocessor scheduling and linear programming

Cites work

• scientific article; zbMATH DE number 4095196 (Why is no real title available?)
• scientific article; zbMATH DE number 51132 (Why is no real title available?)
• scientific article; zbMATH DE number 3483531 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1102774 (Why is no real title available?)
• scientific article; zbMATH DE number 876684 (Why is no real title available?)
• A Cutting Plane Algorithm for the Linear Ordering Problem
• A cutting plane algorithm for a clustering problem
• A new formulation for scheduling unrelated processor under precedence constraints
• Adjacency of vertices of the complete pre-order polytope
• Facets of the clique partitioning polytope
• Facets of the linear ordering polytope
• Facets of the weak order polytope derived from the induced partition projection
• On the acyclic subgraph polytope
• On the partial order polytope of a digraph
• Parallel tabu search message-passing synchronous strategies for task scheduling under precendence constraints
• Performance evaluation of a parallel tabu search task scheduling algorithm
• `` Strong NP-Completeness Results

Cited in

(29)

• scientific article; zbMATH DE number 2080870 (Why is no real title available?)
• A mixed-integer linear programming approach for the t-row and the multi-bay facility layout problem
• Sub-polyhedral scheduling using (unit-)two-variable-per-inequality polyhedra
• Quasi-PTAS for scheduling with precedences using LP hierarchies
• A pre-order relation for exact schedulability test of sporadic tasks on multiprocessor global fixed-priority scheduling
• Preemptive scheduling with dedicated processors: applications of fractional graph coloring
• Mathematical optimization approaches for facility layout problems: the state-of-the-art and future research directions
• Preemptive scheduling of interval orders is polynomial
• A polynomial feasibility test for preemptive periodic scheduling of unrelated processors
• A new formulation for scheduling unrelated processor under precedence constraints
• The feasibility of general task systems with precedence constraints on multiprocessor platforms
• Satisfiability modulo theory (SMT) formulation for optimal scheduling of task graphs with communication delay
• Polyhedral Reformulation of a Scheduling Problem And Related Theoretical Results
• Ten notes on equal-processing-time scheduling: at the frontiers of solvability in polynomial time
• Optimal solutions for the double row layout problem
• Explicit Modelling of Multiple Intervals in a Constraint Generation Procedure for Multiprocessor Scheduling
• Exact quantification of the sub-optimality of uniprocessor fixed priority pre-emptive scheduling
• Linear algorithms for preemptive scheduling of multiprocessor tasks subject to minimal lateness
• Preemptive open shop scheduling with multiprocessors: Polynomial cases and applications
• The maximum common edge subgraph problem: A polyhedral investigation
• The maximum gain of increasing the number of preemptions in multiprocessor scheduling
• scientific article; zbMATH DE number 6263704 (Why is no real title available?)
• scientific article; zbMATH DE number 1759431 (Why is no real title available?)
• A study of scheduling problems with preemptions on multi-core computers with GPU accelerators
• Logic versus Approximation
• The corridor allocation problem
• Probabilistic analysis of scheduling precedence constrained parallel tasks on multicomputers with contiguous processor allocation
• Preemptive scheduling and antichain polyhedra
• Unrelated parallel machine scheduling problem with precedence constraints: polyhedral analysis and branch-and-cut

Describes a project that uses

Uses Software

• ABACUS
• CPLEX

This page was built for publication: Multiprocessor scheduling under precedence constraints: polyhedral results

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2489902)