An asymptotically optimal online algorithm to minimize the total completion time on two multipurpose machines with unit processing times

DOI10.1016/j.disopt.2012.07.005zbMath1254.90076MaRDI QIDQ1926488

Shlomo Karhi, Dvir Shabtay

Publication date: 28 December 2012

Published in: Discrete Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.disopt.2012.07.005

zbMATH Keywords

competitive ratio; online scheduling; total completion time; multipurpose machine scheduling

Mathematics Subject Classification ID

90B35: Deterministic scheduling theory in operations research

Related Items

Mixed coordination mechanisms for scheduling games on hierarchical machines, 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, Total completion time minimization in online hierarchical scheduling of unit-size jobs

Cites Work

• Scheduling unit length jobs on parallel machines with lookahead information
• Improved bounds for online scheduling with eligibility constraints
• 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
• Online scheduling of two job types on a set of multipurpose machines with unit processing times
• Optimal online algorithms for scheduling on two identical machines under a grade of service
• The Competitiveness of On-Line Assignments
• A POSTERIOR COMPETITIVENESS FOR LIST SCHEDULING ALGORITHM ON MACHINES WITH ELIGIBILITY CONSTRAINTS