We consider the problem of scheduling operations/nodes, the dependency among which is characterized by a Directed Acyclic Graph (DAG). Due to its NP-hard nature, heuristic algorithms were traditionally used to acquire reasonably good solutions, and more recent works have proposed Machine Learning (ML) heuristics that can generalize to unseen graphs and outperform the non-ML heuristics. However, it is computationally costly to generate solutions using existing ML schedulers since they adopt the episodic reinforcement learning framework that necessitates multi-round neural network processing. We propose a novel ML scheduler that uses a one-shot neural network encoder to sample node priorities which are converted by list scheduling to the final schedules. Since the one-shot encoder can efficiently sample the priorities in parallel, our algorithm runs significantly faster than existing ML baselines and has comparable run time with the fast traditional heuristics. We empirically show that our algorithm generates better schedules than both non-neural and neural baselines across various real-world and synthetic scheduling tasks.
Wonseok Jeon (Qualcomm AI Research)
Mukul Gagrani (QualComm)
Burak Bartan (Stanford University)
Weiliang Zeng (QualComm)
Harris Teague (Qualcomm)
Piero Zappi (Qualcomm Tech. Inc.)
Piero Zappi is a Sr. Staff research Engineer at Qualcomm. His current work focus on applying ML to combinatorial optimization problems.
Christopher Lott (Qualcomm AI Research)
More from the Same Authors
2022 Poster: Local Metric Learning for Off-Policy Evaluation in Contextual Bandits with Continuous Actions »
Haanvid Lee · Jongmin Lee · Yunseon Choi · Wonseok Jeon · Byung-Jun Lee · Yung-Kyun Noh · Kee-Eung Kim
2022 Poster: Neural Topological Ordering for Computation Graphs »
Mukul Gagrani · Corrado Rainone · Yang Yang · Harris Teague · Wonseok Jeon · Roberto Bondesan · Herke van Hoof · Christopher Lott · Weiliang Zeng · Piero Zappi
2020 Poster: Debiasing Distributed Second Order Optimization with Surrogate Sketching and Scaled Regularization »
Michal Derezinski · Burak Bartan · Mert Pilanci · Michael Mahoney