Fair Sequence Problem に対する評価指標と解法について

摘要

処理回数の異なる複数種の仕事が一度に与えられた時，各仕事の処理をできるだけ分散させることで，その進行速度を均等に調整することができる．Fair Sequence Problem(以下：FSP) は，このように各仕事の処理を均等に行うための最適なスケジュールを求める問題である．FSP は，製造現場やリアルタイムシステム，ネットワーク環境など，様々な環境下におけるスケジュール問題として現れる．以下では，各仕事をシンボル，その要求処理回数を割当数と呼ぶ．FSP は自動車系企業の混合ライン生産において，複数の製品を安定的(Just-In-Time) に生産するための最適化モデルとして誕生した．代表的なモデルとしてProduct Rate Variation Problem(PRVP) がある．PRVP はMiltenburg ら(1989) が提唱したモデルで，製品の生産率を一定に保つことを目的とした最適化問題である．そこでは，計画期間を有限で直線的な単位時間枠の並びと考える．一方Corominas ら(2007) は，計画期間を無限と考えた循環的なスケジュールを扱うResponse Time Variability Problem(RTVP) を提唱した．RTVP では，実際のシンボルの割当間隔と理想的な（等間隔の）割当間隔とのズレの2 乗和を評価指標としている．以上のように，FSP におけるスケジュールの評価指標においては，「均等性」の解釈に様々な考え方がある．本研究では循環的なスケジュールを対象としたFSP について，評価指標に依らない新たなモデルと解法を提案する．また，提案するモデルに複数の評価指標を当てはめ，検討を行う．