A survey on makespan minimization in semi-online environments
From MaRDI portal
Publication:1617278
DOI10.1007/s10951-018-0567-zzbMath1406.90041OpenAlexW2797898895MaRDI QIDQ1617278
Publication date: 7 November 2018
Published in: Journal of Scheduling (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s10951-018-0567-z
Deterministic scheduling theory in operations research (90B35) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Online algorithms; streaming algorithms (68W27)
Related Items (9)
Semi-online scheduling on two identical machines with a common due date to maximize total early work ⋮ Scheduling with testing on multiple identical parallel machines ⋮ Competitive analysis of online machine rental and online parallel machine scheduling problems with workload fence ⋮ Semi-online scheduling: a survey ⋮ Machine covering in the random-order model ⋮ Dynamic scheduling of patients in emergency departments ⋮ A new lower bound for classic online bin packing ⋮ An improved parametric algorithm on two-machine scheduling with given lower and upper bounds for the total processing time ⋮ Starting time minimization for the maximum job variant
Cites Work
- Semi-on-line scheduling with ordinal data on two uniform machines
- Semi on-line scheduling on two parallel processors with known sum and lower bound on the size of the tasks
- On-line bin-stretching
- Semi-online scheduling with combined information on two identical machines in parallel
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A simple semi on-line algorithm for \(\mathrm{P}2//C_{\max}\) with a buffer
- Semi-online scheduling with bounded job sizes on two uniform machines
- Improved semi-online makespan scheduling with a reordering buffer
- Semi-online scheduling problems on a small number of machines
- Lower bounds for online makespan minimization on a small number of related machines
- Semi-online scheduling revisited
- Online scheduling with one rearrangement at the end: revisited
- Semi-online scheduling on two uniform machines with the known largest size
- Two uniform machines with nearly equal speeds: unified approach to known sum and known optimum in semi on-line scheduling
- Online algorithms with advice for bin packing and scheduling problems
- Online bin stretching with bunch techniques
- Semi-online preemptive scheduling: one algorithm for all variants
- On robust online scheduling algorithms
- Semi-online scheduling with known partial information about job sizes on two identical machines
- Semi-on-line multiprocessor scheduling with given total processing time
- Semi-online scheduling with known maximum job size on two uniform machines
- Online scheduling with rearrangement on two related machines
- Competitive ratio of list scheduling on uniform machines and randomized heuristics
- Optimal algorithms for online scheduling with bounded rearrangement at the end
- On the optimality of list scheduling for online uniform machines scheduling
- Online scheduling with a buffer on related machines
- Several semi-online scheduling problems on two identical machines with combined information
- Semi on-line scheduling on three processors with known sum of the tasks
- A new algorithm for online uniform-machine scheduling to minimize the makespan
- Semi-online scheduling problems on two identical machines with inexact partial information
- An efficient algorithm for semi-online multiprocessor scheduling with given total processing time
- Online scheduling with reassignment
- New algorithms for an ancient scheduling problem.
- Online scheduling with reassignment on two uniform machines
- Two semi-online scheduling problems on two uniform machines
- Extension of algorithm list scheduling for a semi-online scheduling problem
- Online scheduling on two uniform machines to minimize the makespan
- Tighter approximation bounds for LPT scheduling in two special cases
- Optimal and online preemptive scheduling on uniformly related machines
- Semi on-line algorithms for the partition problem
- Improved bounds for on-line load balancing
- Semi on-line scheduling on two identical machines
- A better lower bound for on-line scheduling
- Nonclairvoyant scheduling
- Bin stretching revisited
- The optimal on-line parallel machine scheduling
- New algorithms for related machines with temporary jobs.
- On-line scheduling revisited
- Tight upper bounds for semi-online scheduling on two uniform machines with known optimum
- A two-phase algorithm for bin stretching with stretching factor 1.5
- Online bin stretching with three bins
- General parametric scheme for the online uniform machine scheduling problem with two different speeds
- A theory and algorithms for combinatorial reoptimization
- Algorithms better than LPT for semi-online scheduling with decreasing processing times
- Semi-on-line scheduling on two parallel processors with an upper bound on the items
- Pseudo lower bounds for online parallel machine scheduling
- Semi-on-line problems on two identical machines with combined partial information
- Semi-online algorithms for parallel machine scheduling problems
- A note on on-line scheduling with partial information
- New lower and upper bounds for on-line scheduling
- Ordinal algorithms for parallel machine scheduling
- Optimal semi-online algorithms for scheduling problems with reassignment on two identical machines
- A lower bound on deterministic online algorithms for scheduling on related machines without preemption
- Online makespan minimization with parallel schedules
- New approximation bounds for LPT scheduling
- Improved lower bounds for the online bin stretching problem
- On the value of job migration in online makespan minimization
- An efficient algorithm for bin stretching
- Semi-online scheduling with ``end of sequence information
- The on-line multiprocessor scheduling problem with known sum of the tasks
- Semi-online scheduling on two uniform processors
- Semi-online scheduling jobs with tightly-grouped processing times on three identical machines
- Weighted Online Problems with Advice
- ONLINE MINIMUM MAKESPAN SCHEDULING WITH A BUFFER
- Online Scheduling with Bounded Migration
- The Power of Reordering for Online Minimum Makespan Scheduling
- Scheduling Independent Tasks on Uniform Processors
- On randomized online scheduling
- Optimal Semi-online Scheduling Algorithms on a Small Number of Machines
- Tighter Bounds for LPT Scheduling on Uniform Processors
- Bounds for List Schedules on Uniform Processors
- An On-Line Scheduling Heuristic with Better Worst-Case Ratio Than Graham’s List Scheduling
- Bounds for LPT Schedules on Uniform Processors
- Better Bounds for Online Scheduling
- A Note on "An On-Line Scheduling Heuristic with Better Worst Case Ratio than Graham's List Scheduling"
- A Parametric Worst Case Analysis of the LPT Heuristic for Two Uniform Machines
- On-line routing of virtual circuits with applications to load balancing and machine scheduling
- An On-Line Algorithm for Some Uniform Processor Scheduling
- Improved Bounds for the Online Scheduling Problem
- Scheduling Parallel Machines On-Line
- A Better Algorithm for an Ancient Scheduling Problem
- Load Balancing for Response Time
- On-Line Load Balancing for Related Machines
- Online Makespan Scheduling with Sublinear Advice
- Recent Advances for a Classical Scheduling Problem
- Algorithms – ESA 2005
- Bounds for Certain Multiprocessing Anomalies
- Bounds on Multiprocessing Timing Anomalies
- Optimal non-preemptive semi-online scheduling on two related machines
- Makespan minimization in online scheduling with machine eligibility
- Semi-online scheduling with decreasing job sizes
- Randomized on-line scheduling on two uniform machines
This page was built for publication: A survey on makespan minimization in semi-online environments
