Optimal on-line algorithms for single-machine scheduling

DOI10.1007/3-540-61310-2_30zbMath1414.90152OpenAlexW1585522101MaRDI QIDQ4645938

No author found.

Publication date: 11 January 2019

Published in: Integer Programming and Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/3-540-61310-2_30

zbMATH Keywords

single-machine schedulingonline algorithmsworst-case analysis

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35) Combinatorial optimization (90C27) Online algorithms; streaming algorithms (68W27)

Related Items (24)

Online parallel-batch scheduling to minimize total weighted completion time on single unbounded machine ⋮ Online integrated production-distribution scheduling problems without preemption ⋮ Online scheduling problems with flexible release dates: applications to infrastructure restoration ⋮ A best possible algorithm for an online scheduling problem with position-based learning effect ⋮ A semi-online algorithm and its competitive analysis for parallel-machine scheduling problem with rejection ⋮ Online scheduling of simple linear deteriorating jobs to minimize the total general completion time ⋮ On competitive analysis for polling systems ⋮ Competitive kill-and-restart and preemptive strategies for non-clairvoyant scheduling ⋮ Joint replenishment meets scheduling ⋮ An improved greedy algorithm for stochastic online scheduling on unrelated machines ⋮ A best possible online algorithm for minimizing the total completion time and the total soft penalty cost ⋮ Integrated Scheduling of Production and Two-Stage Delivery of Make-to-Order Products: Offline and Online Algorithms ⋮ Online over time scheduling on parallel-batch machines: a survey ⋮ Robust algorithms for total completion time ⋮ Optimal on-line flow time with resource augmentation ⋮ Asymptotic analysis of an on-line algorithm for the single machine completion time problem with release dates ⋮ Applying ``peeling onion approach for competitive analysis in online scheduling with rejection ⋮ A \(2.28\)-competitive algorithm for online scheduling on identical machines ⋮ On-line scheduling of parallel machines to minimize total completion times ⋮ A class of on-line scheduling algorithms to minimize total completion time ⋮ An optimal online algorithm for single-processor scheduling problem with learning effect ⋮ Randomized selection algorithm for online stochastic unrelated machines scheduling ⋮ On-line booking policies and competitive analysis of medical examination in hospital ⋮ An Optimal Online Algorithm for Scheduling with Learning Consideration

Cites Work

• Unnamed Item
• Unnamed Item
• New lower and upper bounds for on-line scheduling
• PERFORMANCE ANALYSIS OF SIX APPROXIMATION ALGORITHMS FOR THE ONE-MACHINE MAXIMUM LATENESS SCHEDULING PROBLEM WITH READY TIMES
• Scheduling jobs that arrive over time
• Bounds for Certain Multiprocessing Anomalies

This page was built for publication: Optimal on-line algorithms for single-machine scheduling