Scheduling Solver OptSeq
%load_ext autoreload
%autoreload 2

簡易システムの紹介ビデオ

はじめに

スケジューリング(scheduling)とは,稀少資源を諸活動へ(時間軸を考慮して)割り振るための方法に対する理論体系である. スケジューリングの応用は,工場内での生産計画,計算機におけるジョブのコントロール,プロジェクトの遂行手順の決定など,様々である.

ここで考えるのは,以下の一般化資源制約付きスケジューリングモデルであり,ほとんどの実際問題をモデル化できるように設計されている.

  • 複数の作業モードをもつ作業
  • 時刻依存の資源使用可能量上限
  • 作業ごとの納期と重み付き納期遅れ和
  • 作業の後詰め
  • 作業間に定義される一般化された時間制約
  • モードごとに定義された時刻依存の資源使用量
  • モードの並列処理
  • モードの分割処理
  • 状態の考慮

OptSeq(オプトシーク)は,一般化スケジューリング問題に対する最適化ソルバーである. スケジューリング問題は,通常の混合整数最適化ソルバーが苦手とするタイプの問題であり, 実務における複雑な条件が付加されたスケジューリング問題に対しては,専用の解法が必要となる. OptSeqは,スケジューリング問題に特化したメタヒューリスティクス(metaheuristics)を用いることによって, 大規模な問題に対しても短時間で良好な解を探索することができるように設計されている

このモジュールは, すべてPythonで書かれたクラスで構成されている. OptSeqのトライアルバージョンは, http://logopt.com/optseq/ からダウンロード,もしくは github https://github.com/mikiokubo/optseqtrial からクローンできる.

OptSeqモジュールの基本クラス

行うべき仕事(ジョブ,作業,タスク)を作業(activity;活動)とよぶ. スケジューリング問題の目的は作業をどのようにして時間軸上に並べて遂行するかを決めることであるが, ここで対象とする問題では作業を処理するための方法が何通りかあって,そのうち1つを選択することによって 処理するものとする.このような作業の処理方法をモード(mode)とよぶ.

納期や納期遅れのペナルティ(重み)は作業ごとに定めるが, 作業時間や資源の使用量はモードごとに決めることができる.

作業を遂行するためには資源(resource)を必要とする場合がある. 資源の使用可能量は時刻ごとに変化しても良いものとする. また,モードごとに定める資源の使用量も作業開始からの経過時間によって変化しても良いものとする. 通常,資源は作業完了後には再び使用可能になるものと仮定するが, お金や原材料のように一度使用するとなくなってしまうものも考えられる. そのような資源を再生不能資源(nonrenewable resource)とよぶ.

作業間に定義される時間制約(time constraint)は, ある作業(先行作業)の処理が終了するまで,別の作業(後続作業)の処理が開始できないことを表す 先行制約を一般化したものであり, 先行作業の開始(完了)時刻と後続作業の開始(完了)時刻の 間に以下の制約があることを規定する

先行作業の開始(完了)時刻 $+$ 時間ずれ $\leq$ 後続作業の開始(完了)時刻

ここで,時間ずれは任意の整数値であり負の値も許すものとする. この制約によって,作業の同時開始,最早開始時刻,時間枠などの様々な条件を記述することができる.

OptSeqでは,モードを作業時間分の小作業の列と考え,処理の途中中断や並列実行も可能であるとする.その際,中断中の資源使用量や並列作業中の資源使用量も別途定義できるものとする.

また,時刻によって変化させることができる状態(state)が準備され,モード開始の状態の制限やモードによる状態の推移を定義できる.