New algorithms for an ancient scheduling problem.
From MaRDI portal
Publication:960514
DOI10.1006/jcss.1995.1074zbMath1295.90008OpenAlexW4210281823MaRDI QIDQ960514
Amos Fiat, Yair Bartal, Howard J. Karloff, Rakesh V. Vohra
Publication date: 21 December 2008
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1006/jcss.1995.1074
Nonnumerical algorithms (68W05) Deterministic scheduling theory in operations research (90B35) Randomized algorithms (68W20)
Related Items
A survey on makespan minimization in semi-online environments ⋮ Online makespan minimization with parallel schedules ⋮ A lower bound for randomized on-line multiprocessor scheduling ⋮ Scheduling with testing on multiple identical parallel machines ⋮ Online makespan minimization with budgeted uncertainty ⋮ List's worst-average-case or WAC ratio ⋮ On two dimensional packing ⋮ Separating online scheduling algorithms with the relative worst order ratio ⋮ Robust Polynomial-Time Approximation Schemes for Parallel Machine Scheduling with Job Arrivals and Departures ⋮ Scheduling resource allocation with timeslot penalty for changeover ⋮ ONLINE MINIMUM MAKESPAN SCHEDULING WITH A BUFFER ⋮ Approximation and online algorithms for multidimensional bin packing: a survey ⋮ On the value of job migration in online makespan minimization ⋮ Scheduling web advertisements: a note on the minspace problem ⋮ On-line scheduling of parallel jobs ⋮ Randomized algorithms for that ancient scheduling problem ⋮ Improved semi-online makespan scheduling with a reordering buffer ⋮ Semi-online scheduling problems on a small number of machines ⋮ Improved upper bounds for online malleable job scheduling ⋮ An on-line algorithm for some uniform processor Scheduling ⋮ Machine covering in the random-order model ⋮ Online scheduling with rearrangement on two related machines ⋮ Competitive ratio of list scheduling on uniform machines and randomized heuristics ⋮ Improved algorithm for a generalized on-line scheduling problem on identical machines ⋮ Unnamed Item ⋮ Semi-online scheduling revisited ⋮ Randomized on-line scheduling on three processors. ⋮ The \(k\)-server problem ⋮ Tight Bounds for Online Vector Scheduling ⋮ Online scheduling with rejection and withdrawal ⋮ Optimal on-line algorithms to minimize makespan on two machines with resource augmentation ⋮ Scheduling unit length jobs on parallel machines with lookahead information ⋮ On Approximation Algorithms for Two-Stage Scheduling Problems ⋮ Online scheduling with rejection and reordering: exact algorithms for unit size jobs ⋮ Scheduling In the random-order model ⋮ Online Makespan Scheduling with Job Migration on Uniform Machines ⋮ Semi-online scheduling with decreasing job sizes ⋮ Online scheduling for jobs with nondecreasing release times and similar lengths on parallel machines ⋮ Online scheduling of two job types on a set of multipurpose machines with unit processing times ⋮ Minimizing the maximum starting time on-line ⋮ Randomized on-line scheduling on two uniform machines ⋮ Randomized priority algorithms ⋮ Competitive routing of virtual circuits with unknown duration ⋮ Multipurpose machine scheduling with rejection and identical job processing times ⋮ Optimal preemptive on-line scheduling on uniform processors with non-decreasing speed ratios ⋮ On-line algorithms for packing rectangles into several strips ⋮ Improved bounds for online scheduling with eligibility constraints ⋮ Load balancing of temporary tasks in the \(\ell _{p}\) norm ⋮ Preemptive multiprocessor scheduling with rejection ⋮ Randomized on-line scheduling similar jobs to minimize makespan on two identical processors ⋮ On-line bin-stretching ⋮ An optimal online algorithm for scheduling two machines with release times ⋮ Online scheduling of jobs with favorite machines ⋮ Heuristic scheduling of parallel machines with sequence-dependent set-up times ⋮ Greedy is optimal for online restricted assignment and smart grid scheduling for unit size jobs ⋮ Semi on-line algorithms for the partition problem ⋮ Online makespan scheduling with job migration on uniform machines ⋮ Scheduling uniform machines on-line requires nondecreasing speed ratios ⋮ A 2-competitive largest job on least loaded machine online algorithm based on the multi list scheduling model ⋮ New results on competitive analysis of online SRPT scheduling ⋮ Semi-online scheduling jobs with tightly-grouped processing times on three identical machines ⋮ Approximating the Optimal Algorithm for Online Scheduling Problems via Dynamic Programming ⋮ On-line scheduling revisited ⋮ A manifesto for the computational method ⋮ Some recent results in the analysis of greedy algorithms for assignment problems
