Approximation schemes for scheduling on parallel machines

DOI<55::AID-JOS2>3.0.CO;2-J 10.1002/(SICI)1099-1425(199806)1:1<55::AID-JOS2>3.0.CO;2-JzbMath0909.90168OpenAlexW1977276352MaRDI QIDQ1268852

Tal Yadid, Yossi Azar, Gerhard J. Woeginger, Noga Alon

Publication date: 1 November 1998

Published in: Journal of Scheduling (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/(sici)1099-1425(199806)1:1<55::aid-jos2>3.0.co;2-j

zbMATH Keywords

combinatorial optimization approximation algorithm scheduling theory worst-case ratio polynomial-time approximation scheme machine completion times

Mathematics Subject Classification ID

Abstract computational complexity for mathematical programming problems (90C60) Deterministic scheduling theory in operations research (90B35)

Related Items (77)

Approximation algorithms for simple assembly line balancing problems ⋮ New Algorithmic Results for Bin Packing and Scheduling ⋮ Tightness of sensitivity and proximity bounds for integer linear programs ⋮ Approximation schemes for the generalized extensible bin packing problem ⋮ An APTAS for bin packing with clique-graph conflicts ⋮ Non-preemptive Scheduling on Machines with Setup Times ⋮ On the optimality of exact and approximation algorithms for scheduling problems ⋮ Robust Polynomial-Time Approximation Schemes for Parallel Machine Scheduling with Job Arrivals and Departures ⋮ A fast and effective subset sum based improvement procedure for workload balancing on identical parallel machines ⋮ Exact and meta-heuristic approaches for the production leveling problem ⋮ Parallel machine scheduling with restricted job rejection ⋮ Approximation and online algorithms for multidimensional bin packing: a survey ⋮ An additive approximation scheme for the Nash social welfare maximization with identical additive valuations ⋮ The longest processing time rule for identical parallel machines revisited ⋮ Polynomial time approximation scheme for two parallel machines scheduling with a common due date to maximize early work ⋮ Approximation algorithms for extensible bin packing ⋮ Parameterized complexity of configuration integer programs ⋮ A unified framework for designing EPTAS for load balancing on parallel machines ⋮ The benefit of preemption with respect to the \(\ell_p\) norm ⋮ On multiprocessor temperature-aware scheduling problems ⋮ High-multiplicity \(N\)-fold IP via configuration LP ⋮ EPTAS for the dual of splittable bin packing with cardinality constraint ⋮ Fair and efficient allocation with few agent types, few item types, or small value levels ⋮ Scheduling and fixed-parameter tractability ⋮ Improved bounds for stochastic extensible bin packing under distributional assumptions ⋮ A state-of-the-art survey on multi-scenario scheduling ⋮ An Efficient PTAS for Parallel Machine Scheduling with Capacity Constraints ⋮ EPTAS for parallel identical machine scheduling with time restrictions ⋮ Penalty cost constrained identical parallel machine scheduling problem ⋮ A tight linear time \(\frac{13}{12}\)-approximation algorithm for the \(P2 || C_{\max}\) problem ⋮ Randomized approximation schemes for minimizing the weighted makespan on identical parallel machines ⋮ Breaking symmetries to rescue sum of squares in the case of makespan scheduling ⋮ Approximation scheme for single-machine rescheduling with job delay and rejection ⋮ Scheduling with machine conflicts ⋮ Speed-robust scheduling: sand, bricks, and rocks ⋮ Scheduling of pipelined operator graphs ⋮ Tight bounds for selfish and greedy load balancing ⋮ Unnamed Item ⋮ An efficient polynomial time approximation scheme for load balancing on uniformly related machines ⋮ Speed scaling of tasks with precedence constraints ⋮ Improved bi-criteria approximation schemes for load balancing on unrelated machines with cost constraints ⋮ Metaheuristics for order scheduling problem with unequal ready times ⋮ Minimizing envy and maximizing average Nash social welfare in the allocation of indivisible goods ⋮ Online scheduling with rejection and reordering: exact algorithms for unit size jobs ⋮ Approximation Algorithms for Unrelated Machine Scheduling with an Energy Budget ⋮ Vector scheduling with rejection on a single machine ⋮ Bi-Criteria Approximation Algorithms for Load Balancing on Unrelated Machines with Costs ⋮ TWO APPROXIMATION SCHEMES FOR SCHEDULING ON PARALLEL MACHINES UNDER A GRADE OF SERVICE PROVISION ⋮ Parameterizing by the number of numbers ⋮ Vector assignment schemes for asymmetric settings ⋮ EPTAS for load balancing problem on parallel machines with a non-renewable resource ⋮ Parallel machine scheduling with nested job assignment restrictions ⋮ Scheduling reclaimer operations in the stockyard to minimize makespan ⋮ Parameterized complexity of machine scheduling: 15 open problems ⋮ Unnamed Item ⋮ Load balancing of temporary tasks in the \(\ell _{p}\) norm ⋮ Approximating vector scheduling: almost matching upper and lower bounds ⋮ A unified view of parallel machine scheduling with interdependent processing rates ⋮ A Unified Approach to Truthful Scheduling on Related Machines ⋮ On-line scheduling with extendable working time on a small number of machines ⋮ Simpler and Better Algorithms for Minimum-Norm Load Balancing ⋮ Approximation algorithms for the multiprocessor scheduling with submodular penalties ⋮ Complexity of min-max subsequence problems ⋮ An EPTAS for scheduling on unrelated machines of few different types ⋮ Fully polynomial time approximation scheme to maximize early work on parallel machines with common due date ⋮ Closing the Gap for Makespan Scheduling via Sparsification Techniques ⋮ Speed-robust scheduling. Sand, bricks, and rocks ⋮ POLYNOMIAL APPROXIMATION SCHEMES FOR THE MAX-MIN ALLOCATION PROBLEM UNDER A GRADE OF SERVICE PROVISION ⋮ Power-aware scheduling for makespan and flow ⋮ EPTAS for load balancing problem on parallel machines with a non-renewable resource ⋮ Improved approximation algorithms for the combination problem of parallel machine scheduling and path ⋮ Empowering the configuration-IP: new PTAS results for scheduling with setup times ⋮ In memoriam: Gerhard Woeginger (1964--2022) ⋮ Tight approximation bounds for the LPT rule applied to identical parallel machines with small jobs ⋮ Optimal preemptive scheduling for general target functions ⋮ Approximation algorithms for shop scheduling problems with minsum objective ⋮ A new approach for bicriteria partitioning problem

This page was built for publication: Approximation schemes for scheduling on parallel machines