scientific article; zbMATH DE number 512917

MaRDI QIDQ4281629zbMATH OpenFDO

Authors Gerhard J. Woeginger, Hans L. Bodlaender, Klaus Jansen

Publication date 7 April 1994

zbMATH Keywords

\(NP\)-completecoloring of precolored bipartite graphsjob incompatibilitiesmultiprocessor systempolynomial time approximation algorithmsscheduling

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Scheduling with incompatible jobs
• Scheduling of incompatible jobs on unrelated machines
• Scheduling with complete multipartite incompatibility graph on parallel machines: complexity and algorithms

Cited in

(15)

• Scheduling incompatible tasks on two machines
• Scheduling two jobs with fixed and nonfixed routes
• Scheduling with incompatible jobs
• Scheduling of unit-length jobs with cubic incompatibility graphs on three uniform machines
• Scheduling with complete multipartite incompatibility graph on parallel machines: complexity and algorithms
• Multi-coloring and job-scheduling with assignment and incompatibility costs
• Two job cyclic scheduling with incompatibility constraints
• Solution methods for a scheduling problem with incompatibility and precedence constraints
• Scheduling of incompatible jobs on unrelated machines
• Approximation results for the optimum cost chromatic partition problem
• Scheduling of identical jobs with bipartite incompatibility graphs on uniform machines. Computational experiments
• Approximation algorithms for time constrained scheduling
• On min-max graph balancing with strict negative correlation constraints
• Chromatic cost coloring of weighted bipartite graphs
• Time slot scheduling of compatible jobs

This page was built for publication:

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