Online scheduling of precedence-constrained jobs on a single machine (回路とシステム) Online scheduling of precedence-constrained jobs on a single machine

Search this Article

Author(s)

Abstract

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.

Journal

  • 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

Codes

  • NII Article ID (NAID)
    110009962282
  • NII NACSIS-CAT ID (NCID)
    AN10013094
  • Text Lang
    ENG
  • ISSN
    0913-5685
  • NDL Article ID
    025980393
  • NDL Call No.
    Z16-940
  • Data Source
    NDL  NII-ELS 
Page Top