Randomized approximation schemes for minimizing the weighted makespan on identical parallel machines

DOI10.1007/s10878-024-01118-wOpenAlexW4393356394MaRDI QIDQ6126818

Ruiqing Sun

Publication date: 10 April 2024

Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10878-024-01118-w

zbMATH Keywords

schedulingapproximation algorithmfully polynomial time approximation schemeefficient polynomial time approximation schemeweighted makespan

Mathematics Subject Classification ID

Mathematical programming (90Cxx)

Cites Work

• Unnamed Item
• Approximation schemes for scheduling on parallel machines
• Minimizing average completion time in the presence of release dates
• Scheduling problems on two sets of identical machines
• Single machine scheduling with rejection to minimize the weighted makespan
• A unified framework for designing EPTAS for load balancing on parallel machines
• A PTAS for Minimizing the Total Weighted Completion Time on Identical Parallel Machines
• Integer Programming with a Fixed Number of Variables
• Convex quadratic and semidefinite programming relaxations in scheduling
• Closing the Gap for Makespan Scheduling via Sparsification Techniques
• Worst Case Bound of an LRF Schedule for the Mean Weighted Flow-Time Problem
• Algorithms for Scheduling Independent Tasks
• Best-Possible Online Algorithms for Single Machine Scheduling to Minimize the Maximum Weighted Completion Time
• Lift-and-Round to Improve Weighted Completion Time on Unrelated Machines
• Scheduling to Minimize Total Weighted Completion Time via Time-Indexed Linear Programming Relaxations
• Weighted Completion Time Minimization for Unrelated Machines via Iterative Fair Contention Resolution
• Bounds for Certain Multiprocessing Anomalies
• Bounds on Multiprocessing Timing Anomalies
• A PTAS for Scheduling Unrelated Machines of Few Different Types
• An EPTAS for scheduling on unrelated machines of few different types

This page was built for publication: Randomized approximation schemes for minimizing the weighted makespan on identical parallel machines