Optimal semi-online algorithms for preemptive scheduling problems with inexact partial information

DOI10.1007/S00236-007-0058-8MaRDI QIDQ2464037zbMATH OpenOpenAlexFDO

Authors Yiwei Jiang, Yong He

Publication date 10 December 2007

Published in Acta Informatica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00236-007-0058-8

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Deterministic scheduling theory in operations research (90B35)

Recommendations

• Algorithms and Computation
• Computing and Combinatorics
• Semi-online scheduling problems on two identical machines with inexact partial information
• Semi-online scheduling on two identical processors with two types of partial information
• Optimal Semi-online Scheduling Algorithms on a Small Number of Machines

Cites work

• A Level Algorithm for Preemptive Scheduling
• A lower bound for on-line scheduling on uniformly related machines
• An optimal algorithm for preemptive on-line scheduling
• Bin stretching revisited
• On-line bin-stretching
• Optimal algorithms for semi-online preemptive scheduling problems on two uniform machines
• Optimal preemptive on-line scheduling on uniform processors with non-decreasing speed ratios
• Optimal preemptive semi-online scheduling to minimize makespan on two related machines
• Optimal semi-online preemptive algorithms for machine covering on two uniform machines
• Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
• Ordinal algorithms for parallel machine scheduling
• Ordinal on-line scheduling for maximizing the minimum machine completion time
• Preemptive on-line scheduling for two uniform processors
• Preemptive Online Scheduling: Optimal Algorithms for All Speeds
• Preemptive Scheduling of Uniform Processor Systems
• Randomized on-line scheduling on two uniform machines
• Scheduling with deadlines and loss functions
• Semi on-line algorithms for the partition problem
• Semi on-line scheduling on two identical machines
• Semi-on-line problems on two identical machines with combined partial information
• Semi-on-line scheduling with ordinal data on two uniform machines
• Semi-online scheduling problems on two identical machines with inexact partial information
• Semi-online scheduling with decreasing job sizes
• STACS 2004

Cited in

(7)

• Semi-online scheduling: a survey
• Semi-online preemptive scheduling: one algorithm for all variants
• Coping with Incomplete Information in Scheduling — Stochastic and Online Models
• Computing and Combinatorics
• Algorithms and Computation
• Tighter bounds on non-clairvoyant parallel machine scheduling with prediction to minimize makespan
• Semi-online scheduling problems on two identical machines with inexact partial information

This page was built for publication: Optimal semi-online algorithms for preemptive scheduling problems with inexact partial information

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2464037)