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.005MaRDI QIDQ1926488zbMATH OpenOpenAlexFDO

Authors Dvir Shabtay, Shlomo Karhi

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 ratiomultipurpose machine schedulingonline schedulingtotal completion time

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35)

Recommendations

• Online scheduling of two job types on a set of multipurpose machines with unit processing times
• Online scheduling of two uniform machines to minimize total completion times
• An optimal online algorithm for single machine scheduling to minimize total general completion time
• Total completion time minimization in online hierarchical scheduling of unit-size jobs
• A class of on-line scheduling algorithms to minimize total completion time

Cites work

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

Cited in

(8)

• 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
• Online scheduling of two job types on a set of multipurpose machines with unit processing times
• Total completion time minimization in online hierarchical scheduling of unit-size jobs
• On the Asymptotic Optimality of a Simple On-Line Algorithm for the Stochastic Single-Machine Weighted Completion Time Problem and Its Extensions
• On the optimality of the \(TLS\) algorithm for solving the online-list scheduling problem with two job types on a set of multipurpose machines
• Mixed coordination mechanisms for scheduling games on hierarchical machines
• Comments on ``Competitive analysis of a better on-line algorithm to minimize total completion time on a single-machine

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1926488)