Approximation algorithms for the workload partition problem and applications to scheduling with variable processing times

DOI10.1016/j.ejor.2016.06.062zbMath1394.90297MaRDI QIDQ1752203

George Steiner, Dvir Shabtay, Daniel Oron

Publication date: 24 May 2018

Published in: European Journal of Operational Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ejor.2016.06.062

zbMATH Keywords

scheduling; approximation algorithms; identical parallel machines; controllable processing times; workload partition problem

Mathematics Subject Classification ID

90C60: Abstract computational complexity for mathematical programming problems

90B35: Deterministic scheduling theory in operations research

68M20: Performance evaluation, queueing, and scheduling in the context of computer systems

Cites Work

• Unnamed Item
• Single machine batch scheduling to minimize total completion time and resource consumption costs
• Approximation schemes for parallel machine scheduling problems with controllable processing times
• Single and two-resource allocation algorithms for minimizing the maximal lateness in a single machine
• Minimizing the total weighted flow time in a single machine with controllable processing times
• A survey of scheduling with controllable processing times
• Parallel machine scheduling with a convex resource consumption function
• Resource Management in Machine Scheduling Problems: A Survey
• Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems
• Solving a class of two-resource allocation problem by equivalent load method
• Allocation of resources in project management
• Cost-effectiveness of a preventive counseling and support package for postnatal depression
• Bounds for Certain Multiprocessing Anomalies
• Convex Resource Allocation Problems on Directed Acyclic Graphs: Duality, Complexity, Special Cases, and Extensions