On the optimality of the \(TLS\) algorithm for solving the online-list scheduling problem with two job types on a set of multipurpose machines

DOI10.1007/s10878-012-9460-4zbMath1275.90027OpenAlexW2036952194MaRDI QIDQ358659

Dvir Shabtay, Shlomo Karhi

Publication date: 9 August 2013

Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10878-012-9460-4

zbMATH Keywords

competitive analysismakespanonline schedulingalgorithm \(TLS\)multipurpose machines

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35)

Related Items (7)

Total completion time minimization in online hierarchical scheduling of unit-size jobs ⋮ Single machine scheduling with two competing agents, arbitrary release dates and unit processing times ⋮ Single machine scheduling with two competing agents and equal job processing times ⋮ Total completion time minimization scheduling on two hierarchical uniform machines ⋮ On-line Scheduling with a Monotonous Subsequence Constraint ⋮ Online packing of arbitrary sized items into designated and multipurpose bins ⋮ Optimal robot scheduling to minimize the makespan in a three-machine flow-shop environment with job-independent processing times

Cites Work

• 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
• On-Line Load Balancing in a Hierarchical Server Topology
• Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
• The Competitiveness of On-Line Assignments
• Parallel machine scheduling with job assignment restrictions
• Bounds for Certain Multiprocessing Anomalies
• Makespan minimization in online scheduling with machine eligibility

This page was built for publication: On the optimality of the \(TLS\) algorithm for solving the online-list scheduling problem with two job types on a set of multipurpose machines