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.90076OpenAlexW2049627958MaRDI 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 ratioonline schedulingtotal completion timemultipurpose machine scheduling

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35)

Related Items (4)

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 ⋮ Total completion time minimization scheduling on two hierarchical uniform machines ⋮ Mixed coordination mechanisms for scheduling games on hierarchical machines

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

This page was built for publication: An asymptotically optimal online algorithm to minimize the total completion time on two multipurpose machines with unit processing times