WEKO3
アイテム
動的ジョブに対するスケジュール長最小化のためのアルゴリズム
https://ipsj.ixsq.nii.ac.jp/records/32758
https://ipsj.ixsq.nii.ac.jp/records/3275839994db6-799b-45d4-9d9b-bf3533fa7f1e
| 名前 / ファイル | ライセンス | アクション |
|---|---|---|
IPSJ-AL88003002.pdf (947.2 kB)
|
Copyright (c) 1988 by the Information Processing Society of Japan
|
|
| オープンアクセス | ||
| Item type | SIG Technical Reports(1) | |||||||
|---|---|---|---|---|---|---|---|---|
| 公開日 | 1988-09-22 | |||||||
| タイトル | ||||||||
| タイトル | 動的ジョブに対するスケジュール長最小化のためのアルゴリズム | |||||||
| タイトル | ||||||||
| 言語 | en | |||||||
| タイトル | Minimizing Schedule - Length for Jobs with Release Times | |||||||
| 言語 | ||||||||
| 言語 | jpn | |||||||
| 資源タイプ | ||||||||
| 資源タイプ識別子 | http://purl.org/coar/resource_type/c_18gh | |||||||
| 資源タイプ | technical report | |||||||
| 著者所属 | ||||||||
| 琉球大学工学部 | ||||||||
| 著者所属 | ||||||||
| 琉球大学工学部 | ||||||||
| 著者所属 | ||||||||
| 大阪大学工学部 | ||||||||
| 著者所属 | ||||||||
| 大阪大学工学部 | ||||||||
| 著者所属 | ||||||||
| 大阪大学工学部 | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| University of the Ryukyus | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| University of the Ryukyus | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| Osaka University | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| Osaka University | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| Osaka University | ||||||||
| 著者名 |
川口, 剛
× 川口, 剛
|
|||||||
| 著者名(英) |
Tsuyoshi, Kawaguchi
× Tsuyoshi, Kawaguchi
|
|||||||
| 論文抄録 | ||||||||
| 内容記述タイプ | Other | |||||||
| 内容記述 | 発生時刻の異なるジョブを、スケジュール長が最小となるようにm(≧1)台の均質プロセッサにスケジュールする問題が考察される。各ジョブi(1≦i≦n)は時刻a_iに発生し、その処理のためにp_i時間要す。またジョブは互いに独立である。この問題で特にすべてのa_iが等しい場合に対しては、これまでに多くのヒューリスティック・アルゴリズムが提案されている。しかし、a_iが任意の値をもつ場合に対しては、得られるスケジュールの良さが理論的に保鉦されるアルゴリズムは報告されていない。本論文では、a_iが任意の値をもつ場合に対して、O(n log n)の時間計算量をもつヒューリスティック・アルゴリズムを提案する。そして、このアルゴリズムによって得られるスケジュールのスケジュール長C(S_A)と最適スケジュールのスケジュール長C(S_O)の相対比C(S_A)/C(S_O)が、最悪の場合でも2-1/m以下となることを示す。またC(S_A)とC(S_O)の差が、最悪の場合でもp_iの最大値以下となることを示す。 | |||||||
| 論文抄録(英) | ||||||||
| 内容記述タイプ | Other | |||||||
| 内容記述 | In this paper we study the problem of nonpreemptively scheduling jobs on m identical processors so as to minimize schedule-length. Jobs have release times and processing times. There exists no precedence relation among jobs. An O(n log n) algorithm is presented for the problem. Let C(S_A) denote the schedule-length obtained by the proposed algorithm and C(S_O) be that of an optimal schedule. We show that the ratio C(S_A)/C(S_O) is bounded by 2-1/m and the difference between C(S_A) and C(S_O) does not exceed the processing time of the largest job. | |||||||
| 書誌レコードID | ||||||||
| 収録物識別子タイプ | NCID | |||||||
| 収録物識別子 | AN1009593X | |||||||
| 書誌情報 |
情報処理学会研究報告アルゴリズム（AL） 巻 1988, 号 69(1988-AL-003), p. 1-7, 発行日 1988-09-22 |
|||||||
| Notice | ||||||||
| SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc. | ||||||||
| 出版者 | ||||||||
| 言語 | ja | |||||||
| 出版者 | 情報処理学会 | |||||||
