A dynamic programming framework for non-preemptive scheduling problems on multiple machines

DOI10.1137/1.9781611973730.72MaRDI QIDQ5363000zbMATH OpenOpenAlexFDO

Authors Sungjin Im, Shi Li, Benjamin Moseley, Eric Torng

Publication date 5 October 2017

Published in Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/1.9781611973730.72

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35) Dynamic programming (90C39) Approximation algorithms (68W25)

Recommendations

• Approximating the optimal algorithm for online scheduling problems via dynamic programming
• Dual techniques for scheduling on a machine with varying speed
• Online Non-preemptive Scheduling in a Resource Augmentation Model based on Duality
• Scheduling jobs that arrive over time
• On minimizing the total flow time on multiple machines

Cited in

(6)

• scientific article; zbMATH DE number 7765369 (Why is no real title available?)
• Minimizing the maximum flow time in the online food delivery problem
• From preemptive to non-preemptive scheduling using rejections
• An \(\mathcal O(\log m)\)-competitive algorithm for online machine minimization
• Maximizing Throughput in Flow Shop Real-Time Scheduling
• Approximations for Throughput Maximization

This page was built for publication: A dynamic programming framework for non-preemptive scheduling problems on multiple machines

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