MISC

査読有り
2009年7月4日

4C1 SCHEDULING MULTIPROCESSOR TASKS WITH PROMPT SERVICE CONSTRAINTS ON ALIGNED IDENTICAL PROCESSORS :

Proceedings of International Symposium on Scheduling
  • KARUNO Yoshiyuki
  • ,
  • YAMASHITA Kougaku
  • ,
  • CHIBA Eishi
  • ,
  • NAGAMOCHI Hiroshi

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.

リンク情報
CiNii Articles
http://ci.nii.ac.jp/naid/110008009652
CiNii Books
http://ci.nii.ac.jp/ncid/AA11901544
URL
http://dl.ndl.go.jp/info:ndljp/pid/10355593
ID情報
  • CiNii Articles ID : 110008009652
  • CiNii Books ID : AA11901544

エクスポート
BibTeX RIS