2009年7月4日
4C1 SCHEDULING MULTIPROCESSOR TASKS WITH PROMPT SERVICE CONSTRAINTS ON ALIGNED IDENTICAL PROCESSORS :
Proceedings of International Symposium on Scheduling
- ,
- ,
- ,
- 巻
- 2009
- 号
- 開始ページ
- 203
- 終了ページ
- 208
- 記述言語
- 英語
- 掲載種別
- 出版者・発行元
- 日本機械学会
We consider a combinatorial optimization problem of scheduling n multiprocessor tasks on aligned m identical processors. Each task T_j is characterized by a processing time p_j, the number q_j of processors required, and a ready time r_j. There is a choice for each taks whether the aligned processors serve the task or not. If the aligned processors select a task T_j, they have to start the service of the task promptly after it becomes ready (i.e., they have to start the service exactly at time t=r_j), choosing consecutive q_j processors in the alignment. Any processor can handle at most one task at a time, and no preemption is allowed for the services of tasks (and hence, a selected task T_j is completed exactly at time t=r_j+p_j on the employed consecutive q_j processors). The objective is to find a feasible schedule that maximizes the number of selected tasks. We reduce the NP-complete PARTITION to the multiprocessor task scheduling problem, which implies the NP-hardness for an arbitrary m. We also show that if two processors are available and all tasks have the same processing time, it can be solved in polynomial time by a dynamic programming approach.
- リンク情報
- ID情報
-
- CiNii Articles ID : 110008009652
- CiNii Books ID : AA11901544