Restricted assignment scheduling with resource constraints

DOI10.1016/j.tcs.2018.08.016zbMath1417.90076OpenAlexW2888472094WikidataQ129344524 ScholiaQ129344524MaRDI QIDQ1713408

Hans Kellerer, Zsolt Tuza, György Dósa

Publication date: 25 January 2019

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

Full work available at URL: http://real.mtak.hu/74272/6/19_D%C3%B3sa_ProceedingsMAPSP2017.pdf

zbMATH Keywords

schedulinggraph coloringresourcesrestricted assignmentAPX hardness

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35) Coloring of graphs and hypergraphs (05C15) Approximation algorithms (68W25)

Related Items (1)

An improved algorithm for parallel machine scheduling under additional resource constraints

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Approximation algorithms for the graph orientation minimizing the maximum weighted outdegree
• Approximation algorithms for scheduling unrelated parallel machines
• Scheduling with conflicts: Online and offline algorithms
• A simple algorithm for edge-coloring bipartite multigraphs
• Scheduling subject to resource constraints: Classification and complexity
• Scheduling tasks on two processors with deadlines and additional resources
• Minimizing mean flow time with parallel processors and resource constraints
• Optimization, approximation, and complexity classes
• Deadline scheduling of tasks with ready times and resource constraints
• Mutual exclusion scheduling
• Parallel machine scheduling with earliness--tardiness penalties and additional resource con\-straints.
• Scheduling problems for parallel dedicated machines under multiple resource constraints.
• Multiprofessor scheduling
• Packing triangles in bounded degree graphs.
• Scheduling parallel dedicated machines under a single non-shared resource
• Parallel machine scheduling with nested job assignment restrictions
• Parallel machine scheduling with additional resources: notation, classification, models and solution methods
• A quasi-polynomial approximation for the restricted assignment problem
• Graph balancing: a special case of scheduling unrelated parallel machines
• An optimal rounding gives a better approximation for scheduling unrelated machines
• Exact and Approximate Algorithms for Scheduling Nonidentical Processors
• Complexity Results for Multiprocessor Scheduling under Resource Constraints
• On Preemptive Scheduling of Unrelated Parallel Processors by Linear Programming
• Improved Algorithms for Bipartite Network Flow
• Santa Claus Schedules Jobs on Unrelated Machines
• Paths, Trees, and Flowers
• On (1,∊)-Restricted Assignment Makespan Minimization
• Scheduling parallel dedicated machines with the speeding‐up resource
• Scheduling

This page was built for publication: Restricted assignment scheduling with resource constraints