An efficient algorithm for semi-online multiprocessor scheduling with given total processing time

DOI10.1007/S10951-015-0430-4MaRDI QIDQ906558zbMATH OpenOpenAlexFDO

Authors V. M. Kotov, Michaël Gabay, Hans Kellerer

Publication date 22 January 2016

Published in Journal of Scheduling (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s10951-015-0430-4

zbMATH Keywords

competitive analysismultiprocessor schedulingsemi-online scheduling

Mathematics Subject Classification ID

Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Online algorithms; streaming algorithms (68W27) Deterministic scheduling theory in operations research (90B35)

Recommendations

• Semi-on-line multiprocessor scheduling with given total processing time
• SEMI-ON-LINE PARALLEL MACHINES SCHEDULING UNDER KNOWN TOTAL AND LARGEST PROCESSING TIMES
• scientific article; zbMATH DE number 5669942
• Lower bounds and semi on-line multiprocessor scheduling
• Semi-online scheduling problems on a small number of machines

Cites work

• An efficient algorithm for bin stretching
• Better Algorithms for Online Bin Stretching
• Bounds for Certain Multiprocessing Anomalies
• Bounds on Multiprocessing Timing Anomalies
• scientific article; zbMATH DE number 4130003 (Why is no real title available?)
• On-line bin-stretching
• On-line scheduling revisited
• Recent advances for a classical scheduling problem
• Semi on-line algorithms for the partition problem
• Semi-on-line multiprocessor scheduling with given total processing time
• Semi-online scheduling revisited
• The on-line multiprocessor scheduling problem with known sum of the tasks

Cited in

(23)

• A survey on makespan minimization in semi-online environments
• General parametric scheme for the online uniform machine scheduling problem with two different speeds
• Algorithms better than LPT for semi-online scheduling with decreasing processing times
• Lower bounds and semi on-line multiprocessor scheduling
• An improved parametric algorithm on two-machine scheduling with given lower and upper bounds for the total processing time
• Competitive analysis of online machine rental and online parallel machine scheduling problems with workload fence
• Tight lower bounds for semi-online scheduling on two uniform machines with known optimum
• Semi-online scheduling: a survey
• scientific article; zbMATH DE number 5669942 (Why is no real title available?)
• Semi-online scheduling revisited
• scientific article; zbMATH DE number 2090589 (Why is no real title available?)
• A semi-online algorithm for single machine scheduling with rejection
• Semi-on-line multiprocessor scheduling with given total processing time
• Bin stretching with migration on two hierarchical machines
• Parallel solutions for preemptive makespan scheduling on two identical machines
• Online early work maximization on three hierarchical machines with a common due date
• Semi-online scheduling on two identical parallel machines with initial-lookahead information
• Online two-dimensional load balancing
• Fifty years of research in scheduling -- theory and applications
• Semi-online multiprocessor scheduling with known largest job processing time
• Improved online load balancing with known makespan
• Scheduling with testing on multiple identical parallel machines
• Semi on-line scheduling on three processors with known sum of the tasks

This page was built for publication: An efficient algorithm for semi-online multiprocessor scheduling with given total processing time

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