On the optimality of list scheduling for online uniform machines scheduling

DOI10.1007/S11590-011-0335-XMaRDI QIDQ694192zbMATH OpenOpenAlexFDO

Authors Fangqiu Han, Zhiyi Tan, Yang Yang

Publication date 11 December 2012

Published in Optimization Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s11590-011-0335-x

zbMATH Keywords

onlinecompetitive analysisuniform machines

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35)

Recommendations

• Optimal online-list batch scheduling
• Online-list scheduling on a single bounded parallel-batch machine to minimize makespan
• Optimal and online preemptive scheduling on uniformly related machines
• STACS 2004
• Online scheduling on uniform machines with two hierarchies
• Online scheduling on \(m\) uniform machines to minimize total (weighted) completion time
• Online batch scheduling problem on uniform machines with agreeable processing times
• On-line preemptive scheduling on uniform machines
• A best possible on-line algorithm for scheduling on uniform parallel-batch machines
• Online scheduling with reassignment on two uniform machines

Cites work

• scientific article; zbMATH DE number 4130003 (Why is no real title available?)
• A new algorithm for online uniform-machine scheduling to minimize the makespan
• An On-Line Algorithm for Some Uniform Processor Scheduling
• An optimal algorithm for preemptive on-line scheduling
• Bounds for Certain Multiprocessing Anomalies
• Bounds for List Schedules on Uniform Processors
• Handbook of applied optimization
• Improved Bounds for the Online Scheduling Problem
• New lower and upper bounds for on-line scheduling
• On-Line Load Balancing for Related Machines
• Optimal Algorithms for the Online Time Series Search Problem
• Preemptive on-line scheduling for two uniform processors
• Preemptive online scheduling: Optimal algorithms for all speeds
• Randomized on-line scheduling on two uniform machines
• Tighter approximation bounds for LPT scheduling in two special cases

Cited in

(7)

• Lower bounds for online makespan minimization on a small number of related machines
• Competitive ratio of list scheduling on uniform machines and randomized heuristics
• On the optimality of the \(TLS\) algorithm for solving the online-list scheduling problem with two job types on a set of multipurpose machines
• Optimal online-list batch scheduling
• A survey on makespan minimization in semi-online environments
• A lower bound on deterministic online algorithms for scheduling on related machines without preemption
• A 2-competitive largest job on least loaded machine online algorithm based on the multi list scheduling model

This page was built for publication: On the optimality of list scheduling for online uniform machines scheduling

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