Online heuristic for the preemptive single machine scheduling problem of minimizing the total weighted completion time

DOI10.1080/10556788.2013.854360zbMath1299.90131OpenAlexW2037005161MaRDI QIDQ2926062

Mikhail Batsyn, Pavel Sukhov, Boris I. Goldengorin, Panos M. Pardalos

Publication date: 29 October 2014

Published in: Optimization Methods and Software (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1080/10556788.2013.854360

zbMATH Keywords

single machine schedulingefficient heuristicweighted shortest remaining processing timeWSRPT rule

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35) Approximation methods and heuristics in mathematical programming (90C59) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20)

Related Items

An exact algorithm for the preemptive single machine scheduling of equal-length jobs ⋮ Preemptive scheduling in a two-stage supply chain to minimize the makespan ⋮ Discrete and continuous-time formulations for dealing with break periods: preemptive and non-preemptive scheduling

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Minimizing total weighted tardiness on a single machine with release dates and equal-length jobs
• Scheduling jobs with equal processing times and time windows on identical parallel machines
• An algorithm for single machine sequencing with release dates to minimize total weighted completion time
• Scheduling with release dates on a single machine to minimize total weighted completion time
• A 1. 47-approximation for a preemptive single-machine scheduling problem
• Lower tolerance-based branch and bound algorithms for the ATSP
• Branch-and-bound method for minimizing the weighted completion time scheduling problem on a single machine with release dates
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• An improved approximation algorithm for the single machine total completion time scheduling problem with availability constraints
• Scheduling with limited machine availability
• Single Machine Scheduling with Release Dates
• Computer-Aided complexity classification of combinational problems
• Online Scheduling of a Single Machine to Minimize Total Weighted Completion Time