著者

五島 洋行 増田 士朗

出版者

The Institute of Electronics, Information and Communication Engineers

雑誌

電子情報通信学会論文誌 A (ISSN:09135707)

巻号頁・発行日

vol.J90-A, no.3, pp.190-200, 2007-03-01

---

本論文では,後続ジョブとの資源非競合を考慮したオンラインスケジューリング方法に関する提案を行う.検討対象はMIMO-FIFO型で繰返し処理を行う離散事象システムとする.このようなシステムの挙動は,MPLシステムと呼ばれるmax-plus代数系での線形な方程式で記述できる.従来のMPL表現は,前のジョブとの資源非競合を考慮した定式化を行うもので,途中工程での最早開始時刻が求められる.しかし実用的なスケジューリングを行うには,工程の余裕度の把握や,ジョブの進捗に応じてスケジューリング結果をオンラインで更新する必要があり,各工程の余裕時間やシステムの内部状態の変化まで把握できることが望ましい.最近我々は,単一ジョブの場合についての計算方法を提案したが,後続ジョブとの資源非競合までは考慮されておらず,一度に多くのジョブを処理する場合などには,最適な結果を与えないこともあり得る.そこで本研究では,後続ジョブとの非競合性も考慮した,最遅開始時刻を求めるMPL表現の一般形を導出し,更に,加工開始後にシステムのパラメータに変化が発生したときの,効率的な再スケジューリング方法についても考察する.