On the Performance of Smith’s Rule in Single-Machine Scheduling with Nonlinear Cost

DOI10.1145/2629652zbMath1398.90049OpenAlexW2044030708MaRDI QIDQ4962185

Tobias Jacobs, Wiebke Höhn

Publication date: 30 October 2018

Published in: ACM Transactions on Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/2629652

zbMATH Keywords

schedulingsingle machinemin-sum objectiveuniversal sequenceSmith's ruleworst-case guaranteenonlinear cost

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Deterministic scheduling theory in operations research (90B35) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)

Related Items (11)

Dual Techniques for Scheduling on a Machine with Varying Speed ⋮ An Optimal Control Framework for Online Job Scheduling with General Cost Functions ⋮ The efficiency-fairness balance of round robin scheduling ⋮ On Submodular Search and Machine Scheduling ⋮ Splitting versus setup trade-offs for scheduling to minimize weighted completion time ⋮ The TV advertisements scheduling problem ⋮ Robust Appointment Scheduling with Heterogeneous Costs ⋮ Optimal algorithms for scheduling under time-of-use tariffs ⋮ How unsplittable-flow-covering helps scheduling with job-dependent cost functions ⋮ Unnamed Item ⋮ Submodular Maximization with Uncertain Knapsack Capacity

This page was built for publication: On the Performance of Smith’s Rule in Single-Machine Scheduling with Nonlinear Cost