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

DOI10.1016/j.cor.2011.05.002zbMath1251.90187OpenAlexW2162270659MaRDI 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 ratioonline schedulingeligibility constraintmultipurpose machine scheduling

Mathematics Subject Classification ID

Abstract computational complexity for mathematical programming problems (90C60) Deterministic scheduling theory in operations research (90B35) Online algorithms; streaming algorithms (68W27)

Related Items

Total completion time minimization in online hierarchical scheduling of unit-size jobs, Single-machine scheduling with workload-dependent tool change durations and equal processing time jobs to minimize total completion 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, 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 with two GoS levels and unit processing time, Dynamic scheduling with uncertain job types, Makespan minimization in online scheduling with machine eligibility, Online scheduling of jobs with favorite machines, Online scheduling with unit processing times and processing set restrictions

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