New results in two identical machines scheduling with agreement graphs

DOI10.1016/J.TCS.2019.01.038MaRDI QIDQ2420580zbMATH OpenOpenAlexWikidataFDO

Authors Amine Mohabeddine, Mourad Boudhar

Publication date 6 June 2019

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2019.01.038

zbMATH Keywords

agreement graphcomplexityconflict graphidentical machinesmakespanscheduling

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Deterministic scheduling theory in operations research (90B35)

Recommendations

• Scheduling jobs on identical machines with agreement graph
• Two-machine open shop problem with agreement graph
• New complexity results for shop scheduling problems with agreement graphs
• Scheduling: agreement graph vs resource constraints
• Scheduling of identical jobs with bipartite incompatibility graphs on uniform machines. Computational experiments

Cites work

• An optimal time algorithm for finding a maximum weight independent set in a tree
• Bounds for Multiprocessor Scheduling with Resource Constraints
• Complexity Results for Multiprocessor Scheduling under Resource Constraints
• Flow shop scheduling problem with conflict graphs
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• Mutual exclusion scheduling
• Mutual exclusion scheduling with interval graphs or related classes. I
• Open shop scheduling problems with conflict graphs
• Restricted coloring models for timetabling
• Restrictions of graph partition problems. I
• Scheduling jobs on identical machines with agreement graph
• Scheduling subject to resource constraints: Classification and complexity
• Scheduling with conflicts: Online and offline algorithms
• Scheduling: agreement graph vs resource constraints
• The mutual exclusion scheduling problem for permutation and comparability graphs.

Cited in

(7)

• Scheduling jobs on identical machines with agreement graph
• Approximation algorithms for two parallel dedicated machine scheduling with conflict constraints
• New complexity results for shop scheduling problems with agreement graphs
• A metric approach for scheduling problems with minimizing the maximum penalty
• Two-machine open shop problem with agreement graph
• Scheduling: agreement graph vs resource constraints
• Complexity and approximation algorithms for two parallel dedicated machine scheduling with conflict constraints

Describes a project that uses

Uses Software

• Algorithm 447

This page was built for publication: New results in two identical machines scheduling with agreement graphs

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