LP-based online scheduling: From single to parallel machines

DOI10.1007/s10107-007-0204-7zbMath1162.90009OpenAlexW2061672548WikidataQ65553909 ScholiaQ65553909MaRDI QIDQ1013970

José R. Correa, Michael R. Wagner

Publication date: 24 April 2009

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL: http://hdl.handle.net/10533/127845

zbMATH Keywords

Linear programmingOnline algorithmsParallel machine schedulingWeighted sum of completion times

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Deterministic scheduling theory in operations research (90B35) Approximation algorithms (68W25) Randomized algorithms (68W20)

Related Items (18)

Online Appointment Scheduling in the Random Order Model ⋮ Unrelated Machine Scheduling with Stochastic Processing Times ⋮ A better online algorithm for the parallel machine scheduling to minimize the total weighted completion time ⋮ Online scheduling problems with flexible release dates: applications to infrastructure restoration ⋮ A semi-online algorithm and its competitive analysis for parallel-machine scheduling problem with rejection ⋮ Performance analysis of fixed assignment policies for stochastic online scheduling on uniform parallel machines ⋮ Competitive analysis of preemptive single-machine scheduling ⋮ Online scheduling with deterioration and unexpected processor breakdown ⋮ An improved greedy algorithm for stochastic online scheduling on unrelated machines ⋮ Greed Works—Online Algorithms for Unrelated Machine Stochastic Scheduling ⋮ An improved 2.11-competitive algorithm for online scheduling on parallel machines to minimize total weighted completion time ⋮ Randomized mechanism design for decentralized network scheduling ⋮ Online Parallel-Machine Scheduling in KRT Environment to Minimize Total Weighted Completion Time ⋮ A \(2.28\)-competitive algorithm for online scheduling on identical machines ⋮ Asymptotical optimality of WSEPT for stochastic online scheduling on uniform machines ⋮ An optimal online algorithm for single-processor scheduling problem with learning effect ⋮ Randomized selection algorithm for online stochastic unrelated machines scheduling ⋮ A Tight 2-Approximation for Preemptive Stochastic Scheduling

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On-line scheduling to minimize average completion time revisited.
• Minimizing average completion time in the presence of release dates
• The power of \(\alpha\)-points in preemptive single machine scheduling.
• Randomized algorithms for on-line scheduling problems: How low can't you go?
• The asymptotic performance ratio of an on-line algorithm for uniform parallel machine scheduling with release dates
• Approximation Techniques for Average Completion Time Scheduling
• Single Machine Scheduling with Release Dates
• An Experimental Study of LP-Based Approximation Algorithms for Scheduling Problems
• A guessing game and randomized online algorithms
• A Global Constraint for Total Weighted Completion Time
• Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
• Scheduling to Minimize Average Completion Time: Off-Line and On-Line Approximation Algorithms
• Scheduling Unrelated Machines by Randomized Rounding
• List Scheduling in Order of α-Points on a Single Machine
• An experimental study of online scheduling algorithms
• Online Scheduling of a Single Machine to Minimize Total Weighted Completion Time

This page was built for publication: LP-based online scheduling: From single to parallel machines