Scheduling jobs on identical machines with agreement graph

DOI10.1016/j.cor.2011.04.014zbMath1251.90115OpenAlexW2088522084MaRDI QIDQ1761988

Mourad Boudhar, Mohamed Bendraouche

Publication date: 15 November 2012

Published in: Computers \& Operations Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.cor.2011.04.014

zbMATH Keywords

complexityschedulingidentical machinesagreement graphlist algorithm

Mathematics Subject Classification ID

Applications of graph theory (05C90) Deterministic scheduling theory in operations research (90B35) Marketing, advertising (90B60)

Related Items (13)

Path cover with minimum nontrivial paths and its application in two-machine flow-shop scheduling with a conflict graph ⋮ Scheduling: agreement graph vs resource constraints ⋮ Approximation of the parallel machine scheduling problem with additional unit resources ⋮ Approximation algorithms for two parallel dedicated machine scheduling with conflict constraints ⋮ New results in two identical machines scheduling with agreement graphs ⋮ Complexity and approximation algorithms for two parallel dedicated machine scheduling with conflict constraints ⋮ Storage Yard Management: Modelling and Solving ⋮ Scheduling on uniform machines with a conflict graph: complexity and resolution ⋮ An improved algorithm for parallel machine scheduling under additional resource constraints ⋮ Flow shop scheduling problem with conflict graphs ⋮ Scheduling identical jobs on uniform machines with a conflict graph ⋮ Two-machine open shop problem with agreement graph ⋮ Open shop scheduling problems with conflict graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Restrictions of graph partition problems. I
• Bounded vertex colorings of graphs
• A note on the decomposition of graphs into isomorphic matchings
• Scheduling with conflicts: Online and offline algorithms
• Mutual exclusion scheduling with interval graphs or related classes. I
• The complexity of generalized clique packing
• NP-completeness of graph decomposition problems
• Stable sets and polynomials
• Restricted coloring models for timetabling
• Mutual exclusion scheduling
• Matching and multidimensional matching in chordal and strongly chordal graphs
• The mutual exclusion scheduling problem for permutation and comparability graphs.
• Multicoloring trees.
• A note on greedy algorithms for the maximum weighted independent set problem
• Analysis of Preflow Push Algorithms for Maximum Network Flow
• Mathematical Foundations of Computer Science 2004
• Bounds for Certain Multiprocessing Anomalies
• Bounded vertex coloring of trees

This page was built for publication: Scheduling jobs on identical machines with agreement graph