3213 即時処理制約を持つ多プロセッサ使用タスクのスケジューリング(OS5-2 効率化,環境負荷低減の技術,OS5 安全・安心・防災・環境負荷低減,オーガナイズド・セッション)

概要

論文の詳細を見る
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 task 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 tune 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 prove that the scheduling problem is NP-hard for an arbitrary m.
一般社団法人日本機械学会の論文
2008-12-09