Makespan minimization in online scheduling with machine eligibility
From MaRDI portal
Publication:5919997
DOI10.1007/s10479-012-1271-6zbMath1272.90015MaRDI QIDQ5919997
Michael L. Pinedo, Kangbok Lee, Joseph Y.-T. Leung
Publication date: 8 August 2013
Published in: Annals of Operations Research (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s10479-012-1271-6
competitive ratio; makespan; parallel machine scheduling; eligibility constraint; interval and nested processing sets; offline scheduling; online and semi-online scheduling; tree-hierarchical and GoS processing sets
90B35: Deterministic scheduling theory in operations research
Related Items
Semi-Online Hierarchical Scheduling on Two Machines for lp-Norm Load Balancing, Online hierarchical scheduling on two machines with known total size of low-hierarchy jobs, Online scheduling to minimize maximum weighted flow-time on a bounded parallel-batch machine, A survey on makespan minimization in semi-online environments, Semi-online hierarchical scheduling for \(l_p\)-norm load balancing with buffer or rearrangements, On the optimality of the LP-based algorithm for online scheduling with GoS eligibility constraints, A multi-stage stochastic programming model of lot-sizing and scheduling problems with machine eligibilities and sequence-dependent setups, Competitive analysis of online machine rental and online parallel machine scheduling problems with workload fence, Online scheduling of jobs with favorite machines, Online scheduling with unit processing times and processing set restrictions, MIP models and a matheuristic algorithm for an identical parallel machine scheduling problem under multiple copies of shared resources constraints, Research on permutation flow shop scheduling problems with general position-dependent learning effects, Online scheduling on two parallel identical machines under a grade of service provision
Cites Work
- Fast approximation algorithms for job scheduling with processing set restrictions
- A note on hierarchical scheduling on two uniform machines
- Online hierarchical scheduling: an approach using mathematical programming
- Semi-online scheduling on 2 machines under a grade of service provision with bounded processing times
- Online and semi-online hierarchical scheduling for load balancing on uniform machines
- Scheduling jobs with equal processing times subject to machine eligibility constraints
- Scheduling unit length jobs on parallel machines with lookahead information
- Improved bounds for online scheduling with eligibility constraints
- Approximation algorithms for scheduling unrelated parallel machines
- On-line service scheduling
- Online parallel machines scheduling with two hierarchies
- Online scheduling on two uniform machines subject to eligibility constraints
- Online and semi-online scheduling of two machines under a grade of service provision
- Preemptive scheduling on a small number of hierarchical machines
- The hierarchical model for load balancing on two machines
- Online scheduling on parallel machines with two goS levels
- Online scheduling on two uniform machines to minimize the makespan
- Scheduling on identical machines: How good is LPT in an on-line setting?
- Online algorithms: a survey
- Online scheduling of two job types on a set of multipurpose machines with unit processing times
- Parallel machine scheduling under a grade of service provision
- Online scheduling on uniform machines with two hierarchies
- Worst-case analysis for on-line service policies
- Parallel machine scheduling with nested job assignment restrictions
- An optimal rounding gives a better approximation for scheduling unrelated machines
- Optimal online algorithms for scheduling on two identical machines under a grade of service
- Scheduling unit length jobs with parallel nested machine processing set restrictions
- Parallel machine scheduling with nested processing set restrictions
- Scheduling with Deadlines and Loss Functions
- On-Line Load Balancing in a Hierarchical Server Topology
- Scheduling parallel machines with inclusive processing set restrictions
- On Preemptive Scheduling of Unrelated Parallel Processors by Linear Programming
- Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
- The Competitiveness of On-Line Assignments
- Scheduling to Minimize Average Completion Time: Off-Line and On-Line Approximation Algorithms
- A POSTERIOR COMPETITIVENESS FOR LIST SCHEDULING ALGORITHM ON MACHINES WITH ELIGIBILITY CONSTRAINTS
- Scheduling Parallel Machines On-Line
- Makespan minimization in online scheduling with machine eligibility
- An optimal online algorithm for scheduling two machines with release times