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

DOI10.1016/j.ejor.2016.06.062zbMath1394.90297OpenAlexW2461363908MaRDI 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

schedulingapproximation algorithmsidentical parallel machinescontrollable processing timesworkload partition problem

Mathematics Subject Classification ID

Abstract computational complexity for mathematical programming problems (90C60) Deterministic scheduling theory in operations research (90B35) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20)

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