Scheduling Parallel Machines On-Line

DOI10.1137/S0097539793248317zbMath0845.68042MaRDI QIDQ4862799

David P. Williamson, David B. Shmoys, Joel M. Wein

Publication date: 15 September 1996

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Analysis of algorithms and problem complexity (68Q25) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Deterministic scheduling theory in operations research (90B35) Discrete mathematics in relation to computer science (68R99)

Related Items (45)

A survey on makespan minimization in semi-online environments ⋮ Resource scheduling with variable requirements over time ⋮ On-line service scheduling ⋮ Online scheduling of two type parallel jobs on identical machines ⋮ Online scheduling on a parallel batch machine with delivery times and limited restarts ⋮ Scheduling with conflicts: Online and offline algorithms ⋮ On-line scheduling on parallel machines to minimize the makespan ⋮ ON ONLINE SCHEDULING JOBS WITH RESTART TO MAXIMIZE THE NUMBER OF JOBS COMPLETED TIME ON A SINGLE MACHINE ⋮ On an Online Traveling Repairman Problem with Flowtimes: Worst-Case and Average-Case Analysis ⋮ On-line scheduling mesh jobs with dependencies ⋮ Approximating call-scheduling makespan in all-optical networks ⋮ Scheduling on identical machines: How good is LPT in an on-line setting? ⋮ Scheduling parallel jobs to minimize the makespan ⋮ Competitive kill-and-restart and preemptive strategies for non-clairvoyant scheduling ⋮ An improved monotone algorithm for scheduling related machines with precedence constraints ⋮ Unnamed Item ⋮ A system-centric metric for the evaluation of online job schedules ⋮ Optimal algorithms for online single machine scheduling with deteriorating jobs ⋮ Online parallel machine scheduling to maximize the number of early jobs ⋮ Tight bounds for selfish and greedy load balancing ⋮ Makespan minimization in online scheduling with machine eligibility ⋮ A comment on scheduling on uniform machines under chain-type precedence constraints ⋮ Makespan minimization in online scheduling with machine eligibility ⋮ On-line scheduling on a single machine: Maximizing the number of early jobs ⋮ Online scheduling with equal processing times and machine eligibility constraints ⋮ The asymptotic performance ratio of an on-line algorithm for uniform parallel machine scheduling with release dates ⋮ An optimal online algorithm for scheduling on two parallel machines with GoS eligibility constraints ⋮ Online scheduling of malleable parallel jobs with setup times on two identical machines ⋮ An optimization-driven dynamic vehicle routing algorithm for on-demand meal delivery using drones ⋮ Online strip packing with modifiable boxes ⋮ On-line scheduling of parallel jobs with runtime restrictions ⋮ On-line single-server dial-a-ride problems ⋮ Online Scheduling of Incompatible Family Jobs with Equal Length on an Unbounded Parallel-Batch Machine with Job Delivery ⋮ Utilization of nonclairvoyant online schedules ⋮ Idle regulation in non-clairvoyant scheduling of parallel jobs ⋮ Heuristics for online scheduling on identical parallel machines with two GoS levels ⋮ On truthfulness and approximation for scheduling selfish tasks ⋮ Optimal and online preemptive scheduling on uniformly related machines ⋮ Fairness in parallel job scheduling ⋮ Restarts can help in the on-line minimization of the maximum delivery time on a single machine ⋮ On-line scheduling with precedence constraints ⋮ On an on-line scheduling problem for parallel jobs ⋮ An Online Scheduling Problem on a Drop-Line Parallel Batch Machine with Delivery Times and Limited Restart ⋮ A note on on-line scheduling with precedence constraints on identical machines ⋮ Speed scaling for maximum lateness

This page was built for publication: Scheduling Parallel Machines On-Line