Scheduling Unrelated Machines by Randomized Rounding

DOI10.1137/S0895480199357078zbMath1055.90040MaRDI QIDQ4785695

Andreas S. Schulz, Martin Skutella

Publication date: 5 January 2003

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

zbMATH Keywords

schedulingapproximation algorithmon-line algorithmlinear programming relaxationrandomized rounding

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Stochastic scheduling theory in operations research (90B36) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Approximation algorithms (68W25)

Related Items (31)

Scheduling maintenance jobs in networks ⋮ Serving in the Dark should be done Non-Uniformly ⋮ Scheduling Parallel-Task Jobs Subject to Packing and Placement Constraints ⋮ An \(R||C_{\max}\) quantum scheduling algorithm ⋮ Unrelated Machine Scheduling with Stochastic Processing Times ⋮ A better online algorithm for the parallel machine scheduling to minimize the total weighted completion time ⋮ Analysis of bounds for a capacitated single-item lot-sizing problem ⋮ Parallel-machine scheduling of jobs with mixed job-, machine- and position-dependent processing times ⋮ Performance analysis of fixed assignment policies for stochastic online scheduling on uniform parallel machines ⋮ The benefit of preemption with respect to the \(\ell_p\) norm ⋮ Power of Preemption for Minimizing Total Completion Time on Uniform Parallel Machines ⋮ An improved greedy algorithm for stochastic online scheduling on unrelated machines ⋮ GRASP with path-relinking for the non-identical parallel machine scheduling problem with minimising total weighted completion times ⋮ Scheduling to Minimize Total Weighted Completion Time via Time-Indexed Linear Programming Relaxations ⋮ Greed Works—Online Algorithms for Unrelated Machine Stochastic Scheduling ⋮ Static Routing in Stochastic Scheduling: Performance Guarantees and Asymptotic Optimality ⋮ Unrelated parallel machine scheduling -- perspectives and progress ⋮ Approximability of average completion time scheduling on unrelated machines ⋮ Non-identical parallel-machine scheduling research with minimizing total weighted completion times: models, relaxations and algorithms ⋮ On-line scheduling to minimize average completion time revisited. ⋮ Almost sure asymptotic optimality for online routing and machine scheduling problems ⋮ Unnamed Item ⋮ Online Parallel-Machine Scheduling in KRT Environment to Minimize Total Weighted Completion Time ⋮ A new approximation algorithm for unrelated parallel machine scheduling with release dates ⋮ Decentralized utilitarian mechanisms for scheduling games ⋮ LP-based online scheduling: From single to parallel machines ⋮ Truthfulness for the Sum of Weighted Completion Times ⋮ Lift-and-Round to Improve Weighted Completion Time on Unrelated Machines ⋮ Scheduling parallel machines with inclusive processing set restrictions and job release times ⋮ A Tight 2-Approximation for Preemptive Stochastic Scheduling ⋮ Stochastic Online Scheduling Revisited

This page was built for publication: Scheduling Unrelated Machines by Randomized Rounding