Optimal online algorithms for scheduling on two identical machines under a grade of service
From MaRDI portal
Publication:2508148
DOI10.1631/jzus.2006.A0309zbMath1108.90314MaRDI QIDQ2508148
Yong He, Chunmei Tang, Yiwei Jiang
Publication date: 9 October 2006
Published in: Journal of Zhejiang University. Science A (Search for Journal in Brave)
Deterministic scheduling theory in operations research (90B35) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20)
Related Items
Total completion time minimization in online hierarchical scheduling of unit-size jobs ⋮ Online parallel machines scheduling with two hierarchies ⋮ OPTIMAL ONLINE ALGORITHMS ON TWO HIERARCHICAL MACHINES WITH RESOURCE AUGMENTATION ⋮ Semi-online early work maximization problem on two hierarchical machines with partial information of processing time ⋮ On the optimality of the \(TLS\) algorithm for solving the online-list scheduling problem with two job types on a set of multipurpose machines ⋮ A note on hierarchical scheduling on two uniform machines ⋮ Total completion time minimization scheduling on two hierarchical uniform machines ⋮ An asymptotically optimal online algorithm to minimize the total completion time on two multipurpose machines with unit processing times ⋮ Semi-online scheduling: a survey ⋮ Semi-online hierarchical scheduling for \(l_p\)-norm load balancing with buffer or rearrangements ⋮ Online scheduling on uniform machines with two hierarchies ⋮ Multiprofessor scheduling ⋮ Online hierarchical scheduling: an approach using mathematical programming ⋮ Bin stretching with migration on two hierarchical machines ⋮ Online scheduling on two parallel identical machines under a grade of service provision ⋮ Semi-online hierarchical load balancing problem with bounded processing times ⋮ Semi-online scheduling on 2 machines under a grade of service provision with bounded processing times ⋮ Online early work maximization on three hierarchical machines with a common due date ⋮ Online early work maximization problem on two hierarchical machines with buffer or rearrangements ⋮ Online and semi-online hierarchical scheduling for load balancing on uniform machines ⋮ Optimal algorithms for semi-online machine covering on two hierarchical machines ⋮ Preemptive scheduling on a small number of hierarchical machines ⋮ The hierarchical model for load balancing on two machines ⋮ Scheduling unit length jobs on parallel machines with lookahead information ⋮ Semi-Online Hierarchical Scheduling on Two Machines for lp-Norm Load Balancing ⋮ Makespan minimization in online scheduling with machine eligibility ⋮ Online scheduling on parallel machines with two goS levels ⋮ Semi-online algorithms for hierarchical scheduling on three parallel machines with a buffer size of 1 ⋮ Makespan minimization in online scheduling with machine eligibility ⋮ Online scheduling of two job types on a set of multipurpose machines with unit processing times ⋮ An FPTAS for parallel-machine scheduling under a grade of service provision to minimize makespan ⋮ On the optimality of the LP-based algorithm for online scheduling with GoS eligibility constraints ⋮ Optimal algorithm for semi-online scheduling on two machines under GoS levels ⋮ Heuristics for online scheduling on identical parallel machines with two GoS levels ⋮ Online scheduling with unit processing times and processing set restrictions ⋮ Scheduling parallel machines with inclusive processing set restrictions and job release times ⋮ Online hierarchical scheduling on two machines with known total size of low-hierarchy jobs ⋮ Online fractional hierarchical scheduling on uniformly related machines ⋮ Online scheduling with migration on two hierarchical machines ⋮ On-line booking policies and competitive analysis of medical examination in hospital ⋮ Optimal online algorithms on two hierarchical machines with tightly-grouped processing times
Cites Work
- Approximation algorithms for scheduling unrelated parallel machines
- Parallel machines scheduling with nonsimultaneous machine available time
- Exact bounds of the modified LPT algorithms applying to parallel machines scheduling with nonsimultaneous machine available times
- Optimal preemptive semi-online scheduling to minimize makespan on two related machines
- Parallel machine scheduling under a grade of service provision
- Optimal algorithms for semi-online preemptive scheduling problems on two uniform machines
- A note on parallel machine scheduling with non-simultaneous machine available time
- The Competitiveness of On-Line Assignments
