準備時間と先行制約を伴う並列機械スケジューリング問題の近似解法について
スポンサーリンク
概要
- 論文の詳細を見る
This paper discusses a parallel-machine scheduling problem where many jobs are scheduled on identical parallel machines so as to minimize the maximum lateness under precedence constraints given by partial order, each job having an arbitrary ready time, a unit processing time and an arbitrary due date. This problem is well known to be NP-complete, strongly suggesting the intractability of the problem. Thus this paper aims to get excellent approximation algorithms for the problem. First, some practical meanings of the model are discussed, and properties of the problem useful for approximation algorithms are shown. Then approximation algorithms based on some heuristics are proposed, and their performances are analyzed both theoretically and experimentally, showing in result the superiority of one of the proposed algorithms.
- 1988-01-25
論文 | ランダム
- 43)上拍圧迫の脈波伝達時間に及ぼす影響に就て
- 角膜脈波伝達時間に関する研究
- 9) 心搏週期と脈波伝達時間(第8回日本循環器学会東北・北海道地方学会総会)
- 角膜脈波伝達時間測定時に於ける角膜の意義について
- 心搏周期と脈波伝達時間