Online scheduling on two uniform machines to minimize the makespan

DOI10.1016/J.TCS.2009.01.007zbMath1171.68005OpenAlexW2057160460WikidataQ57185766 ScholiaQ57185766MaRDI QIDQ1019187

Feifeng Zheng, Chengbin Chu, Ming Liu, Yin-Feng Xu

Publication date: 28 May 2009

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2009.01.007

zbMATH Keywords

competitive analysismakespanuniform machinesgrade of serviceonline schedulingreassignment

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Deterministic scheduling theory in operations research (90B35) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20)

Related Items (21)

A survey on makespan minimization in semi-online environments ⋮ Online scheduling on two uniform machines subject to eligibility constraints ⋮ ONLINE MINIMUM MAKESPAN SCHEDULING WITH A BUFFER ⋮ Semi-online scheduling: a survey ⋮ Semi-online scheduling with two GoS levels and unit processing time ⋮ Online scheduling on two parallel identical machines under a grade of service provision ⋮ Online scheduling with rearrangement on two related machines ⋮ Optimal semi-online algorithms for scheduling problems with reassignment on two identical machines ⋮ General parametric scheme for the online uniform machine scheduling problem with two different speeds ⋮ Online scheduling with one rearrangement at the end: revisited ⋮ Online scheduling with rejection and withdrawal ⋮ Optimal algorithms for online scheduling with bounded rearrangement at the end ⋮ Makespan minimization in online scheduling with machine eligibility ⋮ Online Makespan Scheduling with Job Migration on Uniform Machines ⋮ Fast approximation algorithms for uniform machine scheduling with processing set restrictions ⋮ Makespan minimization in online scheduling with machine eligibility ⋮ Online scheduling with reassignment on two uniform machines ⋮ A competitive online algorithm for minimizing total weighted completion time on uniform machines ⋮ Semi-online scheduling on two uniform parallel machines with initial lookahead ⋮ Online makespan scheduling with job migration on uniform machines ⋮ Heuristics for online scheduling on identical parallel machines with two GoS levels

Cites Work

• Unnamed Item
• Online and semi-online scheduling of two machines under a grade of service provision
• Online scheduling with reassignment
• Semi on-line algorithms for the partition problem
• Preemptive on-line scheduling for two uniform processors
• Parallel machine scheduling under a grade of service provision
• Semi-online scheduling on two uniform processors
• Bounds for List Schedules on Uniform Processors
• Automata, Languages and Programming
• Bounds for Certain Multiprocessing Anomalies
• Randomized on-line scheduling on two uniform machines

This page was built for publication: Online scheduling on two uniform machines to minimize the makespan