| 講演名 | 2014/11/13 Online scheduling of precedence-constrained jobs on a single machine , |
|---|---|
| PDFダウンロードページ | PDFダウンロードページへ |
| 抄録(和) | |
| 抄録(英) | 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. |
| キーワード(和) | |
| キーワード(英) | |
| 資料番号 | Vol.2014-AL-150 No.9 |
| 発行日 |
| 研究会情報 | |
| 研究会 | MSS |
|---|---|
| 開催期間 | 2014/11/13(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Mathematical Systems Science and its applications(MSS) |
|---|---|
| 本文の言語 | ENG |
| タイトル（和） | |
| サブタイトル（和） | |
| タイトル（英） | Online scheduling of precedence-constrained jobs on a single machine |
| サブタイトル（和） | |
| キーワード(1)（和/英） | |
| 第 1 著者 氏名（和/英） | / TAKAHIRO FUJITA |
| 第 1 著者 所属（和/英） | Department of Informatics, Kyushu University |
| 発表年月日 | 2014/11/13 |
| 資料番号 | Vol.2014-AL-150 No.9 |
| 巻番号（vol） | vol.114 |
| 号番号（no） | 313 |
| ページ範囲 | pp.- |
| ページ数 | 5 |
| 発行日 | |