Semi-online scheduling on two uniform machines with the known largest size

DOI10.1007/S10878-009-9254-5MaRDI QIDQ491206zbMATH OpenOpenAlexFDO

Authors Sheng-Yi Cai, Qifan Yang

Publication date 24 August 2015

Published in Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s10878-009-9254-5

zbMATH Keywords

analysis of algorithmscompetitive ratiosemi-online schedulinguniform machines

Mathematics Subject Classification ID

Online algorithms; streaming algorithms (68W27) Analysis of algorithms (68W40) Deterministic scheduling theory in operations research (90B35) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• Semi-online scheduling with known maximum job size on two uniform machines
• Semi on-line scheduing problem with the largest processing time of jobs on two uniform machines known
• Semi-online scheduling with bounded job sizes on two uniform machines
• Two uniform machines with nearly equal speeds: unified approach to known sum and known optimum in semi on-line scheduling
• Two semi-online scheduling problems on two uniform machines

Cites work

• Bin stretching revisited
• Bounds for List Schedules on Uniform Processors
• Optimal non-preemptive semi-online scheduling on two related machines
• Optimal preemptive semi-online scheduling to minimize makespan on two related machines
• Preemptive and non-preemptive on-line algorithms for scheduling with rejection on two uniform machines
• Preemptive on-line scheduling for two uniform processors
• Randomized on-line scheduling on two uniform machines
• Semi on-line algorithms for the partition problem
• Semi-online scheduling on two uniform processors
• Semi-online scheduling with ``end of sequence information
• Two semi-online scheduling problems on two uniform machines

Cited in

(13)

• Online hierarchical scheduling on two machines with known total size of low-hierarchy jobs
• A survey on makespan minimization in semi-online environments
• Optimal preemptive online algorithms for scheduling with known largest size on two uniform machines
• Semi-online scheduling on two uniform parallel machines with initial lookahead
• Semi-online scheduling with bounded job sizes on two uniform machines
• Semi-online scheduling with known maximum job size on two uniform machines
• Two semi-online scheduling problems on two uniform machines
• Semi-online scheduling: a survey
• Semi on-line scheduing problem with the largest processing time of jobs on two uniform machines known
• A better semi-online algorithm for \(\mathrm Q3/s_{1} = s_{2}\leq s_{3}/C_{\mathrm{min}}\) with the known largest size
• Semi-online machine covering on two uniform machines with known total size
• Semi-online scheduling problems on two uniform machines under a grade of service provision
• Two uniform machines with nearly equal speeds: unified approach to known sum and known optimum in semi on-line scheduling

This page was built for publication: Semi-online scheduling on two uniform machines with the known largest size

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