Online Scheduling of a Single Machine to Minimize Total Weighted Completion Time

DOI10.1287/moor.1040.0092zbMath1082.90033OpenAlexW3135987664MaRDI QIDQ5704194

Chris N. Potts, Edward J. Anderson

Publication date: 11 November 2005

Published in: Mathematics of Operations Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1287/moor.1040.0092

zbMATH Keywords

scheduling, single machine, total weighted completion time, online algorithm, competitive ratio

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40) Deterministic scheduling theory in operations research (90B35) Approximation methods and heuristics in mathematical programming (90C59)

Related Items (40)

Online over time processing of combinatorial problems ⋮ Online parallel-batch scheduling to minimize total weighted completion time on single unbounded machine ⋮ Online scheduling to minimize maximum weighted flow-time on a bounded parallel-batch machine ⋮ Online scheduling with rejection to minimize the total weighted completion time plus the total rejection cost on parallel machines ⋮ Online scheduling on \(m\) uniform machines to minimize total (weighted) completion time ⋮ 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-ON-LINE SCHEDULING PROBLEM OF TWO PARALLEL MACHINES WITH COMMON MAINTENANCE TIME ⋮ Online scheduling on bounded batch machines to minimize the maximum weighted completion time ⋮ Best-Possible Online Algorithms for Single Machine Scheduling to Minimize the Maximum Weighted Completion Time ⋮ Online heuristic for the preemptive single machine scheduling problem of minimizing the total weighted completion time ⋮ Online scheduling to minimize the total weighted completion time plus the rejection cost ⋮ Online scheduling of simple linear deteriorating jobs to minimize the total general completion time ⋮ The efficiency-fairness balance of round robin scheduling ⋮ Competitive analysis of preemptive single-machine scheduling ⋮ An on-line scheduling problem of parallel machines with common maintenance time ⋮ On competitive analysis for polling systems ⋮ Competitive kill-and-restart and preemptive strategies for non-clairvoyant scheduling ⋮ Online scheduling of jobs with kind release times and deadlines on a single machine ⋮ Joint replenishment meets scheduling ⋮ Online Single Machine Scheduling to Minimize the Maximum Starting Time ⋮ Online scheduling of equal-length jobs with incompatible families on multiple batch machines to maximize the weighted number of early jobs ⋮ An improved 2.11-competitive algorithm for online scheduling on parallel machines to minimize total weighted completion time ⋮ Online over time scheduling on parallel-batch machines: a survey ⋮ Online scheduling with linear deteriorating jobs to minimize the total weighted completion time ⋮ The medical laboratory scheduling for weighted flow-time ⋮ Best semi-online algorithms for unbounded parallel batch scheduling ⋮ An optimal semi-online algorithm for a single machine scheduling problem with bounded processing time ⋮ Applying ``peeling onion approach for competitive analysis in online scheduling with rejection ⋮ Online Parallel-Machine Scheduling in KRT Environment to Minimize Total Weighted Completion Time ⋮ LPT online strategy for parallel-machine scheduling with kind release times ⋮ A \(2.28\)-competitive algorithm for online scheduling on identical machines ⋮ On-line scheduling of parallel machines to minimize total completion times ⋮ Scheduling of tasks with effectiveness precedence constraints ⋮ LP-based online scheduling: From single to parallel machines ⋮ Online scheduling to minimize total weighted (modified) earliness and tardiness cost ⋮ Online scheduling to minimize modified total tardiness with an availability constraint ⋮ Online scheduling of unit length jobs on a batching machine to maximize the number of early jobs with lookahead ⋮ An optimal online algorithm for single-processor scheduling problem with learning effect ⋮ Randomized selection algorithm for online stochastic unrelated machines scheduling

This page was built for publication: Online Scheduling of a Single Machine to Minimize Total Weighted Completion Time