| Presentation | 2014/11/13 Online scheduling of precedence-constrained jobs on a single machine TAKAHIRO FUJITA, KOHEI HATANO, SHUJI KIJIMA, EIJI TAKIMOTO, |
|---|---|
| PDF Download Page | PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | 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. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | |
| Paper # | Vol.2014-AL-150 No.9 |
| Date of Issue |
| Conference Information | |
| Committee | MSS |
|---|---|
| Conference Date | 2014/11/13(1days) |
| Place (in Japanese) | (See Japanese page) |
| Place (in English) | |
| Topics (in Japanese) | (See Japanese page) |
| Topics (in English) | |
| Chair | |
| Vice Chair | |
| Secretary | |
| Assistant | |
| Paper Information | |
| Registration To | Mathematical Systems Science and its applications(MSS) |
|---|---|
| Language | ENG |
| Title (in Japanese) | (See Japanese page) |
| Sub Title (in Japanese) | (See Japanese page) |
| Title (in English) | Online scheduling of precedence-constrained jobs on a single machine |
| Sub Title (in English) | |
| Keyword(1) | |
| 1st Author's Name | TAKAHIRO FUJITA |
| 1st Author's Affiliation | Department of Informatics, Kyushu University() |
| 2nd Author's Name | KOHEI HATANO |
| 2nd Author's Affiliation | Department of Informatics, Kyushu University |
| 3rd Author's Name | SHUJI KIJIMA |
| 3rd Author's Affiliation | Department of Informatics, Kyushu University |
| 4th Author's Name | EIJI TAKIMOTO |
| 4th Author's Affiliation | Department of Informatics, Kyushu University |
| Date | 2014/11/13 |
| Paper # | Vol.2014-AL-150 No.9 |
| Volume (vol) | vol.114 |
| Number (no) | 313 |
| Page | pp.pp.- |
| #Pages | 5 |
| Date of Issue | |