Online scheduling of two job types on a set of multipurpose machines with unit processing times

DOI10.1016/j.cor.2011.05.002zbMath1251.90187MaRDI QIDQ1761990

Dvir Shabtay, Shlomo Karhi

Publication date: 15 November 2012

Published in: Computers \& Operations Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.cor.2011.05.002

zbMATH Keywords

competitive ratio; online scheduling; eligibility constraint; multipurpose machine scheduling

Mathematics Subject Classification ID

90C60: Abstract computational complexity for mathematical programming problems

90B35: Deterministic scheduling theory in operations research

68W27: Online algorithms; streaming algorithms

Related Items

Makespan minimization in online scheduling with machine eligibility, Dynamic scheduling with uncertain job types, On the optimality of the \(TLS\) algorithm for solving the online-list scheduling problem with two job types on a set of multipurpose machines, Semi-online scheduling with two GoS levels and unit processing time, Single-machine scheduling with workload-dependent tool change durations and equal processing time jobs to minimize total completion time, 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, Online scheduling of jobs with favorite machines, Online scheduling with unit processing times and processing set restrictions, Total completion time minimization in online hierarchical scheduling of unit-size jobs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Approximation algorithms for scheduling unrelated parallel machines
• Online parallel machines scheduling with two hierarchies
• Online and semi-online scheduling of two machines under a grade of service provision
• Online scheduling on parallel machines with two goS levels
• New algorithms for an ancient scheduling problem.
• Parallel machine scheduling of machine-dependent jobs with unit-length.
• Parallel machine scheduling under a grade of service provision
• New lower and upper bounds for on-line scheduling
• 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
• On-Line Load Balancing in a Hierarchical Server Topology
• Scheduling parallel machines with inclusive processing set restrictions
• An On-Line Scheduling Heuristic with Better Worst-Case Ratio Than Graham’s List Scheduling
• Task Scheduling on a Multiprocessor System with Independent Memories
• Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
• The Competitiveness of On-Line Assignments
• A POSTERIOR COMPETITIVENESS FOR LIST SCHEDULING ALGORITHM ON MACHINES WITH ELIGIBILITY CONSTRAINTS
• Improved Bounds for the Online Scheduling Problem
• A Better Algorithm for an Ancient Scheduling Problem
• Parallel machine scheduling with job assignment restrictions
• Semi-matchings for bipartite graphs and load balancing
• Bounds for Certain Multiprocessing Anomalies
• Makespan minimization in online scheduling with machine eligibility