Online scheduling of precedence-constrained jobs on a single machine (回路とシステム) Online scheduling of precedence-constrained jobs on a single machine
Search this Article
We consider an online job scheduling problem of precedence-constrained jobs on a single machine. In this problem, the player is supposed to determine a schedule of n fixed jobs at each trial, under the constraints that some jobs have higher priority than other jobs in each permutation. The goal is to minimize the sum of completion times over all jobs and T days, under precedence constraints. We propose an online job scheduling algorithm which predicts almost as well as the best known offline approximation algorithms in hindsight. Furthermore, our algorithm runs in O(n^4) time for each trial.
- IEICE technical report. Circuits and systems
IEICE technical report. Circuits and systems 114(312), 45-49, 2014-11-20
The Institute of Electronics, Information and Communication Engineers