Multiprocessor scheduling under precedence constraints: polyhedral results

DOI10.1016/J.DAM.2004.07.009zbMATH Open1120.90070OpenAlexW1999728843MaRDI QIDQ2489902FDOQ2489902

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

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

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

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)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• `` Strong NP-Completeness Results
• Title not available (Why is that?)
• A cutting plane algorithm for a clustering problem
• Facets of the clique partitioning polytope
• On the partial order polytope of a digraph
• Facets of the linear ordering polytope
• A Cutting Plane Algorithm for the Linear Ordering Problem
• On the acyclic subgraph polytope
• Title not available (Why is that?)
• Title not available (Why is that?)
• Facets of the weak order polytope derived from the induced partition projection
• Performance evaluation of a parallel tabu search task scheduling algorithm
• A new formulation for scheduling unrelated processor under precedence constraints
• Adjacency of vertices of the complete pre-order polytope
• Parallel tabu search message-passing synchronous strategies for task scheduling under precendence constraints

Cited In (28)

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

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)