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 (10)

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

This page was built for publication: Online scheduling of two job types on a set of multipurpose machines with unit processing times