A note on graph balancing problems with restrictions

DOI10.1016/j.ipl.2009.09.015zbMath1197.05147OpenAlexW2066813640MaRDI QIDQ990093

Kangbok Lee, Joseph Y.-T. Leung, Michael L. Pinedo

Publication date: 2 September 2010

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2009.09.015

zbMATH Keywords

computational complexityapproximation algorithmcombinatorial problemsFPTASparallel machines schedulingeligibility constraintsfully polynomial time approximation schemegraph balancing

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (7)

On some special cases of the restricted assignment problem ⋮ Structural parameters for scheduling with assignment restrictions ⋮ On the configuration-LP for scheduling on unrelated machines ⋮ A 3/2-approximation algorithm for the graph balancing problem with two weights ⋮ Scheduling reclaimer operations in the stockyard to minimize makespan ⋮ Greedy is optimal for online restricted assignment and smart grid scheduling for unit size jobs ⋮ Makespan minimization on unrelated parallel machines with simple job-intersection structure and bounded job assignments

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Graph classes and the complexity of the graph orientation minimizing the maximum weighted outdegree
• Approximation algorithms for scheduling unrelated parallel machines
• Parallel machine scheduling of machine-dependent jobs with unit-length.
• Polynomial time approximation algorithms for machine scheduling: Ten open problems
• Parallel machine scheduling under a grade of service provision
• An optimal rounding gives a better approximation for scheduling unrelated machines
• GRAPH ORIENTATION ALGORITHMS TO MINIMIZE THE MAXIMUM OUTDEGREE
• Scheduling parallel machines with inclusive processing set restrictions
• Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems
• Parallel machine scheduling with job assignment restrictions
• Approximation Algorithms for the Graph Orientation Minimizing the Maximum Weighted Outdegree
• Algorithms and Data Structures

This page was built for publication: A note on graph balancing problems with restrictions