Scheduling Solver OptSeq

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

はじめに

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

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

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

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

このモジュールは, すべてPythonで書かれたクラスで構成されている. OptSeqのトライアルバージョンは, http://logopt.com/optseq/ からダウンロード,もしくは github https://github.com/scmopt/optseq からクローンできる. また,テクニカルドキュメントは,https://scmopt.github.io/manual/07optseq.html にある.

OptSeqモジュール (optseq.py) の基本クラス

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

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

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

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

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

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

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

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

注意

OptSeqでは作業,モード,資源名を文字列で区別するため重複した名前を付けることはできない. なお,使用できる文字列は, 英文字 (a--z, A--Z), 数字 (0--9), 大括弧 ([ ]), アンダーバー (_), および @ に限定される. また,作業名は source, sink以外, モードは dummy 以外の文字に限定される.

それ以外の文字列はすべてアンダーバー (_)に置き換えられる.

Parameter クラス

OptSeqを制御するためのパラメータを格納したクラス.

Modelクラスの中で使用される.

OptSeqに内在されている最適化ソルバーの動作は, パラメータ(parameter)を変更することによってコントロールできる. モデルインスタンスmodelのパラメータを変更するときは,以下の書式で行う.

model.Params.パラメータ名 = 値

代表的なパラメータとその意味を記す.

  • TimeLimitは最大計算時間 (秒) を設定する. 既定値は600 (秒)
  • RandomSeedは乱数系列の種を設定する.既定値は 1
  • Makespanは最大完了時刻(一番遅く終わる作業の完了時刻)を最小にするときTrueそれ以外のとき (各作業に定義された納期遅れの重みと再生不能資源の逸脱量の重み付き和を最小にするとき)False(既定値)を設定する.
  • Neighborhoodは近傍探索を行う際の近傍数を設定するためのパラメータである. 既定値は20であり,大規模な問題例で求解時間が長い場合には小さい値に設定することが推奨される.
  • Tenure:タブー長の初期値を表すパラメータ.必ず正数を入力する.既定値は1.- Initial: 前回最適化の探索を行った際の最良解を初期値とした探索を行うときTrue,それ以外のときFalseを表すパラメータである. 既定値はFalse 最良解の情報は作業の順序と選択されたモードとしてファイル名 optseq_best_act_data.txtに保管されている. このファイルを書き換えることによって,異なる初期解から探索を行うことも可能である.
  • OutputFlag: 計算の途中結果を出力させるためのフラグである.Trueのとき出力On,Falseのとき出力Off.既定値はFalse
  • ReportInterval: 計算のログを出力するためのインターバル.既定値は1073741823
  • Backtruck: 最大のバックトラック数を表すパラメータ.既定値は1000

class Parameters[source]

Parameters()

OptSeq parameter class to control the operation of OptSeq.

  • param TimeLimit: Limits the total time expended (in seconds). Positive integer. Default=600.

  • param OutputFlag: Controls the output log. Boolean. Default=False (0).

  • param RandomSeed: Sets the random seed number. Integer. Default=1.

  • param ReportInterval: Controls the frequency at which log lines are printed (iteration number). Default=1073741823.

  • param Backtruck: Controls the maximum backtrucks. Default=1000.

  • param MaxIteration: Sets the maximum numbers of iterations. Default=1073741823.

  • param Initial: =True if the user wants to set an initial activity list. Default = False.

      Note that the file name of the activity list must be "optseq_best_act_data.txt."
  • param Tenure: Controls a parameter of tabu search (initial tabu tenure). Default=1.

  • param Neighborhood: Controls a parameter of tabu search (neighborhood size). Default=20.
  • param Makespan: Sets the objective function.

      Makespan is True if the objective is to minimize the makespan (maximum completion time),
      is False otherwise, i.e., to minimize the total weighted tardiness of activities.
      Default=False.

Parametesクラスの使用例

params = Parameters()
params.Makespan = True 
print("Time Limit  = ", params.TimeLimit)
print(params)
Time Limit  =  600
 
 TimeLimit = 600 
 OutputFlag = 0
 RandomSeed = 1 
 ReportInterval = 1073741823 
 Backtruck = 1000
 Initial = False 
 Tenure = 1
 Neighborhood = 20 
 makespan = True 

Mode クラス

optSeqでは, 作業の処理方法をモード(mode)とよぶ. Modeは作業(Activity)の遂行方法を定義するためのクラスである. 作業は少なくとも1つのモードをもち,そのうちのいずれかを選択して処理される.

モードのインスタンスは,モードクラスModeから生成される.

モードインスタンス = Mode(name, duration=0)

コンストラクタの引数の名前と意味は以下の通り.

  • nameはモードの名前を文字列で与える.ただしモードの名前に'dummy'を用いることはできない.
  • durationはモードの作業時間を非負の整数で与える.既定値は $0$.

モードインスタンスは,以下のメソッドをもつ.

  • addResourceはモードを実行するときに必要な資源とその量を指定する.

    モードインスタンス.addResource(resource, requirement={}, rtype = None)

    引数と意味は以下の通り.

    • resourceは追加する資源インスタンスを与える.
    • requirementは資源の必要量を辞書もしくは正数値で与える. 辞書のキーはタプル (開始時刻,終了時刻) であり, 値は資源の使用量を表す正数値である. 正数値で与えた場合には,開始時刻は $0$, 終了時刻は無限大と設定される.

      注:作業時間が $0$ のモードに資源を追加することはできない.その場合には実行不可能解と判断される.

    • rtypeは資源のタイプを表す文字列. None, 'break', 'max' のいずれかから選択する(既定値は通常の資源を表すNone). 'break'を与えた場合には,中断中に使用する資源量を指定する. 'max'を与えた場合には,並列処理中に使用する資源の「最大量」を指定する. 省略可で,その場合には通常の資源使用量を表し,並列処理中には資源使用量の「総和」を使用することになる.

  • addBreakは中断追加メソッドである. モードは単位時間ごとに分解された作業時間分の小作業の列と考えられる. 小作業を途中で中断してしばらく時間をおいてから次の小作業を開始することを中断(break)とよぶ. 中断追加メソッド(addBreak)は,モード実行時における中断の情報を指定する.

    モードインスタンス.addBreak(start=0, finish=0, maxtime='inf')

    引数と意味は以下の通り.

    • startは中断可能な最早時刻を与える.省略可で,既定値は $0$.
    • finishは中断可能時刻の最遅時刻を与える.省略可で,既定値は $0$.
    • maxtimeは最大中断可能時間を与える.省略可で,既定値は無限大('inf').
  • addParallelは並列追加メソッドである. モードは単位時間ごとに分解された作業時間分の小作業の列と考えられる. 資源量に余裕があるなら,同じ時刻に複数の小作業を実行することを並列実行(parallel execution)とよぶ.

    並列追加メソッドaddParallelは,モード実行時における並列実行に関する情報を指定する.

    モードインスタンス.addParallel(start=1, finish=1, maxparallel='inf')

    引数と意味は以下の通り.

    • startは並列実行可能な最小の小作業番号を与える.省略可で,既定値は $1$.
    • finishは並列実行可能な最大の小作業番号を与える.省略可で,既定値は $1$.
    • maxparallelは同時に並列実行可能な最大数を与える.省略可で,既定値は無限大('inf').
  • addStateは状態追加メソッドである. 状態追加メソッド(addState)は,モード実行時における状態の値と実行直後(実行開始が時刻 $t$ のときには,時刻 $t+1$)の 状態の値を定義する.

モードインスタンス.addState(state, fromValue=0, toValue=0)

引数と意味は以下の通り.

  • stateはモードに付随する状態インスタンスを与える.省略不可.
  • fromValueはモード実行時における状態の値を与える.省略可で,既定値は $0$.
  • toValueはモード実行直後における状態の値を与える.省略可で,既定値は $0$.

モードインスタンスは以下の属性をもつ.

  • nameはモード名である.
  • durationはモードの作業時間である.
  • requirementはモードの実行の資源・資源タイプと必要量を表す辞書である. キーは資源名と資源タイプ(None:通常, ’break’:中断中, ’max’:並列作業中の最大資源量)のタプルであり,値は資源必要量を表す辞書である.この辞書のキーはタプル(開始時刻,終了時刻)であり,値は資源の使用量を表す正数値である.

  • breakableは中断の情報を表す辞書である. 辞書のキーはタプル(開始時刻,終了時刻)であり,値は中断可能時間を表す正数値である.

  • parallelは並列作業の情報を表す辞書である.辞書のキーはタプル(開始小作業番号,終了小作業番号)であり, 値は最大並列可能数を表す正数値である.

class Mode[source]

Mode(name='', duration=0)

OptSeq mode class.

- Arguments:
    - name: Name of mode (sub-activity).
            Remark that strings in OptSeq are restricted to a-z, A-Z, 0-9,[],_ and @.
            Also you cannot use "dummy" for the name of a mode.
            - duration(optional): Processing time of mode. Default=0.

- Attbibutes:
    - requirement: Dictionary that maps a pair of resource name and resource type (rtype) to requirement dictionary.
            Requirement dictionary maps intervals (pairs of start time and finish time) to amounts of requirement.
            Resource type (rtype) is None (standard resource type), "break" or "max."
    - breakable: Dictionary that maps breakable intervals to maximum brek times.
    - paralel:  Dictionary that maps parallelable intervals to maximum parallel numbers.
    - state: Dictionary that maps states to the tuples of values.

Modeクラスの使用例

mode = Mode("test mode")
mode.addBreak(0,10,1)
mode.addParallel(1,1,2)
print(mode)
 duration 0  
 break interval 0 10 max 1  
 parallel interval 1 1 max 2 

Activity クラス

成すべき仕事(ジョブ,活動,タスク)を総称して作業(activity)とよぶ.

Acticityは作業を定義するためのクラスである.

作業クラスのインスタンスは,モデルインスタンスmodelの作業追加メソッド(addActivity)の返値として生成される.

作業インスタンス=model.addActivity(name="", duedate="inf", backward= False, weight=1, autoselect=False, quadratic=False)

作業には任意の数のモード(作業の実行方法)を追加することができる. モードの追加は,addModesメソッドで行う.

作業インスタンス.addModes(モードインスタンス1, モードインスタンス2, ... )

作業の情報は,作業インスタンスの属性に保管されている. 作業インスタンスは以下の属性をもつ.

  • nameは作業名である.
  • duedateは作業の納期であり,$0$ 以上の整数もしく無限大'inf'(既定値)を入力する.
  • backwardは作業を後ろ詰め(バックワード)で最適化するときTrue,それ以外の場合(前詰め;フォワード;既定値)Falseを入力する. ただし,後ろ詰めを指定した場合には,状態変数は機能しない.また,納期 (duedate) は無限大 'inf'以外であるか、後続作業に 'inf' 以外の納期が設定されている必要がある. また,前詰めと後ろ詰めの混合も可能であるが,後ろ詰めを指定した作業の後続作業も「自動的に」後ろ詰めに変更される. 後ろ詰めの場合の納期は絶対条件として処理されるので,後続作業の含めて実行不能にならないように設定する必要がある.

  • weightは作業の完了時刻が納期を遅れたときの単位時間あたりのペナルティである.

  • autoselectはモードを自動選択するときTrue,それ以外のときFalseを設定する. 既定値はFalseであり,状態によってモードの開始が制限されている場合には, autoselectをTrueに設定しておくことが推奨される.

注意:作業の定義でautoselectをTrueに指定した場合には,その作業に制約を逸脱したときの重みを無限大とした (すなわち絶対制約とした)再生不能資源を定義することはできない. かならず重みを既定値の無限大'inf'ではない正数値と設定し直す必要がある.

  • quadraticは納期遅れに対する関数を線形ではなく,2次関数にしたいときTrueにする.既定値はFalse.

  • modesは作業に付随するモードインスタンスのリストを保持する.

  • selectedは探索によって発見された解において選択されたモードインスタンスを保持する.
  • startは探索によって発見された解における作業の開始時刻である.
  • completionは探索によって発見された解における作業の終了時刻である.
  • executeは探索によって発見された解における作業の実行を表す辞書である.キーは作業の開始時刻と終了時刻のタプル, 値は並列実行数を表す正数値である.

class Activity[source]

Activity(name='', duedate='inf', backward=False, weight=1, autoselect=False, quadratic=False)

OptSeq activity class.

You can create an activity object by adding an activity to a model (using Model.addActivity)
instead of by using an Activity constructor.

- Arguments:
        - name: Name of activity. Remark that strings in OptSeq are restricted to a-z, A-Z, 0-9,[],_ and @.
                Also you cannot use "source" and "sink" for the name of an activity.
        - duedate(optional): Duedate of activity. A non-nagative integer or string "inf."
        - backward(optional): True if activity is distached backwardly, False (default) otherwise.
        - weight(optional): Panalty of one unit of tardiness. Positive integer.
        - autoselect(optional): True or False flag that indicates the activity selects the mode automatically or not.

Activityクラスの使用例

act = Activity("sample activity", duedate=100, backward=True, weight=10)
act.addModes(mode)
print(act)
activity sample_activity 
 backward duedate 100  
 weight 10  
 test_mode 

Resource クラス

Resourceは資源を定義するためのクラスである.

資源インスタンスは,モデルの資源追加メソッド(addResource)の返値として生成される.

資源インスタンス = model.addResource(name, capacity, rhs=0, direction='<=', weight='inf')

資源インスタンスは,以下のメソッドをもつ.

  • addCapacityは資源に容量を追加するためのメソッドであり,資源の容量を追加する.

    引数と意味は以下の通り.

    • startは資源容量追加の開始時刻(区間の始まり)を与える.
    • finishは資源容量追加の終了時刻(区間の終わり)を与える.
    • amountは追加する容量(資源量上限)を与える.
  • setRhs(rhs)は再生不能資源を表す線形制約の右辺定数をrhsに設定する.引数は整数値(負の値も許すことに注意)とする.

  • setDirection(dir)は再生不能資源を表す制約の種類をdirに設定する. 引数のdirは'<=', '>=', '='のいずれかとする.

  • addTerms(coeffs,vars,values)は,再生不能資源制約の左辺に1つ,もしくは複数の項を追加するメソッドである. 作業がモードで実行されるときに $1$, それ以外のとき $0$ となる変数(値変数)を x[作業,モード]とすると, 追加される項は, $ 係数 \times x[作業,モード] $ と記述される. addTermsメソッドの引数は以下の通り.

    • coeffsは追加する項の係数もしくは係数リスト.係数もしくは係数リストの要素は整数(負の値も許す).
    • varsは追加する項の作業インスタンスもしくは作業インスタンスのリスト. リストの場合には,リストcoeffsと同じ長さをもつ必要がある.
    • valuesは追加する項のモードインスタンスもしくはモードインスタンスのリスト. リストの場合には,リストcoeffsと同じ長さをもつ必要がある.  

資源インスタンスは以下の属性をもつ.

  • nameは資源名である.
  • capacityは資源の容量(使用可能量の上限)を表す辞書である. 辞書のキーはタプル (開始時刻, 終了時刻) であり,値は容量を表す正数値である.
  • rhsは再生不能資源制約の右辺定数である. 既定値は $0$.
  • directionは再生不能資源制約の方向を表す. 既定値は '<='.
  • termsは再生不能資源制約の左辺を表す項のリストである.各項は (係数,作業インスタンス,モードインスタンス) のタプルである.
  • weightは再生不能資源制約を逸脱したときのペナルティの重みを表す. 正数値か絶対制約を表す'inf'を入れる. 既定値は無限大(絶対制約)を表す文字列'inf'である.

class Resource[source]

Resource(name='', capacity=None, rhs=0, direction='<=', weight='inf')

OptSeq resource class.

 - Arguments:
     - name: Name of resource.
             Remark that strings in OptSeq are restricted to a-z, A-Z, 0-9,[],_ and @.
     - capacity (optional): Capacity dictionary of the renewable (standard) resource.
                 Capacity dictionary maps intervals (pairs of start time and finish time) to amounts of capacity.
                 If it is given by a positive integer, it is converted into the dictionay {(0,"inf"):capacity}.
     - rhs (optional): Right-hand-side constant of nonrenewable resource constraint.
     - direction (optional): Rirection (or sense) of nonrenewable resource constraint; "<=" (default) or ">=".
             - weight (optional): Weight of nonrenewable resource to compute the penalty for violating the constraint. Non-negative integer or "inf" (default).

 - Attbibutes:
     - capacity: Capacity dictionary of the renewable (standard) resource.
     - rhs: Right-hand-side constant of nonrenewable resource constraint.
     - direction: Rirection (or sense) of nonrenewable resource constraint; "<=" (default) or "=" or ">=".
     - terms: List of terms in left-hand-side of nonrenewable resource.
                Each term is a tuple of coeffcient,activity and mode.
     - weight: Weight of nonrenewable resource to compute the penalty for violating the constraint. Non-negative integer or "inf" (default).

Resourceクラスの使用例

res = Resource("sample resource", capacity = 1)
res.addCapacity(0,5,10)
print("renewable resource= \n", res)

res2 = Resource("non-renewable", rhs=1, direction="<=", weight=100 )
res2.addTerms(coeffs=1, vars=act, values=mode)
print( res2.printConstraint() )
renewable resource= 
 resource sample_resource  
 interval 0 inf capacity 1  
 interval 0 5 capacity 10 
nonrenewable weight 100 1(sample_activity,test_mode) <=1 

Temporal クラス

Temporalは時間制約を定義するためのクラスである.

時間制約インスタンスは,モデルに含まれる形で生成される. 時間制約インスタンスは,上述したモデルの時間制約追加メソッド(addTemporal)の返値として生成される.

時間制約インスタンス = model.addTemporal(pred, succ, tempType='CS', delay=0, pred_mode=None, succ_mode=None)

時間制約インスタンスは以下の属性をもつ.

  • predは先行作業のインスタンスである.
  • succは後続作業のインスタンスである.
  • typeは時間制約のタイプを表す文字列であり,'SS'(開始,開始),'SC'(開始,完了),'CS'(完了,開始),'CC'(完了,完了)のいずれかを指定する. 既定値は 'CS'
  • delayは時間制約の時間ずれを表す整数値である. 既定値は $0$
  • pred_modeは先行作業の特定のモードであり,そのモードに対して時間制約を追加したいときに使用する.既定値はNoneで,その場合にはモードに依存せず作業に対する時間制約となる.
  • succ_modeは後続作業の特定のモードであり,そのモードに対して時間制約を追加したいときに使用する.既定値はNoneで,その場合にはモードに依存せず作業に対する時間制約となる.

class Temporal[source]

Temporal(pred, succ, tempType='CS', delay=0, pred_mode=None, succ_mode=None)

OptSeq temporal class.

A temporal constraint has the following form::

predecessor's completion (start) time +delay <=
                successor's start (completion) time.

Parameter "delay" can be negative.

- Arguments:
    - pred: Predecessor (an activity object) or string "source."
            Here, "source" specifies a dummy activity that precedes all other activities and starts at time 0.
    - succ: Successor (an activity object) or string "source."
            Here, "source" specifies a dummy activity that precedes all other activities and starts at time 0.
    - tempType (optional): String that differentiates the temporal type.
        "CS" (default)=Completion-Start, "SS"=Start-Start,
        "SC"= Start-Completion, "CC"=Completion-Completion.
    - delay (optional): Time lag between the completion (start) times of two activities.
    - pred_mode (optional): Predecessor's mode
    - succ_mode (optional): Successor's mode

- Attributes:
    - pred: Predecessor (an activity object) or string "source."
    - succ: Successor (an activity object) or string "source."
    - type: String that differentiates the temporal type.
        "CS" (default)=Completion-Start, "SS"=Start-Start,
        "SC"= Start-Completion, "CC"=Completion-Completion.
    - delay: Time lag between the completion (start) times of two activities. default=0.

Temporalクラスの使用例

act2 = Activity("sample activity2")
temp = Temporal(act, act2)
print(temp)
temporal sample_activity sample_activity2  type CS delay 0 

State クラス

Stateは状態を定義するためのクラスである.

状態インスタンスは,モデルに含まれる形で生成される. 状態インスタンスは,モデルの状態追加メソッド(addState)の返値として生成される.

状態インスタンス = model.addState(name)

状態インスタンスは,指定時に状態の値を変化させるためのメソッドaddValueをもつ.

addValue(time, value)は,状態を時刻time(非負整数値)に値value(非負整数値)に変化させることを指定する.

状態インスタンスは以下の属性をもつ.

  • nameは状態の名称を表す文字列である.
  • valueは,時刻をキーとし,その時刻に変化する値を値とした辞書である.

状態によってモードの開始が制限されている場合には, 作業のautoselect属性をTrueに設定しておくことが推奨される. ただし,作業の定義でautoselectをTrueに指定した場合には,その作業に制約を逸脱したときの重みを無限大とした (すなわち絶対制約とした)再生不能資源を定義することはできない. かならず重みを既定値の無限大'inf'ではない正数値と設定し直す必要がある.

class State[source]

State(name='')

OptSeq state class.

You can create a state object by adding a state to a model (using Model.addState) instead of by using a State constructor.

- Arguments:
    - name: Name of state. Remark that strings in OptSeq are restricted to a-z, A-Z, 0-9,[],_ and @.

Stateクラスの使用例

state = State("sample state")
state.addValue(time=5,value=1)
print(state)
state sample_state  time 5 value 1 

Modelクラス

Modelはモデルを定義するためのクラスである.

Modelは引数なしで(もしくは名前を引数として),以下のように記述する.

model = Model()

model = Model('名前')

モデルインスタンスmodelは,以下のメソッドをもつ.

  • addActivityは,モデルに1つの作業を追加する.返値は作業インスタンスである.

作業インスタンス = model.addActivity(name="", duedate="inf", backward = False, weight=1, autoselect=False, quadratic =False)

引数の名前と意味は以下の通り.

  • nameは作業の名前を文字列で与える.ただし作業の名前に'source', 'sink'を用いることはできない.

  • duedateは作業の納期を 0 以上の整数もしくは,無限大を表す文字列'inf'で与える. この引数は省略可で,既定値は'inf'である.

  • backwardは作業を後ろ詰め(バックワード)で最適化するときTrue,それ以外の場合(前詰め;フォワード;既定値)Falseを入力する.
    ただし,後ろ詰めを指定した場合には,状態変数は機能しない.また,納期 (duedate) は無限大 'inf'以外であるか、後続作業に 'inf' 以外の納期が設定されている必要がある. また,前詰めと後ろ詰めの混合も可能であるが,後ろ詰めを指定した作業の後続作業も「自動的に」後ろ詰めに変更される.後ろ詰めの場合の納期は絶対条件として処理されるので,後続作業の含めて実行不能にならないように設定する必要がある.

  • weightは作業の完了時刻が納期を遅れたときの単位時間あたりのペナルティである. 省略可で,既定値は 1.

  • autoselectは作業に含まれるモードを自動選択するか否かを表すフラグである. モードを自動選択するときTrue,それ以外のときFalseを設定する. 既定値はFalse. 状態によってモードの開始が制限されている場合には, autoselectをTrueに設定しておくことが望ましい.

    注意: 作業の定義でautoselectをTrueに指定した場合には,その作業に制約を逸脱したときの重みを無限大とした (すなわち絶対制約とした)再生不能資源を定義することはできない. かならず重みを既定値の無限大'inf'ではない正数値と設定し直す必要がある.

  • quadraticは納期遅れに対する関数を線形ではなく,2次関数にしたいときTrueにする.既定値はFalse.

  • addResourceはモデルに資源を1つ追加する.返値は資源インスタンスである.

    資源インスタンス = model.addResource(name, capacity, rhs=0, direction='<=', weight='inf')

引数の名前と意味は以下の通り.

  • nameは資源の名前を文字列で与える.
  • capacityは資源の容量(使用可能量の上限)を辞書もしくは正数値で与える. 正数値で与えた場合には,開始時刻は $0$,終了時刻は無限大と設定される.
    辞書のキーはタプル (開始時刻, 終了時刻) であり,値は容量を表す正数値である. 開始時刻と終了時刻の組を区間(interval)とよぶ. 離散的な時間を考えた場合には,時刻 $t-1$ から時刻 $t$ の区間を(period) $t$ と定義する. 時刻の初期値を $0$ と仮定すると,期は $1$ から始まる整数値をとる. 区間 (開始時刻, 終了時刻) に対応する期は, 「開始時刻$+1$,開始時刻 $+2$, ..., 終了時刻」 となる.

  • rhsは再生不能資源制約の右辺定数を与える.省略可で,既定値は $0$.

  • directionは再生不能資源制約の種類(制約が等式か不等式か,不等式の場合には方向)を示す文字列を与える. 文字列は'<=', '>=', '=' のいずれかとする. 省略可であり,既定値は '<='である.
  • weightは 再生不能資源制約を逸脱したときのペナルティ計算用の重みを与える. 正数値もしくは無限大を表す文字列'inf'を入力する.省略可で,既定値は'inf'.
  • addTemporalはモデルに時間制約を1つ追加する. 返値は時間制約インスタンスである.

時間制約インスタンス = model.addTemporal(pred, succ, tempType='CS', delay=0, pred_mode=None, succ_mode=None)

時間制約は,先行作業と後続作業の開始(もしくは完了)時刻間の関係を表し, 以下のように記述される. $$ 先行作業(もしくはモード)の開始(完了)時刻 + 時間ずれ \leq 後続作業(もしくはモード)の開始(完了)時刻 $$

ここで時間ずれ(delay)は時間の差を表す整数値である. 先行(後続)作業の開始時刻か完了時刻のいずれを対象とするかは,時間制約のタイプで指定する. タイプは,開始時刻(start time)のとき文字列'S', 完了時刻(completion time)のとき文字列'C'で表し, 先行作業と後続作業のタイプを2つつなげて 'SS', 'SC', 'CS', 'CC'のいずれかから選択する.

引数の名前と意味は以下の通り.

  • predは先行作業(predecessor)のインスタンスもしくは文字列'source'を与える. 文字列'source'は,すべての作業に先行する開始時刻 $0$ のダミー作業を定義するときに用いる.
  • succは後続作業(successor)のインスタンスもしくは文字列'sink'を与える. 文字列'sink'は,すべての作業に後続するダミー作業を定義するときに用いる.
  • tempTypeは時間制約のタイプを与える. 'SS', 'SC', 'CS', 'CC'のいずれかから選択し,省略した場合の既定値は'CS' (先行作業の完了時刻と後続作業の開始時刻)である.
  • delayは先行作業と後続作業の間の時間ずれであり,整数値(負の値も許すことに注意)で与える. 既定値は $0$ である.

  • pred_modeは先行作業の特定のモードであり,そのモードに対して時間制約を追加したいときに使用する.既定値はNoneで,その場合にはモードに依存せず作業に対する時間制約となる.

  • succ_modeは後続作業の特定のモードであり,そのモードに対して時間制約を追加したいときに使用する.既定値はNoneで,その場合にはモードに依存せず作業に対する時間制約となる.
  • addStateはモデルに状態を追加する.引数は状態の名称を表す文字列nameであり, 返値は状態インスタンスである.

    状態インスタンス = model.addState(name)

  • optimizeはモデルの最適化を行う.返値はなし. 最適化を行った結果は,作業,モード,資源,時間制約インスタンスの属性に保管される.

 引数

 - cloud:複数人が同時実行する可能性があるときTrue(既定値はFalse); Trueのとき,ソルバー呼び出し時に生成されるファイルにタイムスタンプを追加し,計算終了後にファイルを消去する.

  • writeは最適化されたスケジュールを簡易Ganttチャート(Gantt chart;Henry Ganttによって $100$年くらい前に提案されたスケジューリングの表記図式なので,Ganttの図式という名前がついている. 実は,最初の発案者はポーランド人のKarol Adamieckiで1896年まで遡る.) としてテキストファイルに出力する. 引数はファイル名(filename)であり,その既定値はoptseq.txtである.ここで出力されるGanttチャートは,作業別に選択されたモードや開始・終了時刻を示したものであり, 資源に対しては使用量と容量が示される.

  • writeExcelは最適化されたスケジュールを簡易Ganttチャートとしてカンマ区切りのテキスト(csv)ファイルに出力する.引数はファイル名(filename)とスケールを表す正整数(scale)である.ファイル名の既定値はoptseq.csvである.スケールは,時間軸をscale分の $1$ に縮めて出力するためのパラメータであり,Excelの列数が上限値をもつために導入された.その既定値は $1$ である.なお,Excel用のGanttチャートでは,資源の残り容量のみを表示する.

モデルインスタンスは,モデルの情報を文字列として返すことができる. たとえば,モデルインスタンスmodelの情報は,

print(model)

で得ることができる.作業,モード,資源,時間制約,状態のインスタンスについても同様であり, print関数で情報を出力することができる.

モデルの情報は,インスタンスの属性に保管されている.インスタンスの属性は「インスタンス.属性名」でアクセスできる.

  • actはモデルに含まれる作業インスタンスのリスト.
  • resはモデルに含まれる資源インスタンスのリスト.
  • activitiesはモデルに含まれる作業名をキー,作業インスタンスを値とした辞書である.
  • modesはモデルに含まれるモード名をキー,モードインスタンスを値とした辞書である.
  • resourcesはモデルに含まれる資源名をキー,資源インスタンスを値とした辞書である.
  • temporalsはモデルに含まれる時間制約の先行作業名と後続作業名のタプルをキー,時間制約インスタンスを値とした辞書である.
  • Paramsは最適化をコントロールするためのパラメータインスタンスである.
  • Statusは最適化の状態を表す整数である.状態の種類と意味を,以下の表に示す.

最適化の状態を表す整数と意味

状態の定数 説明
$-1$ 実行不能(時間制約を満たす解が存在しない場合など)
$0$ 最適化成功
$7$ 実行ファイルoptseq.exeのよび出しに失敗した.
$10$ モデルの入力は完了しているが,まだ最適化されていない.

class Model[source]

Model(name='')

OptSeq model class.

- Attributes:
    - activities: Dictionary that maps activity names to activity objects in the model.
    - modes: Dictionary that maps mode names to mode objects in the model.
    - resources:  Dictionary that maps resource names to resource objects in the model.
    - temporals: Dictionary that maps pairs of activity names to temporal constraint objects in the model.
    - Params: Object including all the parameters of the model.

    - act: List of all the activity objects in the model.
    - res: List of all the resource objects in the model.
    - tempo: List of all the tamporal constraint objects in the model.

Modelクラスの使用例

model = Model()
duration = {1: 13, 2: 25, 3: 15, 4: 27, 5: 22}
act = {}
mode = {}
res=model.addResource("worker",capacity=1)
for i in duration:
    act[i] = model.addActivity(f"Act[{i}]")
    mode[i] = Mode(f"Mode[{i}]", duration[i])
    mode[i].addResource(res,requirement=1)
    act[i].addModes(mode[i])
        
# temporal constraints
model.addTemporal(act[1], act[2], delay = 20)
model.addTemporal(act[1], act[3], delay = 20)
model.addTemporal(act[2], act[4], delay = 10)
model.addTemporal(act[2], act[5], delay = 8)
model.addTemporal(act[3], act[4], delay =10)
model.addTemporal("source", act[1], delay =5)
model.addTemporal(act[4], "sink", delay =5)

model.Params.TimeLimit = 1
model.Params.Makespan = True
model.optimize(cloud=False)
 ================ Now solving the problem ================ 


Solutions:
    source   ---     0     0
      sink   ---   132   132
    Act[1]   ---     5    18
    Act[2]   ---    38    63
    Act[3]   ---    63    78
    Act[4]   ---   100   127
    Act[5]   ---    78   100
print(model)
Model:
number of activities= 5
number of resources= 1

Resource Information
resource worker  
 interval 0 inf capacity 1 

Mode Information
Mode[1]
 duration 13  
 worker interval 0 inf requirement 1 
Mode[2]
 duration 25  
 worker interval 0 inf requirement 1 
Mode[3]
 duration 15  
 worker interval 0 inf requirement 1 
Mode[4]
 duration 27  
 worker interval 0 inf requirement 1 
Mode[5]
 duration 22  
 worker interval 0 inf requirement 1 

Activity Information
activity Act[1] 
 Mode[1] 
activity Act[2] 
 Mode[2] 
activity Act[3] 
 Mode[3] 
activity Act[4] 
 Mode[4] 
activity Act[5] 
 Mode[5] 

Temporal Constraint Information
temporal Act[1] Act[2]  type CS delay 20 
temporal Act[1] Act[3]  type CS delay 20 
temporal Act[2] Act[4]  type CS delay 10 
temporal Act[2] Act[5]  type CS delay 8 
temporal Act[3] Act[4]  type CS delay 10 
temporal source Act[1]  type CS delay 5 
temporal Act[4] sink  type CS delay 5 

Graphvizによる可視化関数 visualize

visualize[source]

visualize(model, rankdir='LR', size='10')

最適化の描画関数 plot_optseq

OptSeqはメタヒューリスティクスによって解の探索を行う. 一般には,解の良さと計算時間はトレードオフ関係がある.つまり,計算時間をかければかけるほど良い解を得られる可能性が高まる. どの程度の計算時間をかければ良いかは,最適化したい問題例(問題に数値を入れたもの)による. plot_optseqは,横軸に計算時間,縦軸に目的関数値をプロットする関数であり,最適化を行ったあとに呼び出す. 得られるPlotlyの図は,どのくらいの計算時間をかければ良いかをユーザーが決めるための目安を与える.

たとえば以下の例の図から,10秒程度の計算時間で良好な解を得ることができるが,念入りにさらに良い解を探索したい場合には30秒以上の計算時間が必要なことが分かる.

plot_optseq[source]

plot_optseq(file_name:str='optseq_output.txt')

fig = plot_optseq()
plotly.offline.plot(fig);

ガントチャートを生成する関数 make_gannt

与えられたモデルに格納されているスケジュールを、ガントチャートで可視化する。

引数:

  • model : モデルオブジェクト
  • start : 開始時刻を表す(pandasの日付時刻型に変換可能な文字列)文字列. 既定値は "2019/1/1".
  • period : 時間の単位を表す文字列. "days"(日), "seconds"(秒), "minutes"(分), "hours(時間)の何れか. 既定値は "days"

返値:

  • fig : ガントチャートの図オブジェクト

make_gannt[source]

make_gannt(model, start='2019/1/1', period='days')

ガントチャートを生成する関数

make_gannt関数の使用例

fig = make_gannt(model)
#fig.show()
plotly.offline.plot(fig);

Notionのガントチャート用のデータフレームを生成する関数 make_gannt_for_notion

Notion のtimelineを用いてガントチャートを表示する.

使用法:

  • 生成したデータフレームをcsvファイルとして保存
  • https://www.notion.so/ でimportしてからタイムラインページを生成して表示
  • もしくは既存のタイムラインページに merge with csv でインポート

引数:

  • model : モデルオブジェクト
  • start : 開始時刻を表す(pandasの日付時刻型に変換可能な文字列)文字列.形式はpandasのto_datetimeに認識される文字列で,例えば"2020/1/1 00:00:00".(既定値).
  • period : 時間の単位を表す文字列. "days"(日), "seconds"(秒), "minutes"(分), "hours(時間)の何れか. 既定値は "days"

返値:

  • df : Notionのタイムライン形式のデータフレーム

make_gannt_for_notion[source]

make_gannt_for_notion(model, start='2020/1/1 00:00:00', period='days')

notionのガントチャートを生成する関数

make_gannt_for_notion関数の使用例

start = dt.datetime(2020,1,1,8,20)
start = start.strftime('%Y-%m-%d %H:%M:%S')

df = make_gannt_for_notion(model, start)
#df.to_csv("gannt.csv", index=False)

資源グラフを生成する関数 make_resource_graph

引数:

  • model: OptSeqモデルファイル
  • scale: 横軸をscale分の1にする.(たとえば分単位を時間単位にする.)既定値は $1$.

make_resource_graph[source]

make_resource_graph(model, scale=1)

資源の使用量と残差(容量-使用量)を図示する関数

make_resource_graph関数の使用例

#model.optimize()
fig = make_resource_graph(model, scale=60)
plotly.offline.plot(fig);

例題

以下の例題を動かすためには,最初に以下を追加する必要がある.

from optseq import *
import plotly

また,optseqでは図を描画するために plotly を利用しているので, numpy, pandas, plotly の各パッケージをインストールしておく必要がある.

例題1 PERT

あなたは航空機会社のコンサルタントだ. あなたの仕事は,着陸した航空機をなるべく早く離陸させるためのスケジュールをたてることだ. 航空機は,再び離陸する前に幾つかの作業をこなさなければならない. まず,乗客と荷物を降ろし,次に機内の掃除をし,最後に新しい乗客を搭乗させ,新しい荷物を積み込む. 当然のことであるが, 乗客を降ろす前に掃除はできず,掃除をした後でないと新しい乗客を入れることはできず, 荷物をすべて降ろし終わった後でないと,新しい荷物は積み込むことができない. また,この航空機会社では, 乗客用のゲートの都合で,荷物を降ろし終わった後でないと新しい乗客を搭乗させることができないのだ. 作業時間は,乗客降ろし $13$ 分,荷物降ろし $25$ 分,機内清掃 $15$ 分,新しい乗客の搭乗 $27$ 分, 新しい荷物の積み込み $22$ 分とする. さて,最短で何分で離陸できるだろうか?

これは,PERT(Program Evaluation and Review Technique)とよばれるスケジューリング理論の始祖とも言える古典的なモデルである. ちなみに,PERTは,第2次世界大戦中における米国海軍のポラリス潜水艦に搭載するミサイルの設計・開発時間の短縮に貢献したことで有名になり,その後オペレーションズ・リサーチの技法の代表格となった.

この問題は,資源制約なしのスケジューリングモデルになる. 使うのは作業と時間制約だけである.

まず,モデルのインスタンスmodelを生成する. 作業名は1から6の整数で表し,キーを作業名,値を作業時間とした辞書durationを準備する.

model = Model()
duration = {1: 13, 2: 25, 3: 15, 4: 27, 5: 22}

作業には必ず1つ以上のモード(作業の仕方)を定義する必要があるので,各作業に対して1つのモードを定義し,それを作業に追加する. 作業とモードはそれぞれ辞書actmode に保管するものとする. 作業はモデルインスタンスmodeladdActivityメソッドで追加し,モードはモードクラスModeから生成してから作業インスタンスにaddModesメソッドで追加する.

act = {}
mode = {}
for i in duration:
    act[i] = model.addActivity(f"Act[{i}]")
    mode[i] = Mode(f"Mode[{i}]", duration[i])
    act[i].addModes(mode[i])

時間制約はmodeladdTemporalメソッドで定義する.引数は先行する作業のインスタンスと後続する作業のインスタンスである.

model.addTemporal(act[1], act[3])
model.addTemporal(act[2], act[4])
model.addTemporal(act[2], act[5])
model.addTemporal(act[3], act[4])

モデルが構築できたら,modelのパラメータParamsで制限時間TimeLimitを1(秒)に設定し,最大完了時刻(メイクスパン)を最小化することを表すMakespanをTrueに設定する. 最後にmodeloptimizeメソッドで最適化を行う.

model.Params.TimeLimit = 1
model.Params.Makespan = True
model.optimize()

プログラム全体を以下に示す.

ex1[source]

ex1()

Example 1 PERT file name: Example1.py Copyright Log Opt Co., Ltd.

Consider a 5-activity problem with precedence constraints between the activities. Such a problem is called PERT (Program Evaluation and Review Technique). The processing times (durations) of the activities are kept in the dictionary duration ={1:13, 2:25, 3:15, 4:27, 5:22 }. Precedence constraints are given by: Activity 1 -> Activity 3; Activity 2 -> Activity 4; Activity 3 -> Activity 4; and Activity 3 -> Activity 5. The objective is to find the maximum completion time (makespan) for all 5 activities.

model = Model()
duration = {1: 13, 2: 25, 3: 15, 4: 27, 5: 22}
act = {}
mode = {}
for i in duration:
    act[i] = model.addActivity(f"Act[{i}]")
    mode[i] = Mode(f"Mode[{i}]", duration[i])
    act[i].addModes(mode[i])

model.addTemporal(act[1], act[3])
model.addTemporal(act[2], act[4])
model.addTemporal(act[2], act[5])
model.addTemporal(act[3], act[4])

model.Params.TimeLimit = 1
model.Params.Makespan = True
model.optimize()
 ================ Now solving the problem ================ 


Solutions:
    source   ---     0     0
      sink   ---    55    55
    Act[1]   ---     0    13
    Act[2]   ---     0    25
    Act[3]   ---    13    28
    Act[4]   ---    28    55
    Act[5]   ---    25    47
visualize(model)
G cluster[Act[1]] cluster[Act[2]] cluster[Act[3]] cluster[Act[4]] cluster[Act[5]] Act[1] Act[1] Mode[1] Mode[1] Act[1]->Mode[1] Act[3] Act[3] Act[1]->Act[3] Act[2] Act[2] Mode[2] Mode[2] Act[2]->Mode[2] Act[4] Act[4] Act[2]->Act[4] Act[5] Act[5] Act[2]->Act[5] Mode[3] Mode[3] Act[3]->Mode[3] Act[3]->Act[4] Mode[4] Mode[4] Act[4]->Mode[4] Mode[5] Mode[5] Act[5]->Mode[5]

最短で$55$分で離陸できることが分かる. 結果をガントチャートに示す.

例題2 資源制約付きPERT

あなたは航空機会社のコンサルタントだ. リストラのため作業員の大幅な削減を迫られたあなたは, 例題1と同じ問題を1人の作業員で行うためのスケジュールを作成しなければならなくなった. 作業時間や時間制約は同じであるが,各々の作業は作業員を1人占有する(すなわち2つの作業を同時にできない) ものとする. どのような順序で作業を行えば,最短で離陸できるだろうか?

この問題は資源制約付きプロジェクトスケジューリング問題とよばれ, $NP$-困難であるが, OptSeqを用いれば容易に解くことができる.

資源制約はmodelインスタンスのaddResourceメソッドで定義する.引数は資源名と容量(資源量上限である).ここでは,1人の作業員を資源制約として定義する.

res=model.addResource("worker",capacity=1)

作業はモードごとに使用する資源を定義できる.したがって,モードのインスタンスに対してaddResourceメソッドで資源を追加する. 引数は資源オブジェクトと使用量requirementであり,ここでは1と指定する.

for i in duration:
    act[i]=model.addActivity(f"Act[{i}]")
    mode[i]=Mode(f"Mode[{i}]",duration[i])
    mode[i].addResource(res,requirement=1)
    act[i].addModes(mode[i])

また, modelのパラメータParamsOutputFlagをTrueに設定することによって,最適化の詳細ログを出力する.

コード全体は以下のようになる.

ex2[source]

ex2()

Example 2 PERT with resource constraint file name: Example2.py Copyright Log Opt Co., Ltd.

Consider a 5-activity problem with precedence constraints between the activities. The processing times (durations) of the activities are kept in the dictionary duration ={1:13, 2:25, 3:15, 4:27, 5:22 }. Precedence constraints are given by: Activity 1 -> Activity 3; Activity 2 -> Activity 4; Activity 3 -> Activity 4; and Activity 3 -> Activity 5. Each activity requires one unit of worker resource whose capacity (maximum amount of availability for each time period) is 1. The objective is to find the maximum completion time (makespan) for all 5 activities

model=Model()
duration ={1:13, 2:25, 3:15, 4:27, 5:22 }
res=model.addResource("worker",capacity=1)

act={}
mode={}
for i in duration:
    act[i]=model.addActivity(f"Act[{i}]")
    mode[i]=Mode(f"Mode[{i}]",duration[i])
    mode[i].addResource(res,requirement=1)
    act[i].addModes(mode[i])

#temporal (precedense) constraints
model.addTemporal(act[1],act[3])
model.addTemporal(act[2],act[4])
model.addTemporal(act[2],act[5])
model.addTemporal(act[3],act[4])

model.Params.TimeLimit=1
model.Params.OutputFlag=True
model.Params.Makespan=True
model.optimize()
 ================ Now solving the problem ================ 


output:
# reading data ... done: 0.00(s)
# random seed: 1
# tabu tenure: 1
# cpu time limit: 1.00(s)
# iteration limit: 1073741823
# computing all-pairs longest paths and strongly connected components ... done
#scc 7
objective value = 102 (cpu time = 0.00(s), iteration = 0)
0: 0.00(s): 102/102

--- best solution ---
source,---, 0 0
sink,---, 102 102
Act[1],---, 47 47--60 60
Act[2],---, 0 0--25 25
Act[3],---, 60 60--75 75
Act[4],---, 75 75--102 102
Act[5],---, 25 25--47 47
--- tardy activity ---
sink: 102
--- resource residuals ---
worker: [0,102] 0 

--- best activity list ---
source ---
Act[2] ---
Act[5] ---
Act[1] ---
Act[3] ---
Act[4] ---
sink ---

objective value = 102
cpu time = 0.00/1.00(s)
iteration = 1/60175


Solutions:
    source   ---     0     0
      sink   ---   102   102
    Act[1]   ---    47    60
    Act[2]   ---     0    25
    Act[3]   ---    60    75
    Act[4]   ---    75   102
    Act[5]   ---    25    47
visualize(model)
G cluster[Act[1]] cluster[Act[2]] cluster[Act[3]] cluster[Act[4]] cluster[Act[5]] worker worker Mode[1] Mode[1] Mode[1]->worker Act[1] Act[1] Act[1]->Mode[1] Act[3] Act[3] Act[1]->Act[3] Mode[2] Mode[2] Mode[2]->worker Act[2] Act[2] Act[2]->Mode[2] Act[4] Act[4] Act[2]->Act[4] Act[5] Act[5] Act[2]->Act[5] Mode[3] Mode[3] Mode[3]->worker Act[3]->Mode[3] Act[3]->Act[4] Mode[4] Mode[4] Mode[4]->worker Act[4]->Mode[4] Mode[5] Mode[5] Mode[5]->worker Act[5]->Mode[5]
今度は$102$分かかることが分かる 結果をガントチャートに示す

例題3 並列ショップスケジューリング

あなたはF1のピットクルーだ. F1レースにとってピットインの時間は貴重であり, ピットインしたレーシングカーに適切な作業を迅速に行い, なるべく早くレースに戻してやることが,あなたの使命である.

  • 作業1: 給油準備 (3秒)
  • 作業2: 飲料水の取り替え  (2秒)
  • 作業3: フロントガラス拭き (2秒)
  • 作業4: ジャッキで車を持ち上げ (2秒)
  • 作業5: タイヤ (前輪左側) 交換 (4秒)
  • 作業6: タイヤ (前輪右側) 交換 (4秒)
  • 作業7: タイヤ (後輪左側) 交換 (4秒)
  • 作業8: タイヤ (後輪右側) 交換 (4秒)
  • 作業9: 給油 (11秒)
  • 作業10: ジャッキ降ろし (2秒)

各作業には,作業時間のほかに, この作業が終わらないと次の作業ができないといったような時間制約がある. 作業時間と時間制約は,以下の図のようになっている.

いま,あなたを含めて3人のピットクルーがいて, これらの作業を手分けして行うものとする. 作業は途中で中断できないものとすると, なるべく早く最後の作業を完了させるには, 誰がどの作業をどういう順番で行えばよいのだろうか?

3人の作業員に区別がない場合には,容量(資源上限)が $3$ の資源workerを定義すれば良い.

res=model.addResource("worker",capacity=3)

後の手順は例題2と同じである. 以下にプログラムを示す.

ex3[source]

ex3()

Example 3 Parallel Shop Problem file name: Example3.py Copyright Log Opt Co., Ltd.

Consider a 10-activity problem in which each activity is processed on three identical parallel machines. The processing times (durations) of the activities are kept in the dictionary duration ={1:3, 2:2, 3:2, 4:2, 5:4, 6:4, 7:4, 8:4, 9:11, 10:2 }. Precedence constraints are given by: Activity 1 -> Activity 9; Activities 5,6,7,8 are processed after Activity 4 and before Activity 10. The objective is to find the maximum completion time (makespan).

model=Model()
duration ={1:3, 2:2, 3:2, 4:2, 5:4, 6:4, 7:4, 8:4, 9:11, 10:2 }
res=model.addResource("worker",capacity=3)
act={}
mode={}
for i in duration:
    act[i]=model.addActivity(f"Act[{i}]")
    mode[i]=Mode(f"Mode[{i}]", duration[i])
    mode[i].addResource(res,1)
    act[i].addModes(mode[i])

model.addTemporal(act[1],act[9])
for i in range(5,9):
    model.addTemporal(act[4],act[i])
    model.addTemporal(act[i],act[10])

model.Params.TimeLimit=1
model.Params.Makespan=True
model.optimize()
 ================ Now solving the problem ================ 


Solutions:
    source   ---     0     0
      sink   ---    14    14
    Act[1]   ---     0     3
    Act[2]   ---     6     8
    Act[3]   ---     0     2
    Act[4]   ---     0     2
    Act[5]   ---     2     6
    Act[6]   ---     6    10
    Act[7]   ---     2     6
    Act[8]   ---     8    12
    Act[9]   ---     3    14
   Act[10]   ---    12    14
visualize(model)
G cluster[Act[1]] cluster[Act[2]] cluster[Act[3]] cluster[Act[4]] cluster[Act[5]] cluster[Act[6]] cluster[Act[7]] cluster[Act[8]] cluster[Act[9]] cluster[Act[10]] worker worker Mode[1] Mode[1] Mode[1]->worker Act[1] Act[1] Act[1]->Mode[1] Act[9] Act[9] Act[1]->Act[9] Mode[2] Mode[2] Mode[2]->worker Act[2] Act[2] Act[2]->Mode[2] Mode[3] Mode[3] Mode[3]->worker Act[3] Act[3] Act[3]->Mode[3] Mode[4] Mode[4] Mode[4]->worker Act[4] Act[4] Act[4]->Mode[4] Act[5] Act[5] Act[4]->Act[5] Act[6] Act[6] Act[4]->Act[6] Act[7] Act[7] Act[4]->Act[7] Act[8] Act[8] Act[4]->Act[8] Mode[5] Mode[5] Mode[5]->worker Act[5]->Mode[5] Act[10] Act[10] Act[5]->Act[10] Mode[6] Mode[6] Mode[6]->worker Act[6]->Mode[6] Act[6]->Act[10] Mode[7] Mode[7] Mode[7]->worker Act[7]->Mode[7] Act[7]->Act[10] Mode[8] Mode[8] Mode[8]->worker Act[8]->Mode[8] Act[8]->Act[10] Mode[9] Mode[9] Mode[9]->worker Act[9]->Mode[9] Mode[10] Mode[10] Mode[10]->worker Act[10]->Mode[10]

最短で$14$分で作業が完了することが分かる. 以下にガントチャートと資源チャートを示す.

例題4 複数モードの利用

上と同じ例題において、作業1が以下の3つのモード(作業方法)で処理できるものとする。

  1. 1人の作業員で行い3秒かかる。
  2. 2人の作業員で行い2秒かかる。
  3. 3人の作業員で行い1秒かかる。

さて、どのモードを採用し、どのようなスケジュールで作業を行えば、最短で終了するだろうか?

作業1に対して3つのモードを準備して,モードごとに異なる作業時間durationと資源の使用量requirementを設定すれば良い.

if i==1:
    mode[1,1]=Mode("Mode[1_1]",duration=3)
    mode[1,1].addResource(res,requirement=1)
    mode[1,2]=Mode("Mode[1_2]",duration=2)
    mode[1,2].addResource(res,requirement=2)
    mode[1,3]=Mode("Mode[1_3]",duration=1)
    mode[1,3].addResource(res,requirement=3)
    act[i].addModes(mode[1,1],mode[1,2],mode[1,3])

プログラム全体は以下のように書ける.

ex4[source]

ex4()

Example 4 Parallel Shop Problem using Modes file name: Example4.py Copyright Log Opt Co., Ltd.

Consider a 10-activity problem in which each activity is processed on three identical parallel machines. The processing times (durations) of the activities are kept in the dictionary duration ={1:3, 2:2, 3:2, 4:2, 5:4, 6:4, 7:4, 8:4, 9:11, 10:2 }. Precedence constraints are given by: Activity 1 -> Activity 9; Activities 5,6,7,8 are processed after Activity 4 and before Activity 10. Activity 1 can be processed in one of the following three modes: Mode 1 with duration 3 that requires 1 unit of worker resource, Mode 2 with duration 2 that requires 2 units of worker resource, and Mode 3 with duration 1 that requires 3 units of worker resource. The objective is to find the maximum completion time (makespan).

model=Model()
duration ={1:3, 2:2, 3:2, 4:2, 5:4, 6:4, 7:4, 8:4, 9:11, 10:2 }
res=model.addResource("worker", capacity=3)
act={}
mode={}

for i in duration:
    act[i]=model.addActivity(f"Act[{i}]")
    if i==1:
        mode[1,1]=Mode("Mode[1_1]",duration=3)
        mode[1,1].addResource(res,requirement=1)
        mode[1,2]=Mode("Mode[1_2]",duration=2)
        mode[1,2].addResource(res,requirement=2)
        mode[1,3]=Mode("Mode[1_3]",duration=1)
        mode[1,3].addResource(res,requirement=3)
        act[i].addModes(mode[1,1],mode[1,2],mode[1,3])
    else:
        mode[i]=Mode(f"Mode[{i}]", duration[i])
        mode[i].addResource(res,1)
        act[i].addModes(mode[i])

model.addTemporal(act[1],act[9])
for i in range(5,9):
    model.addTemporal(act[4],act[i])
    model.addTemporal(act[i],act[10])

model.Params.TimeLimit=1
model.Params.Makespan=True
model.optimize()
 ================ Now solving the problem ================ 


Solutions:
    source   ---     0     0
      sink   ---    13    13
    Act[1] Mode[1_3]     0     1
    Act[2]   ---    11    13
    Act[3]   ---     1     3
    Act[4]   ---     1     3
    Act[5]   ---     3     7
    Act[6]   ---     7    11
    Act[7]   ---     7    11
    Act[8]   ---     3     7
    Act[9]   ---     1    12
   Act[10]   ---    11    13
visualize(model)
G cluster[Act[1]] cluster[Act[2]] cluster[Act[3]] cluster[Act[4]] cluster[Act[5]] cluster[Act[6]] cluster[Act[7]] cluster[Act[8]] cluster[Act[9]] cluster[Act[10]] worker worker Mode[1_1] Mode[1_1] Mode[1_1]->worker Mode[1_2] Mode[1_2] Mode[1_2]->worker Mode[1_3] Mode[1_3] Mode[1_3]->worker Act[1] Act[1] Act[1]->Mode[1_1] Act[1]->Mode[1_2] Act[1]->Mode[1_3] Act[9] Act[9] Act[1]->Act[9] Mode[2] Mode[2] Mode[2]->worker Act[2] Act[2] Act[2]->Mode[2] Mode[3] Mode[3] Mode[3]->worker Act[3] Act[3] Act[3]->Mode[3] Mode[4] Mode[4] Mode[4]->worker Act[4] Act[4] Act[4]->Mode[4] Act[5] Act[5] Act[4]->Act[5] Act[6] Act[6] Act[4]->Act[6] Act[7] Act[7] Act[4]->Act[7] Act[8] Act[8] Act[4]->Act[8] Mode[5] Mode[5] Mode[5]->worker Act[5]->Mode[5] Act[10] Act[10] Act[5]->Act[10] Mode[6] Mode[6] Mode[6]->worker Act[6]->Mode[6] Act[6]->Act[10] Mode[7] Mode[7] Mode[7]->worker Act[7]->Mode[7] Act[7]->Act[10] Mode[8] Mode[8] Mode[8]->worker Act[8]->Mode[8] Act[8]->Act[10] Mode[9] Mode[9] Mode[9]->worker Act[9]->Mode[9] Mode[10] Mode[10] Mode[10]->worker Act[10]->Mode[10]

作業1をモード3(3人同時で1秒)で実行することにより,$13$分に完了時刻を短縮できることが分かる.

例題5 一般化資源制約付きスケジューリング

あなたは1階建てのお家を造ろうとしている大工さんだ. あなたの仕事は,なるべく早くお家を完成させることだ. お家を造るためには,幾つかの作業をこなさなければならない. まず,土台を造り,1階の壁を組み立て,屋根を取り付け,さらに1階の内装をしなければならない. ただし,土台を造る終える前に1階の建設は開始できず,内装工事も開始できない. また,1階の壁を作り終える前に屋根の取り付けは開始できない.

各作業とそれを行うのに必要な時間(単位は日)は,以下のようになっている.

  • 土台: 2人の作業員で1日
  • 1階の壁: 最初の1日目は2人,その後の2日間は1人で,合計3日
  • 内装: 1人の作業員で2日
  • 屋根: 最初の1日は1人,次の1日は2人の作業員が必要で,合計2日

いま,作業をする人は,あなたをあわせて2人いるが,相棒は作業開始3日目に休暇をとっている. さて,最短で何日でお家を造ることができるだろうか?

この例題では,資源の容量(資源量上限)と作業の資源使用量が一定でない(日によって変わる).

最初に作業員資源インスタンスworkercapacity引数を省略して生成する. 次に, 資源インスタンスresaddCapacityメソッドで開始時刻,終了時刻,容量を入力する.

res=model.addResource("worker")
res.addCapacity(0,2,2)
res.addCapacity(2,3,1)
res.addCapacity(3,"inf",2)

これで時刻ごとに異なる資源の容量が定義できた. 実は資源容量は内部的には,辞書で保管されている. 資源インスタンスrescapacity属性を出力すると,以下のようになる.

print(res.capacity)
> {(0, 2):2, (2, 3): 1, (3, 'inf'): 2}

したがって,資源インスタンスを生成する際にcapacity引数で上の辞書を与えても同じである.

作業モードごとの資源の必要量を入力するには,辞書を用いる. 作業ごとに必要量を表す辞書を準備し,モードインスタンスのaddResourceメソッドのrequirement引数に準備した辞書を渡すことによって, 時刻によって異なる資源必要量が定義できる.

req={}
req[1]={(0,1):2}
req[2]={(0,1):2, (1,3):1}
req[3]={(0,2):1}
req[4]={(0,1):1, (1,2):2 }

act={}
mode={}
for i in duration:
    act[i]=model.addActivity(f"Act[{i}]")
    mode[i]=Mode(f"Mode[{i}]", duration[i])
    mode[i].addResource(res,requirement=req[i])
    act[i].addModes(mode[i])

プログラム全体を以下に示す.

ex5[source]

ex5()

Example 5 Resource Constrained Scheduling file name: Example5.py Copyright Log Opt Co., Ltd.

Consider a 4-activity problem with a resource whose capacity is 2 units on day 1, 2, 4, 5, 6, and 1 unit on day 3. The processing times (durations) of the activities are kept in the dictionary duration ={1:1,2:3,3:2,4:2}. Precedence constraints are give by: Activity 1 -> Activity 2; Activity 1 -> Activity 3; Activity 2 -> Activity 4. Activity 1 requires 2 units of resource the first day. Activity 2 requires 2 units of resource the first day and 1 unit on other days. Activity 3 requires 1 unit of resource all the days. Activity 4 requires 1 unit of the resource the first day and 2 units on the second day. The objective is to find the maximum completion time (makespan).

model=Model()
duration ={1:1,2:3,3:2,4:2}

#res=model.addResource("worker", capacity = {(0,2):2, (2,3):1, (3,"inf"): 2} )
res=model.addResource("worker")
res.addCapacity(0,2,2)
res.addCapacity(2,3,1)
res.addCapacity(3,"inf",2)

req={}
req[1]={(0,1):2 }
req[2]={(0,1):2 ,(1,3):1}
req[3]={(0,2):1 }
req[4]={(0,1):1,(1,2):2 }

act={}
mode={}
for i in duration:
    act[i]=model.addActivity(f"Act[{i}]")
    mode[i]=Mode(f"Mode[{i}]", duration[i])
    mode[i].addResource(res,requirement=req[i])
    act[i].addModes(mode[i])

model.addTemporal(act[1],act[2])
model.addTemporal(act[1],act[3])
model.addTemporal(act[2],act[4])

model.Params.TimeLimit=1
model.Params.Makespan=True
model.optimize()
 ================ Now solving the problem ================ 


Solutions:
    source   ---     0     0
      sink   ---     6     6
    Act[1]   ---     0     1
    Act[2]   ---     1     4
    Act[3]   ---     3     5
    Act[4]   ---     4     6
visualize(model)
G cluster[Act[1]] cluster[Act[2]] cluster[Act[3]] cluster[Act[4]] worker worker Mode[1] Mode[1] Mode[1]->worker Act[1] Act[1] Act[1]->Mode[1] Act[2] Act[2] Act[1]->Act[2] Act[3] Act[3] Act[1]->Act[3] Mode[2] Mode[2] Mode[2]->worker Act[2]->Mode[2] Act[4] Act[4] Act[2]->Act[4] Mode[3] Mode[3] Mode[3]->worker Act[3]->Mode[3] Mode[4] Mode[4] Mode[4]->worker Act[4]->Mode[4]

例題6 納期遅れ最小化スケジューリング

あなたは売れっ子連載作家だ.あなたは,A, B, C, D の4社から原稿を依頼されており, それぞれどんなに急いで書いても $1$ 日,$2$ 日,$3$ 日,$4$ 日かかるものと思われる. 各社に約束した納期は,それぞれ $5$ 日後,$9$ 日後,$6$ 日後,$4$ 日後であり, 納期から $1$ 日遅れるごとに $1$ 万円の遅延ペナルティを払わなければならない.

どのような順番で原稿を書けば,支払うペナルティ料の合計を最小にできるだろうか?

今までの例では,すべて最大完了時刻(メイクスパン)を最小化していた. ここでは,作業ごとに決められた納期からの遅れの和を最小化することを考える.

各社の仕事を $1,2,3,4$ とし, その作業時間をduration,納期をdueに保管しておく. 作業を追加するためのaddActivityメソッドのduedate引数で納期を表す $0$ 以上の整数値(もしくは無限大を表す文字列"inf")を指定する. また,引数weightで納期遅れに対する重みを設定できる.重みweightの既定値は $1$ であるので省略しても良い. 作業によって納期遅れのペナルティが異なる場合には,この引数を用いる.

duration={1:1, 2:2, 3:3, 4:4}
due={1:5,2:9,3:6,4:4}

for i in duration:
    act[i]=model.addActivity(f"Act[{i}]", duedate=due[i], weight=1)

さらにmodelのパラメータParamsで最大完了時刻を最小化することを表すMakespanをFalseに設定する(既定値はFalseであるので省略しても良い).

プログラム全体を以下に示す.

ex6[source]

ex6()

Example 6 Minimizing the Tardiness file name: Example6.py Copyright Log Opt Co., Ltd.

Consider a 4-activity problem with one machine resource. The due dates and processing times (durations) of the activities are kept in the dictionaries due={1:5,2:9,3:6,4:4} and duration={1:1, 2:2, 3:3, 4:4 }, respectively. We have to pay tardiness penalty by the amount the completion time of the activity exceeds its due date. The objective is to find the schedule that minimizes total tardiness penalty cost.

model=Model()
due={1:5,2:9,3:6,4:4}
duration={1:1, 2:2, 3:3, 4:4 }

res=model.addResource("writer")
res.addCapacity(0, "inf", 1)

act={}
mode={}

for i in duration:
    act[i]=model.addActivity(f"Act[{i}]", duedate=due[i], weight=1)
    mode[i]=Mode(f"Mode[{i}]", duration[i])
    mode[i].addResource(res,1)
    act[i].addModes(mode[i])

model.Params.TimeLimit=1
model.Params.Makespan=False
model.optimize()
 ================ Now solving the problem ================ 


Solutions:
    source   ---     0     0
      sink   ---    10    10
    Act[1]   ---     4     5
    Act[2]   ---     8    10
    Act[3]   ---     5     8
    Act[4]   ---     0     4
visualize(model)
G cluster[Act[1]] cluster[Act[2]] cluster[Act[3]] cluster[Act[4]] writer writer Mode[1] Mode[1] Mode[1]->writer Act[1] Act[1] Act[1]->Mode[1] Mode[2] Mode[2] Mode[2]->writer Act[2] Act[2] Act[2]->Mode[2] Mode[3] Mode[3] Mode[3]->writer Act[3] Act[3] Act[3]->Mode[3] Mode[4] Mode[4] Mode[4]->writer Act[4] Act[4] Act[4]->Mode[4]

例題7 クリティカルパス法(再生不能資源の使用法)

あなたは,航空機会社のコンサルタントだ. 今度は,作業時間の短縮を要求されている (ただし,資源制約(人の制限)はないものとする). いま,航空機の離陸の前にする作業の時間が,費用をかけることによって短縮でき, 各作業の標準時間,新設備導入によって短縮したときの時間,ならびにそのときに必要な費用は, 以下のように推定されているものとする.

  • 作業1: 乗客降ろし $13$ 分.$10$ 分に短縮可能で,$1$ 万円必要.
  • 作業2: 荷物降ろし $25$ 分.$20$ 分に短縮可能で,$1$ 万円必要.
  • 作業3: 機内清掃 $15$ 分.$10$ 分に短縮可能で, $1$ 万円必要.
  • 作業4: 新しい乗客の搭乗 $27$ 分.$25$ 分に短縮可能で, $1$ 万円必要.
  • 作業5: 新しい荷物積み込み $22$ 分.$20$ 分に短縮可能で, $1$ 万円必要.

さて,いくら費用をかけると,どのくらい離陸時刻を短縮することができるだろうか?

これは, クリティカルパス法 (Critical Path Method; CPM)とよばれる古典的な問題である. CPMは,作業時間を費用(お金)をかけることによって短縮できるという仮定のもとで, 費用と作業完了時刻のトレードオフ曲線を求めることを目的としたPERTの変形で,資源制約がないときには効率的な解法が古くから知られているが, 資源制約がつくと困難な問題になる. ここでは,この問題が「モード」と「再生不能資源」を用いて,OptSeqでモデル化できることを示す.

作業は通常の作業時間と短縮時の作業時間をもつが,これは作業に付随するモードで表現することができる. 問題となるのは,作業時間を短縮したときには,費用がかかるという部分である. 費用は資源の一種と考えられるが,いままで考えていた資源とは異なる種類の資源である.

いままで考えていた資源は,機械や人のように,作業中は使用されるが, 作業が終了すると,再び別の作業で使うことができるようになる. このような,作業完了後に再び使用可能になる資源を, 再生可能資源 (renewable resource)とよぶ. 一方,費用(お金)や原材料のように,一度使うとなくなってしまう資源を, 再生不能資源 (nonrenewable resource)とよぶ.

CPMの例題に対して,再生不能資源(お金)の上限を色々変えて最短時間を求める. まず,各々の作業に対して,通常の作業時間をもつ場合と,短縮された作業時間をもつ場合の 2つのモードを追加し,さらに短縮モードを用いた場合には,再生不能資源を $1$単位使用するという条件を付加する.

再生不能資源は,modelインスタンスのaddResoureメソッドで追加できる.このとき,右辺定数rhsと制約の方向directionを定義する必要がある. 左辺の項は再生不能資源インスタンスresaddTermsメソッドで追加する.引数は順に,係数,作業インスタンス,モードインスタンスである.

res=model.addResource("money",rhs=5,direction="<=")

for i in Jobs:
    res.addTerms(1,act[i],mode[i,2])

再生不能資源は制約最適化ソルバーSCOPの線形制約と同じ構造で入力する. これは,OptSeqがSCOPを利用して最適化しているためである. 再生不能資源とは,作業を変数,モードを変数のとる値とした制約最適化の線形制約に他ならない.

プログラム全体を以下に示す.

ex7[source]

ex7()

Example 7 CPM(critical path method) -- nonrenewable resource file name: Example7.py Copyright Log Opt Co., Ltd.

Consider the same scenario as in Example 1. Here, activities have a standard mode and an express mode whose durations are durationA = {1:13, 2:25, 3:15, 4:27, 5:22 } and durationB = {1:10, 2:20, 3:10, 4:25, 5:20 }, respectively. Express modes require additional costs; they can be processed at most 4. Find the makespan under the restriction.

model=Model()
Jobs=[1,2,3,4,5]
durationA = {1:13, 2:25, 3:15, 4:27, 5:22 }
durationB = {1:10, 2:20, 3:10, 4:25, 5:20 }

act={}
mode={}
for i in Jobs:
    mode[i,1]=Mode(f"Mode[{i}][1]",durationA[i])
    mode[i,2]=Mode(f"Mode[{i}][2]",durationB[i])
    act[i]=model.addActivity(f"Act[{i}]")
    act[i].addModes(mode[i,1],mode[i,2])

res=model.addResource("money",rhs=5,direction="<=")

for i in Jobs:
    res.addTerms(1,act[i],mode[i,2])

model.addTemporal(act[1],act[3])
model.addTemporal(act[2],act[4])
model.addTemporal(act[2],act[5])
model.addTemporal(act[3],act[4])

model.Params.TimeLimit=1
model.Params.Makespan=True
model.optimize()
 ================ Now solving the problem ================ 


Solutions:
    source   ---     0     0
      sink   ---    45    45
    Act[1] Mode[1][2]     0    10
    Act[2] Mode[2][2]     0    20
    Act[3] Mode[3][2]    10    20
    Act[4] Mode[4][2]    20    45
    Act[5] Mode[5][2]    20    40
visualize(model)
G cluster[Act[1]] cluster[Act[2]] cluster[Act[3]] cluster[Act[4]] cluster[Act[5]] money money Act[1] Act[1] Mode[1][1] Mode[1][1] Act[1]->Mode[1][1] Mode[1][2] Mode[1][2] Act[1]->Mode[1][2] Act[3] Act[3] Act[1]->Act[3] Act[2] Act[2] Mode[2][1] Mode[2][1] Act[2]->Mode[2][1] Mode[2][2] Mode[2][2] Act[2]->Mode[2][2] Act[4] Act[4] Act[2]->Act[4] Act[5] Act[5] Act[2]->Act[5] Mode[3][1] Mode[3][1] Act[3]->Mode[3][1] Mode[3][2] Mode[3][2] Act[3]->Mode[3][2] Act[3]->Act[4] Mode[4][1] Mode[4][1] Act[4]->Mode[4][1] Mode[4][2] Mode[4][2] Act[4]->Mode[4][2] Mode[5][1] Mode[5][1] Act[5]->Mode[5][1] Mode[5][2] Mode[5][2] Act[5]->Mode[5][2]

例題8 時間制約

OptSeqでは,完了後に開始できるという通常の時間制約の他に,様々なタイプの時間制約を定義できる. この一般化された時間制約を用いることによって,実際問題で発生する様々な付加条件をモデル化することができる.

一般化した時間制約の適用例として,例題1に以下のような時間制約を追加することを考える.

  1. 作業3と作業5の開始時刻が一致しなければならない.
  2. 作業5の開始時刻は,(開始時刻を $0$ としたとき) ちょうど $50$分でなければならない.
  3. 作業2は作業1の終了後 $5$分~$10$分の間に開始しなければならない.

時間制約には以下の引数を定義することができる.

  • type: 時間制約のタイプを表す文字列であり,'SS'(開始-開始),'SC'(開始-完了),'CS'(完了-開始),'CC'(完了-完了)のいずれかを指定する. 既定値は 'CS' (開始,完了)
  • delay: 時間制約の時間ずれを表す整数値である. 既定値は $0$

作業3と作業5の開始時刻を一致させるためには,制約タイプを 'SS'(開始-開始の関係),時間ずれを $0$ と設定した2本の制約 「作業3の開始時刻 $\leq$ 作業5の開始時刻」,「作業5の開始時刻 $\leq$ 作業3の開始時刻」を追加すれば良い.

model.addTemporal(act[3],act[5],"SS",0)
model.addTemporal(act[5],act[3],"SS",0)

作業の開始時間の固定も,同様である. OptSeqでは,すべての作業に先行するダミーの作業sourceが準備されている. この作業は必ず時刻 $0$ に処理されるので, 開始時刻に相当する時間ずれをもつ時間制約を2本追加することによって,開始時刻を固定することができる.

作業5の開始時刻を $50$分に固定するには,

model.addTemporal('source', act[5],'SS',delay=50)
model.addTemporal(act[5], 'source','SS',delay=-50)

と2本の時間制約を追加する.

作業2は作業1の終了後 $5$分~$10$分の間に開始しなければならないことを表すには,以下の2本の時間制約を使う.

  • 作業1の完了後に時間遅れ $5$ で作業2が開始できる.
  • 作業2の開始後に時間遅れ $-10$ で作業1が完了できる.
model.addTemporal(act[1],act[2],'CS',5)
model.addTemporal(act[2],act[1],'SC',-10)

上のプログラムを追加したコード全体は以下のようになる.

ex8[source]

ex8()

Example 8 Temporal Constraints file name: Example8.py Copyright Log Opt Co., Ltd.

Consider the same scenario as in Example 1. Here, we add an additional temporal constraint; Activity 3 and Activity 5 must be start simultaneously. Find the makespan under this new condition.

model=Model()
durationA = {1:13, 2:25, 3:15, 4:27, 5:22 }

act={}
mode={}

for i in durationA:
    act[i]=model.addActivity(f"Act[{i}]")
    mode[i]=Mode(f"Mode[{i}]", durationA[i])
    act[i].addModes(mode[i])

model.addTemporal(act[1],act[3])
model.addTemporal(act[2],act[4])
model.addTemporal(act[2],act[5])
model.addTemporal(act[3],act[4])

#作業3と作業5の開始時刻が一致しなければならない
model.addTemporal(act[3],act[5],"SS",0)
model.addTemporal(act[5],act[3],"SS",0)

#作業5の開始時刻を  50 分に固定
model.addTemporal("source",act[5],"SS",delay=50)
model.addTemporal(act[5],"source","SS",delay=-50)

#作業2は作業1の終了後5分~10分の間に開始しなければならない
model.addTemporal(act[1],act[2],'CS',5)
model.addTemporal(act[2],act[1],'SC',-10)
    
model.Params.TimeLimit=1
model.Params.Makespan=True
model.optimize()
 ================ Now solving the problem ================ 


Solutions:
    source   ---     0     0
      sink   ---    92    92
    Act[1]   ---     0    13
    Act[2]   ---    18    43
    Act[3]   ---    50    65
    Act[4]   ---    65    92
    Act[5]   ---    50    72
visualize(model)
G cluster[Act[1]] cluster[Act[2]] cluster[Act[3]] cluster[Act[4]] cluster[Act[5]] Act[1] Act[1] Mode[1] Mode[1] Act[1]->Mode[1] Act[2] Act[2] Act[1]->Act[2] (5) Act[3] Act[3] Act[1]->Act[3] Act[2]->Act[1] SC Mode[2] Mode[2] Act[2]->Mode[2] Act[4] Act[4] Act[2]->Act[4] Act[5] Act[5] Act[2]->Act[5] Mode[3] Mode[3] Act[3]->Mode[3] Act[3]->Act[4] Act[3]->Act[5] SS Mode[4] Mode[4] Act[4]->Mode[4] Act[5]->Act[3] SS Mode[5] Mode[5] Act[5]->Mode[5] source source Act[5]->source SS source->Act[5] SS(50)

例題9 作業の途中中断

多くの実際の現場では,緊急の作業が入ってくると,いま行っている作業を途中で中断して, 別の(緊急で行わなければならない)作業を行った後に,再び中断していた作業を途中から行うことがある. このように,途中で作業を中断しても,再び(一から作業をやり直すのではなく) 途中から作業を続行することを「作業の途中中断」とよぶ.

OptSeqでは,これを作業を分割して処理することによって表現する. たとえば,作業時間が$3$時間の作業があったとする. 途中中断可能な場合には,時間の基本単位を$1$時間としたとき,この作業は,$1$ 時間の作業時間をもつ $3$ つの小作業に分割して処理される.

しかし,実際問題では,中断可能なタイミングが限られている場合もある. たとえば,料理をするときに,材料を切ったり,混ぜたりするときには,途中で中断することも可能だが, いったんオーブンレンジに入れたら,途中でとめたりすることはできない.

OptSeqでは作業のモードに対して,区間ごとの最大中断可能時間を設定することによって,様々な作業の中断(break)を表現する.

モードの途中中断は,

addBreak(区間の開始時刻,区間の終了時刻,最大中断時間)

を用いて追加する.

たとえば, 例題6の納期遅れ最小化問題において,いつでも最大1日だけ中断できる場合は,

mode[i].addBreak(0,"inf",1)

とし,作業開始の1日後までなら1日だけ中断できる場合は,

mode[i].addBreak(0,1,1)

とすれば良い.

また,段取りを伴う生産現場においては,中断の途中で他の作業を行うことが禁止されている場合がある. これは,中断中に異なる作業を行うと, 再び段取りなどの処理を行う必要があるため,作業を一からやり直さなければならないからである. これは,作業の中断中でも資源を使い続けていると表現することによって回避することができる.

中断中に資源を使用する場合も,通常の資源を追加するのと同様にaddResourceメソッドに "break" を追加する.

addResource( 資源,{(区間):資源使用量},"break")

例題6において作家が執筆中に休暇をとることができない場合には,

mode[i].addResource(res,1,"break")

とする.

例題6で,すべての作業がいつでも最大1日だけ中断できる場合を考える. ただし,作家は $4$ 日目と $7$ 日目と $11$ 日目に休暇をとるものとする.

中断中に資源を使わない場合と,使う場合のプログラムを以下に示す.

ex9[source]

ex9()

Example 9 Breakable Activity file name: Example9.py Copyright Log Opt Co., Ltd.

Consider the same scenario as in Example 6. Here, Activities can interrupt their processing and re-start after one unit of break time. Find the optimal schedule (minimum tardiness solution) under this new condition.

model=Model()

due={1:5,2:9,3:6,4:4}
duration={1:1, 2:2, 3:3, 4:4 }

res=model.addResource("writer")
res.addCapacity(0,3,1)
res.addCapacity(4,6,1)
res.addCapacity(7,10,1)
res.addCapacity(11,"inf",1)

act={}
mode={}

for i in duration:
    act[i]=model.addActivity(f"Act[{i}]",duedate=due[i])
    mode[i]=Mode(f"Mode[{i}]",duration[i])
    mode[i].addResource(res,1)
    mode[i].addBreak(0,"inf",1)    
    #mode[i].addBreak(0,1,1) #開始後1日までしか中断を入れられない合はここを生かす.
    #mode[i].addResource(res,1,"break") #中断中も資源を使う場合にはここを生かす。
    act[i].addModes(mode[i])

model.Params.TimeLimit=1
model.Params.OutputFlag=True
model.Params.Makespan=False
model.optimize()

結果のログに

Act[3],---, 8 9--10 11--13 13
Act[4],---, 0 1--3 4--6 6

とあるので,作業3と作業4は途中中断しており, 作業3は9日から10日までと11日から13日に,作業4は1日から3日と4日から6日に分割して処理されていることが分かる.

また, 作業が行われている時間の情報は,作業インスタンスのexecute属性に辞書として保管されているので,以下のコードで確認することもできる.

for i in act:
    print(i, act[i].execute) # (開始時刻,終了時刻): 並列数

例題10 作業の並列実行

例題4の並列ショップスケジューリング問題の拡張では, 複数の機械(作業員)によって作業時間が短縮されることを,複数のモードを用いることによって表現していた. ここでは,複数資源による作業の並列処理を,より簡単に表現するための方法を紹介する.

作業の途中中断と同じように,作業を単位時間の作業時間をもつ小作業に分解して考える. いま,資源使用量の上限が $1$ より大きいとき,分解された小作業は,並列して処理できるものとする. ただし実際問題においては,無制限に並列処理ができない場合もある. OptSeqでは,これを最大並列数とよばれるパラメータを用いて表現する.

並列処理は,作業モードに対するaddParallelメソッドを用いて定義される. 書式は,

addParallel(開始小作業番号,終了小作業番号,最大並列数)

である.

たとえば,

mode.addParallel(1,1,3)
mode.addParallel(2,3,2)

は, 最初の小作業は最大3個, 2番目と3番目の小作業は最大2個の小作業を並列処理可能であることを意味する.

並列実行中に資源を使用する量は,標準(省略するか引数がNone)だと,各資源の資源使用量の総和になる. 総和でなく,並列実行中の資源の「最大量」を指定したい場合には,以下のようにaddResourceメソッドの引数に "max" を追加する.

addResource( 資源,{(区間):資源使用量},"max")

例題3の並列ショップスケジューリング問題において,給油作業(作業時間3秒)を,最初の(1番目の)小作業を最大3個並列可能とした場合を考える. 資源使用量を総和としたときと, 最大量としたときのプログラムを以下に示す.

ex10[source]

ex10()

Example 10 Parallel Execution file name: Example10.py Copyright Log Opt Co., Ltd.

Consider the same scenario as in Example 3. Here, Activity 1 can be processed in parallel up to 3 units. Find the optimal schedule under this new condition.

model=Model()
duration ={1:3, 2:2, 3:2, 4:2, 5:4, 6:4, 7:4, 8:4, 9:11, 10:2 }

res=model.addResource("worker")
res.addCapacity(0,"inf",3)

act={}
mode={}

for i in duration:
    act[i]=model.addActivity(f"Act[{i}]")

    if i==1:
        mode[i]=Mode(f"Mode[{i}]", duration[i])
        mode[i].addParallel(1,1,3)
        mode[i].addResource(res,1)       #並列実行中の資源量が各作業の使用量の総和のときはこちらを生かす
        #mode[i].addResource(res,1,'max') #並列実行中で使用する資源量が最大1のときはこちらを生かす
    else:
        mode[i]=Mode(f"Mode[{i}]", duration[i])
        mode[i].addResource(res,1)
    act[i].addModes(mode[i])

model.addTemporal(act[1],act[9])
for i in range(5,9):
    model.addTemporal(act[4],act[i])
    model.addTemporal(act[i],act[10])

model.Params.TimeLimit=1
model.Params.OutputFlag=True
model.Params.Makespan=True
model.optimize()

結果のログに

Act[1],---, 0 0--1[2] 1--2 2

とあるので,作業1は最初の1秒は2人で並列に実行し,2秒目は1人で実行していることが分かる.

また, 作業が行われている時間の情報は,作業インスタンスのexecute属性に辞書として保管されているので,以下のコードで確認することもできる.

for i in act:
    print(i, act[i].execute) # (開始時刻,終了時刻): 並列数

例題11 実務的な機械スケジューリング問題

例として,4作業3機械のスケジューリング問題を考える. 各作業はそれぞれ 3つの子作業(これを以下では作業とよぶ)$1$, $2$, $3$ から成り, この順序で処理しなくてはならない. 各作業を処理する機械, および処理日数は,以下の表の通りである.

小作業1 小作業2 小作業3
作業1 機械1: 7日 機械2: 10日 機械3: 4日
作業2 機械3: 9日 機械1: 5日 機械2 : 11日
作業3 機械1 : 3日 機械3: 9日 機械2 : 12日
作業4 機械2 : 6日 機械3: 13日 機械1 : 9日

このように,作業によって作業を行う機械の順番が異なる問題は,ジョブショップ(job shop)とよばれ, スケジューリングモデルの中でも難しい問題と考えられている.

目的は最大完了時刻最小化とする. ここでは,さらに以下のような複雑な条件がついているものと仮定する.

  1. 各作業の初めの 2日間は作業員資源を必要とする操作がある.
    この操作は平日のみ, かつ 1日あたり高々2個しか行うことができない.
  2. 各作業は,1日経過した後だけ,中断が可能.
  3. 機械1での作業は,最初の1日は2個まで並列処理が可能.
  4. 機械2に限り, 特急処理が可能.
    特急処理を行うと処理日数は4日で済むが,
    全体で1度しか行うことはできない.
  5. 機械1において, 作業1を処理した後は作業2を処理しなくてはならない.

この問題は,機械および作業員資源を再生可能資源とした12作業の スケジューリングモデルとしてOptSeqで記述できる.

ex11[source]

ex11()

A simple test problem for the Resource Constrained Scheduling Solver OptSeq file name: Example11.py Copyright Log Opt Co., Ltd.

Consider a small job shop problem consisting of 4 activities and 3 machines. Each activity consists of three sub-jobs (operations). Operation must be processed in the order of 1,2 and 3 on thecorresponding machines. The machines to be processed and the processing time (days) are kept by the dictionary JobInfo={ (1,1):(1,7), (1,2):(2,10), (1,3):(3,4), (2,1):(3,9), (2,2):(1,5), (2,3):(2,11), (3,1):(1,3), (3,2):(3,9), (3,3):(2,12), (4,1):(2,6), (4,2):(3,13),(4,3):(1,9) } that maps a tuple of activity ID and operation ID to a tuple of machine IDand processing time. The objective is to minimize the latest completion time of activities (makespan). We add the following practical conditions:

  1. Each operation requires the worker resource for the first 2 days. The worker resource is available on weekdays only and its capacity(maximum number of operations to be executed in a day) is 2.
  2. Each operation may have a break after 1 day.
  3. Operations on machine 1 can be processed in parallel.
  4. Operations on machine 2 can be processed in an express mode whose processing time is 4 days. The express mode is restricted to be at most once in a whole.
  5. On machine 1, operation 2 must be executed just after operation 1.
model = Model()
# resource declaration
machine = {}  # define three machines
for j in range(1, 4):
    machine[j] = model.addResource(f"machine[{j}]", capacity={(0, "inf"): 1})

# CAP={} #capacity of human resources; two workers are available on weekdays
# for t in range(9):
#    CAP[(t*7,t*7+5)]=2
# manpower=model.addResource("manpower",capacity=CAP)
# we may write ...
manpower = model.addResource("manpower")
for t in range(9):
    manpower.addCapacity(t*7, t*7+5, 2)

# budget constraint
budget = model.addResource("budget_constraint", rhs=1)

# activity declaration (4 activities are processed on three machines)
# JobInfo containes the info. of operations (activity,1..3):-> machine ID and proc. time
JobInfo = {(1, 1): (1, 7), (1, 2): (2, 10), (1, 3): (3, 4),
           (2, 1): (3, 9), (2, 2): (1, 5), (2, 3): (2, 11),
           (3, 1): (1, 3), (3, 2): (3, 9), (3, 3): (2, 12),
           (4, 1): (2, 6), (4, 2): (3, 13), (4, 3): (1, 9)
           }
act = {}
express = Mode("Express", duration=4)
express.addResource(machine[2], {(0, "inf"): 1}, "max")
express.addResource(manpower, {(0, 2): 1})
express.addBreak(1, 1)

mode = {}
for (i, j) in JobInfo:  # for each job and machine
    act[i, j] = model.addActivity(f"Act[{i}][{j}]")
    mode[i, j] = Mode(f"Mode[{i}][{j}]", duration=JobInfo[i, j][1])
    mode[i, j].addResource(machine[JobInfo[i, j][0]], {
                           (0, "inf"): 1}, "max")
    mode[i, j].addResource(manpower, {(0, 2): 1})
    mode[i, j].addBreak(1, 1)
    if JobInfo[i, j][0] == 1:
        mode[i, j].addParallel(1, 1, 2)

    if JobInfo[i, j][0] == 2:
        # activities processed on machine 2 have two modes, Express and Normal.
        act[i, j].addModes(mode[i, j], express)
        # Express mode needs one budget
        budget.addTerms(1, act[i, j], express)
    else:
        act[i, j].addModes(mode[i, j])  # single mode activity
    # print act[i,j]
# temporal (precedense) constraints
for i in range(1, 5):
    for j in range(1, 3):
        model.addTemporal(act[i, j], act[i, j+1])

# Define that Act[2][2] must be processed just after Act[1][1] on machine 1
# introduce dummy with duration 0 and can break at time 0
# it requires machine 1 during the break,
#  completion of Act[1][1]=start of dummy and completaion of dummy=start of Act[2][2]
d_act = model.addActivity("dummy_activity")
d_mode = Mode("dummy_mode")
d_mode.addBreak(0, 0)
d_mode.addResource(machine[1], {(0, 0): 1}, "break")
d_act.addModes(d_mode)
model.addTemporal(act[1, 1], d_act, tempType="CS")
model.addTemporal(d_act, act[1, 1], tempType="SC")
model.addTemporal(d_act, act[2, 2], tempType="CS")
model.addTemporal(act[2, 2], d_act, tempType="SC")

model.Params.TimeLimit = 10
model.Params.Makespan = True
model.optimize()
 ================ Now solving the problem ================ 


Solutions:
    source   ---     0     0
      sink   ---    38    38
 Act[1][1]   ---     3     9
 Act[1][2] Mode[1][2]    10    20
 Act[1][3]   ---    32    38
 Act[2][1]   ---     0     9
 Act[2][2]   ---     9    13
 Act[2][3] Mode[2][3]    21    32
 Act[3][1]   ---     0     3
 Act[3][2]   ---    23    32
 Act[3][3] Express    32    38
 Act[4][1] Mode[4][1]     2     9
 Act[4][2]   ---    10    23
 Act[4][3]   ---    23    32
dummy_activity   ---     9     9
visualize(model)
G cluster[Act[1][1]] cluster[Act[1][2]] cluster[Act[1][3]] cluster[Act[2][1]] cluster[Act[2][2]] cluster[Act[2][3]] cluster[Act[3][1]] cluster[Act[3][2]] cluster[Act[3][3]] cluster[Act[4][1]] cluster[Act[4][2]] cluster[Act[4][3]] cluster[dummy_activity] machine[1] machine[1] machine[2] machine[2] machine[3] machine[3] manpower manpower budget_constraint budget_constraint Mode[1][1] Mode[1][1] Mode[1][1]->machine[1] max Mode[1][1]->manpower Act[1][1] Act[1][1] Act[1][1]->Mode[1][1] Act[1][2] Act[1][2] Act[1][1]->Act[1][2] dummy_activity dummy_activity Act[1][1]->dummy_activity Mode[1][2] Mode[1][2] Mode[1][2]->machine[2] max Mode[1][2]->manpower Express Express Express->machine[2] max Express->machine[2] max Express->machine[2] max Express->machine[2] max Express->manpower Express->manpower Express->manpower Express->manpower Act[1][2]->Mode[1][2] Act[1][2]->Express Act[1][3] Act[1][3] Act[1][2]->Act[1][3] Mode[1][3] Mode[1][3] Mode[1][3]->machine[3] max Mode[1][3]->manpower Act[1][3]->Mode[1][3] Mode[2][1] Mode[2][1] Mode[2][1]->machine[3] max Mode[2][1]->manpower Act[2][1] Act[2][1] Act[2][1]->Mode[2][1] Act[2][2] Act[2][2] Act[2][1]->Act[2][2] Mode[2][2] Mode[2][2] Mode[2][2]->machine[1] max Mode[2][2]->manpower Act[2][2]->Mode[2][2] Act[2][3] Act[2][3] Act[2][2]->Act[2][3] Act[2][2]->dummy_activity SC Mode[2][3] Mode[2][3] Mode[2][3]->machine[2] max Mode[2][3]->manpower Act[2][3]->Express Act[2][3]->Mode[2][3] Mode[3][1] Mode[3][1] Mode[3][1]->machine[1] max Mode[3][1]->manpower Act[3][1] Act[3][1] Act[3][1]->Mode[3][1] Act[3][2] Act[3][2] Act[3][1]->Act[3][2] Mode[3][2] Mode[3][2] Mode[3][2]->machine[3] max Mode[3][2]->manpower Act[3][2]->Mode[3][2] Act[3][3] Act[3][3] Act[3][2]->Act[3][3] Mode[3][3] Mode[3][3] Mode[3][3]->machine[2] max Mode[3][3]->manpower Act[3][3]->Express Act[3][3]->Mode[3][3] Mode[4][1] Mode[4][1] Mode[4][1]->machine[2] max Mode[4][1]->manpower Act[4][1] Act[4][1] Act[4][1]->Express Act[4][1]->Mode[4][1] Act[4][2] Act[4][2] Act[4][1]->Act[4][2] Mode[4][2] Mode[4][2] Mode[4][2]->machine[3] max Mode[4][2]->manpower Act[4][2]->Mode[4][2] Act[4][3] Act[4][3] Act[4][2]->Act[4][3] Mode[4][3] Mode[4][3] Mode[4][3]->machine[1] max Mode[4][3]->manpower Act[4][3]->Mode[4][3] dummy_mode dummy_mode dummy_mode->machine[1] break dummy_activity->Act[1][1] SC dummy_activity->Act[2][2] dummy_activity->dummy_mode

例題12 状態変数

状態変数とは,時間の経過とともに状態とよばれる非負整数の値が変化する変数である. 作業のモードが,特定の状態でないと開始できないという制約を付加することによって, 通常のスケジューリングモデルでは表現しきれない,様々な付加条件をモデル化することが可能になる.

まず,状態を定義するには,モデルクラスのaddStateメソッドを用いる. addStateメソッドの引数は,状態の名称を表す文字列であり,返値は状態インスタンスである. たとえば,無名の状態stateをモデルインスタンスmodelに追加するには,以下のようにする.

state = model.addState()

状態は,基本的には1つ前の時刻の値を引き継ぎ,ユーザーの指定によって特定の時刻にその値を変化させることができる変数である. 状態が,ある時間においてある値に変化することを定義するためには, addValueメソッドを用いる. たとえば,状態インスタンスstateが時刻0に値1になることを定義するには,次のように記述する.

state.addValue( time=0, value=1 )

状態は,モードで開始された直後に変化させることができる. そのためには,モードインスタンスのaddStateメソッドを用いて定義する. addStateメソッドの引数は,状態インスタンスstate, 開始時の状態(fromValue; 非負整数), 開始直後に変化する状態(toValue; 非負変数)である.

モードインスタンス.addState(state, fromValue, toValue)

これによって,モード開始時の状態 stateが値 fromValue でなくてはならず, 開始直後(開始時刻が $t$ であれば $t+1$ に)状態が値 toValue に変化することになる.

これによって,処理モードに「ある状態のときしか開始できない」といった制約を加えることが可能になる.

この記述は,状態のとる値を変えて,任意の回数行うことができる. たとえば,状態変数 state の取り得る値が $1, 2, 3$ の3種類としたとき,

mode.addState( state, 1, 2)
mode.addState( state, 2, 3)
mode.addState( state, 3, 1)

とすれば,開始時点での状態に関係なく処理は可能で,状態は巡回するように1つずつ変化することになる.

また,これを利用して「あるタイプのモード(以下のmode)は1週間(7日間)に高々3回しか処理できない」ことは, 以下のように表すことができる.

state = model.addState()
state.addValue( time=0,  value=0 ) 
state.addValue( time=7,  value=0 ) 
state.addValue( time=14, value=0 ) 
    ...
mode = Mode('mode')
mode.addState( state, 0, 1)
mode.addState( state, 1, 2)
mode.addState( state, 2, 3)

状態は7日ごとに0にリセットされ,モードmodeは状態stateが0,1,2のときだけ開始でき, 状態が3のときには開始できない.したがって7日の間に3回だけ開始できることになる.

上述のような「開始時状態が指定された処理モード」を 与える場合,通常,そのモードを含む作業の定義において,モードを自動選択(autoselect)にしておくことが推奨される.

OptSeqでは,「まず各作業の処理モードをそれぞれ選び, その後,ある順序にしたがって作業を前づめにスケジュールしていく」 ということの繰り返しを行う. したがって,「開始時状態が指定された処理モード」が存在すると, 処理モードの選び方によっては, 「スケジュールを生成していくとき,割り付け不可能」 ということが頻繁に起こりえる. これを防ぐため,「あらかじめ処理モードを指定せず,前づめスケジュールしながら 適切な処理モードを選択する」ことが必要になり,これを実現するのがモードの自動選択なのである.

作業に対してモードを自動選択に設定するには, 作業クラスのコンストラクタの引数 autoselect を用いるか,作業インスタンスの属性 autoselectを用いる. 具体的には,以下の何れの書式でも,自動選択に設定できる.

act1=model.addActivity('Act1', autoselect=True)
act1.autoselect = True

注意 作業の定義に autoselect を指定した場合には,その作業に制約を逸脱したときの重みを無限大とした (すなわち絶対制約とした)再生不能資源を定義することはできない. かならず重みを既定値の無限大 'inf' ではない正数値と設定し直す必要がある.

ex12[source]

ex12()

Example 12 Example with state file name: Example12.py Copyright Log Opt Co., Ltd.

model = Model()
n = 9 #number of activities

state = model.addState("state")
state.addValue( time=0,  value=0 )
state.addValue( time=7,  value=0 )
state.addValue( time=14, value=0 )

mode = Mode('mode', 1)
mode.addState( state, 0, 1)
mode.addState( state, 1, 2)
mode.addState( state, 2, 3)

act ={}
for i in range(n):
    act[i] = model.addActivity(f"act{i}", duedate = i, autoselect= True)
    act[i].addModes(mode)

model.Params.TimeLimit = 1
model.Params.Makespan = False
model.optimize()

例題13 順序依存の段取り時間

D,E,Fの3つの作業(作業時間は全部30)を1つのライン上で生産する問題を考える。 初期状態startからは、いずれの作業も段取り時間0で作業開始できるが、D,E,Fの間には、以下の表のような順序に依存した作業時間がかかるものとする。

D E F
D - 10 0
E 50 - 10
F 0 10 -

これを表現するためには、状態変数を用いる。状態は start, D,E,F であり、それぞれ 0,1,2,3という整数で表すものとする。 各段取りに対して、段取りモード mode_setup[i,j] を準備し、状態がiでないと開始できず、開始すると状態をjに移すものとする。 各作業 act[j] に対して段取り作業 act_setup[j] を準備し、モードmode_setup[i,j]を追加する。 また、段取り作業の終了時刻と、作業act[j]の開始時刻が一致するようにしておく。

ex13[source]

ex13()

順序依存の段取り時間の例題

model = Model()
duration = {"D": 30, "E": 30, "F": 30}
setup = {("D", "E"): 10, ("E", "D"): 50, ("E", "F"): 10, ("F", "E"): 10,
         ("start", "D"): 0, ("start", "E"): 10, ("start", "F"): 0,
         ("D", "F"): 0, ("F", "D"): 0}
s = {"D": 1, "E": 2, "F": 3, "start": 0}

rs = model.addResource("line1", 1)

act = {}
mode = {}
for i in duration:
    act[i] = model.addActivity(f"Act_{i}")
    mode[i] = Mode(f"Mode_{i}", duration[i])
    mode[i].addResource(rs, {(0, "inf"): 1})
    act[i].addModes(mode[i])

s1 = model.addState("Setup_State")
s1.addValue(time=0, value=s["start"])
# setup mode
mode_setup = {}
for (i, j) in setup:
    mode_setup[i, j] = Mode(f"Mode_setup_{i}_{j}", setup[i, j])
    mode_setup[i, j].addState(s1, s[i], s[j])
    if setup[i, j] != 0:
        mode_setup[i, j].addResource(rs, {(0, setup[i, j]): 1})

    #print (i,j,s[i],s[j],mode_setup[i,j])

act_setup = {}
for k in duration:
    act_setup[k] = model.addActivity(f"Setup_{k}", autoselect=True)
    for (i, j) in setup:
        if k == j:
            act_setup[k].addModes(mode_setup[i, j])

# temporal (precedense) constraints
for j in act_setup:
    model.addTemporal(act_setup[j], act[j], "CS")
    model.addTemporal(act[j], act_setup[j], "SC")

model.Params.TimeLimit = 1
model.Params.Makespan = True
model.optimize()

例題14 貯蔵資源の表現方法

2つの作業(13時間と25時間の作業時間)を考える。作業1の開始後、3時間後に作業2が開始できる。 作業1で製造された半製品は2つのタンク(Tank1,2)のいずれかに保管する必要がある。 タンク1は常に使用可能であるが、タンク2は10時間後にメンテナンスが予定されているため、使うことができない。

半製品はダミーの作業(dummy)で表現され、タンク1,2の使用を表す2つのモード (modeDumodel,2)をもつ。 これらのモードは作業時間は0だが、開始後に休憩可能 (breakable) とし、開始は作業1の開始時、終了は作業2の終了時と設定する。

半製品は長時間保管すると劣化するので、休憩は最大10時間と設定すると、実行不能になり、最大30時間と設定すると実行可能になる。

ex14[source]

ex14()

タンク(貯蔵資源)を考慮した例題

model = Model()
duration = {1: 13, 2: 25}
act = {}
mode = {}
for i in duration:
    act[i] = model.addActivity(f"Act[{i}]")
    mode[i] = Mode(f"Mode[{i}]", duration[i])
    act[i].addModes(mode[i])

r1 = model.addResource("Tank1", 1)
r2 = model.addResource("Tank2", {(0, 10): 1})

dummy = model.addActivity("actDum")
modeDumodel = Mode("DumMode1", 0)
modeDum2 = Mode("DumMode2", 0)
#modeDumodel.addBreak(0, 0, 10)  # infeasible
modeDumodel.addBreak(0,0,30) #feasible
modeDumodel.addResource(r1, 1, rtype="break")
modeDum2.addBreak(0, 0, "inf")
modeDum2.addResource(r2, 1, rtype="break")
dummy.addModes(modeDumodel, modeDum2)

model.addTemporal(act[1], dummy, "SS", 0)
model.addTemporal(dummy, act[1], "SS", 0)
model.addTemporal(act[2], dummy, "CC", 0)
model.addTemporal(dummy, act[2], "CC", 0)

model.addTemporal(act[1], act[2], "SS", 3)

model.Params.TimeLimit = 1
model.optimize()

例題15 ジョブショップスケジューリング問題のベンチマーク問題例

ジョブショップスケジューリング問題は以下のように定義される.

ジョブを $J_1, J_2,\cdots, J_n$,ジョブ $J_j$ に属するオペレーションを $O_{1j},O_{2j},\cdots,O_{m_j j}$, 機械を $M_1,M_2, \cdots, M_m$ とする.

オペレーションは $O_{1j},O_{2j},\cdots,O_{m_j j}$ の順で処理されなければならず, オペレーション $O_{ij}$ を処理するには機械 $\mu_{ij}$ を作業時間 $p_{ij}$ だけ占有する. オペレーションが途中で中断できないという仮定の下で,最後のオペレーションが完了する時刻を最小化する各機械上でのオペレーションの処理順序を求める.

OR-Lib.(http://people.brunel.ac.uk/~mastjjb/jeb/orlib/jobshopinfo.html) にあるベンチマーク問題例を読み込んで解く.

例としてft06.txtを準備した.

 6 6
 2  1  0  3  1  6  3  7  5  3  4  6
 1  8  2  5  4 10  5 10  0 10  3  4
 2  5  3  4  5  8  0  9  1  1  4  7
 1  5  0  5  2  5  3  3  4  8  5  9 
 2  9  1  3  4  5  5  4  0  3  3  1
 1  3  3  3  5  9  0 10  4  4  2  1

データの説明は以下の通り.

Each instance consists of a line of description, a line containing the 
number of jobs and the number of machines, and then one line for each job,
listing the machine number and processing time for each step of the job. 
The machines are numbered starting with 0.

注意: この問題はトライアル版では解けない.

ex15[source]

ex15(fname='../data/optseq/ft06.txt')

ジョブショップスケジューリング問題のベンチマーク問題例

visualize(model, size="10")
G cluster[Act[00]] cluster[Act[01]] cluster[Act[02]] cluster[Act[03]] cluster[Act[04]] cluster[Act[05]] cluster[Act[10]] cluster[Act[11]] cluster[Act[12]] cluster[Act[13]] cluster[Act[14]] cluster[Act[15]] cluster[Act[20]] cluster[Act[21]] cluster[Act[22]] cluster[Act[23]] cluster[Act[24]] cluster[Act[25]] cluster[Act[30]] cluster[Act[31]] cluster[Act[32]] cluster[Act[33]] cluster[Act[34]] cluster[Act[35]] cluster[Act[40]] cluster[Act[41]] cluster[Act[42]] cluster[Act[43]] cluster[Act[44]] cluster[Act[45]] cluster[Act[50]] cluster[Act[51]] cluster[Act[52]] cluster[Act[53]] cluster[Act[54]] cluster[Act[55]] machine[0] machine[0] machine[1] machine[1] machine[2] machine[2] machine[3] machine[3] machine[4] machine[4] machine[5] machine[5] Mode[00] Mode[00] Mode[00]->machine[2] Act[00] Act[00] Act[00]->Mode[00] Act[01] Act[01] Act[00]->Act[01] Mode[01] Mode[01] Mode[01]->machine[0] Act[01]->Mode[01] Act[02] Act[02] Act[01]->Act[02] Mode[02] Mode[02] Mode[02]->machine[1] Act[02]->Mode[02] Act[03] Act[03] Act[02]->Act[03] Mode[03] Mode[03] Mode[03]->machine[3] Act[03]->Mode[03] Act[04] Act[04] Act[03]->Act[04] Mode[04] Mode[04] Mode[04]->machine[5] Act[04]->Mode[04] Act[05] Act[05] Act[04]->Act[05] Mode[05] Mode[05] Mode[05]->machine[4] Act[05]->Mode[05] Mode[10] Mode[10] Mode[10]->machine[1] Act[10] Act[10] Act[10]->Mode[10] Act[11] Act[11] Act[10]->Act[11] Mode[11] Mode[11] Mode[11]->machine[2] Act[11]->Mode[11] Act[12] Act[12] Act[11]->Act[12] Mode[12] Mode[12] Mode[12]->machine[4] Act[12]->Mode[12] Act[13] Act[13] Act[12]->Act[13] Mode[13] Mode[13] Mode[13]->machine[5] Act[13]->Mode[13] Act[14] Act[14] Act[13]->Act[14] Mode[14] Mode[14] Mode[14]->machine[0] Act[14]->Mode[14] Act[15] Act[15] Act[14]->Act[15] Mode[15] Mode[15] Mode[15]->machine[3] Act[15]->Mode[15] Mode[20] Mode[20] Mode[20]->machine[2] Act[20] Act[20] Act[20]->Mode[20] Act[21] Act[21] Act[20]->Act[21] Mode[21] Mode[21] Mode[21]->machine[3] Act[21]->Mode[21] Act[22] Act[22] Act[21]->Act[22] Mode[22] Mode[22] Mode[22]->machine[5] Act[22]->Mode[22] Act[23] Act[23] Act[22]->Act[23] Mode[23] Mode[23] Mode[23]->machine[0] Act[23]->Mode[23] Act[24] Act[24] Act[23]->Act[24] Mode[24] Mode[24] Mode[24]->machine[1] Act[24]->Mode[24] Act[25] Act[25] Act[24]->Act[25] Mode[25] Mode[25] Mode[25]->machine[4] Act[25]->Mode[25] Mode[30] Mode[30] Mode[30]->machine[1] Act[30] Act[30] Act[30]->Mode[30] Act[31] Act[31] Act[30]->Act[31] Mode[31] Mode[31] Mode[31]->machine[0] Act[31]->Mode[31] Act[32] Act[32] Act[31]->Act[32] Mode[32] Mode[32] Mode[32]->machine[2] Act[32]->Mode[32] Act[33] Act[33] Act[32]->Act[33] Mode[33] Mode[33] Mode[33]->machine[3] Act[33]->Mode[33] Act[34] Act[34] Act[33]->Act[34] Mode[34] Mode[34] Mode[34]->machine[4] Act[34]->Mode[34] Act[35] Act[35] Act[34]->Act[35] Mode[35] Mode[35] Mode[35]->machine[5] Act[35]->Mode[35] Mode[40] Mode[40] Mode[40]->machine[2] Act[40] Act[40] Act[40]->Mode[40] Act[41] Act[41] Act[40]->Act[41] Mode[41] Mode[41] Mode[41]->machine[1] Act[41]->Mode[41] Act[42] Act[42] Act[41]->Act[42] Mode[42] Mode[42] Mode[42]->machine[4] Act[42]->Mode[42] Act[43] Act[43] Act[42]->Act[43] Mode[43] Mode[43] Mode[43]->machine[5] Act[43]->Mode[43] Act[44] Act[44] Act[43]->Act[44] Mode[44] Mode[44] Mode[44]->machine[0] Act[44]->Mode[44] Act[45] Act[45] Act[44]->Act[45] Mode[45] Mode[45] Mode[45]->machine[3] Act[45]->Mode[45] Mode[50] Mode[50] Mode[50]->machine[1] Act[50] Act[50] Act[50]->Mode[50] Act[51] Act[51] Act[50]->Act[51] Mode[51] Mode[51] Mode[51]->machine[3] Act[51]->Mode[51] Act[52] Act[52] Act[51]->Act[52] Mode[52] Mode[52] Mode[52]->machine[5] Act[52]->Mode[52] Act[53] Act[53] Act[52]->Act[53] Mode[53] Mode[53] Mode[53]->machine[0] Act[53]->Mode[53] Act[54] Act[54] Act[53]->Act[54] Mode[54] Mode[54] Mode[54]->machine[4] Act[54]->Mode[54] Act[55] Act[55] Act[54]->Act[55] Mode[55] Mode[55] Mode[55]->machine[2] Act[55]->Mode[55]
f = open("../data/optseq/ft06.txt","r")
lines = f.readlines()
f.close()
n, m = map(int, lines[0].split())
print("n,m=", n, m)

model = Model()
act, mode, res = {}, {}, {}
for j in range(m):
    res[j] = model.addResource(f"machine[{j}]",capacity=1)

# prepare data as dic
machine, proc_time ={}, {}
for i in range(n):
    L = list(map(int,lines[i+1].split()))
    for j in range(m):
        machine[i,j] = L[2*j]
        proc_time[i,j] = (L[2*j], L[2*j+1])

for i,j in proc_time:
    act[i,j] = model.addActivity(f"Act[{i}{j}]")
    mode[i,j]=Mode(f"Mode[{i}{j}]", proc_time[i,j][1])
    mode[i,j].addResource(res[proc_time[i,j][0]],1)
    act[i,j].addModes(mode[i,j])
        
for i in range(n):
    for j in range(m-1):
        model.addTemporal(act[i,j],act[i,j+1])

model.Params.TimeLimit=10
model.Params.Makespan =True
model.optimize()
#fig = make_gannt(model, start = "2020/01/01", period ="minutes")
#plotly.offline.plot(fig);
n,m= 6 6

 ================ Now solving the problem ================ 


Solutions:
    source   ---     0     0
      sink   ---    55    55
   Act[00]   ---     5     6
   Act[01]   ---     6     9
   Act[02]   ---    16    22
   Act[03]   ---    30    37
   Act[04]   ---    42    45
   Act[05]   ---    49    55
   Act[10]   ---     0     8
   Act[11]   ---     8    13
   Act[12]   ---    13    23
   Act[13]   ---    28    38
   Act[14]   ---    38    48
   Act[15]   ---    48    52
   Act[20]   ---     0     5
   Act[21]   ---     5     9
   Act[22]   ---     9    17
   Act[23]   ---    18    27
   Act[24]   ---    27    28
   Act[25]   ---    42    49
   Act[30]   ---     8    13
   Act[31]   ---    13    18
   Act[32]   ---    22    27
   Act[33]   ---    27    30
   Act[34]   ---    30    38
   Act[35]   ---    45    54
   Act[40]   ---    13    22
   Act[41]   ---    22    25
   Act[42]   ---    25    30
   Act[43]   ---    38    42
   Act[44]   ---    48    51
   Act[45]   ---    52    53
   Act[50]   ---    13    16
   Act[51]   ---    16    19
   Act[52]   ---    19    28
   Act[53]   ---    28    38
   Act[54]   ---    38    42
   Act[55]   ---    42    43

例題16: 後ろ詰めの表現方法

例題6の納期遅れ最小化問題において, 作業1の納期を15とし,後ろ詰めで最適化を行う.

(後ろ詰めの場合には状態変数は使えない. 実際問題を解く際には,実行不可能にならないように,開始時刻を過去の時点にするなどの工夫が必要になる.)

ex16[source]

ex16()

Example 16 Minimizing the Tardiness file name: Example16.py Copyright Log Opt Co., Ltd.

Consider a 4-activity problem with one machine resource. The due dates and processing times (durations) of the activities are kept in the dictionaries due={1:15,2:9,3:6,4:4} and duration={1:1, 2:2, 3:3, 4:4 }, respectively. We have to pay tardiness penalty by the amount the completion time of the activity exceeds its due date. The objective is to find the schedule that minimizes total tardiness penalty cost.

But the activity 1 shoud be dispatched as late as possible!

model=Model()
due={1:15,2:9,3:6,4:4}
duration={1:1, 2:2, 3:3, 4:4 }

res=model.addResource("writer")
res.addCapacity(0,"inf",1)

act={}
mode={}

for i in duration:
    if i==1:
        act[i]=model.addActivity(f"Act[{i}]", duedate=due[i], backward=True)
    else:
        act[i]=model.addActivity(f"Act[{i}]", duedate=due[i])
    mode[i]=Mode(f"Mode[{i}]", duration[i])
    mode[i].addResource(res,{(0,"inf"):1})
    act[i].addModes(mode[i])

model.addTemporal(act[4],act[1])

model.Params.TimeLimit=1
model.Params.Makespan=False
model.optimize()

例題17: リリース時刻

例題1のモデルで,作業1の開始時刻を,ちょうど10に設定する.

ダミーの始点'source'は時刻 $0$ に開始するので,それとの時間制約を付加する.

ex17[source]

ex17()

model = Model()
duration = {1: 13, 2: 25, 3: 15, 4: 27, 5: 22}
act = {}
mode = {}
for i in duration:
    act[i] = model.addActivity(f"Act[{i}]")
    mode[i] = Mode(f"Mode[{i}]", duration[i])
    act[i].addModes(mode[i])

# temporal (precedense) constraints
model.addTemporal(act[1], act[3])
model.addTemporal(act[2], act[4])
model.addTemporal(act[2], act[5])
model.addTemporal(act[3], act[4])

#リリース時刻
model.addTemporal("source",act[1],tempType="SS",delay=10)
model.addTemporal(act[1],"source",tempType="SS",delay=-10)

model.Params.TimeLimit = 1
model.Params.Makespan = True
model.optimize()

例題18: 平準化

例題2のモデルで,先行制約がない場合を考える. 納期は52日であり,資源制約をなるべく平準化したい.

平準化を行うためには,資源の上限を1から順に増やしていき,納期を満たす最小の資源量を求めれば良い.

ex18[source]

ex18()

for ub in range(1,10):
    model=Model()
    duration ={1:13, 2:25, 3:15, 4:27, 5:22 }
    res=model.addResource("worker",capacity=ub)

    act={}
    mode={}
    for i in duration:
        act[i]=model.addActivity(f"Act[{i}]", duedate=52)
        mode[i]=Mode(f"Mode[{i}]",duration[i])
        mode[i].addResource(res,requirement=1)
        act[i].addModes(mode[i])

    model.Params.TimeLimit=1
    model.optimize()
    completion = 0
    for a in act:
        completion = max(completion, act[a].completion)
    if completion <= 52:
        break
fig = make_resource_graph(model)
plotly.offline.plot(fig);

例題19: モード間の関係

以下のようなモード間の制約は,再生不能資源で表現できる.

  • 作業Aがモード0で行われるなら,作業Bもモード0で行わなければならない.また,作業Bがモード0で行われるなら,作業Aがモード0で行わなければならない.

作業Aをモード0で行うとき1,それ以外のとき0の変数を用いると,制約は以下のように書ける. $$ x[A,0] = x[B,0] $$

  • 作業Aをモード1で行ったときは,作業Bはモード1で実行できない.また,作業Bをモード1で行ったときは,作業Aはモード1で実行できない.
$$ x[A,1] + x[B,1] \leq 1 $$
  • 作業Aをモード2で行ったときは,作業Bはモード2かモード3で行わなければならない.
$$ x[A,2] \leq x[B,2] + x[B,3] $$

ex19[source]

ex19()

model=Model()
duration ={ ("A",0) :10, ("A",1) :13, ("A",2) :12,
            ("B",0) :15, ("B",1) :11, ("B",2) :12, ("B",3) :14 }
act={}
mode={}
for i,j in duration:
    mode[i,j] = Mode(f"Mode[{i},{j}]", duration[i,j])
act["A"] = model.addActivity("Act[A]")
act["B"] = model.addActivity("Act[B]")
act["A"].addModes(mode["A",0], mode["A",1], mode["A",2])
act["B"].addModes(mode["B",0], mode["B",1], mode["B",2], mode["B",3] )

con1 = model.addResource("constraint_1",rhs=0,direction = "=")
con1.addTerms(coeffs=[1,-1], vars= [act["A"], act["B"]], values =[mode["A",0],mode["B",0]])

con2 = model.addResource("constraint_2",rhs=1,direction = "<=")
con2.addTerms(coeffs=[1,1], vars= [act["A"], act["B"]], values =[mode["A",1],mode["B",1]])

con3 = model.addResource("constraint_3",rhs=0,direction = "<=")
con3.addTerms(coeffs=[1,-1,-1], vars= [act["A"], act["B"], act["B"]], values =[mode["A",2], mode["B",2], mode["B",3]])

model.Params.TimeLimit=1
model.Params.Makespan = True
model.optimize()

例題20: 納期遅れをしない範囲でなるべく多くの仕事をこなす方法

例題6の納期遅れ最小化問題で,納期遅れは許されないという条件で,なるべく多くの仕事をこなすにはどうすれば良いだろうか?

仕事を引き受けない場合には,作業時間が0になるモードを定義し,そのモードをなるべく選択しないことを再生不能資源で定義する. ただし,再生不能資源の制約は,重み1の考慮制約とし,できるだけ満たすものとする. なお,納期遅れのペナルティは大きく設定しておく.

ex20[source]

ex20()

model = Model()
due = {1:5, 2:9, 3:6, 4:4}
duration = {1:1, 2:2, 3:3, 4:4 }
res=model.addResource("writer")
res.addCapacity(0,"inf",1)
act={}
mode={}
for i in duration:
    act[i]=model.addActivity(f"Act[{i}]", duedate=due[i], weight = 100 )
    mode[i]=Mode(f"Mode[{i}]",duration[i])
    mode[i,0] = Mode(f"Mode[{i}0]", 0 )
    mode[i].addResource(res,1)
    act[i].addModes(mode[i], mode[i,0])

con1 = model.addResource("constraint_1",rhs=0,direction = "<=", weight=1)
con1.addTerms(coeffs=[1,1,1,1], vars= [act[1],act[2],act[3],act[4]], values =[mode[1,0],mode[2,0],mode[3,0],mode[4,0]])

model.Params.TimeLimit=1
model.Params.OutputFlag=True
model.Params.Makespan=False
model.optimize()

例題21: 資源の優先利用の設定法

例題3の並列ショップスケジューリング問題で,3人のクルーに優先順位をつけたい.クルー1,2,3の順で優先度を1,2,3とする.

各クルーに割り振る作業数に1,2,3を乗じた値の合計を最小にする再生不能資源(制約)を付加する.

model=Model()
duration ={1:3, 2:2, 3:2, 4:2, 5:4, 6:4, 7:4, 8:4, 9:11, 10:2 }
res={}
for r in range(1,4):
    res[r] = model.addResource(f"worker{r}", capacity=1)
act={}
mode={}

for i in duration:
    act[i]=model.addActivity(f"Act[{i}]")
    for r in range(1,4):
        mode[i,r]=Mode(f"Mode[{i}{r}]", duration[i])
        mode[i,r].addResource(res[r],1)
        act[i].addModes(mode[i,r])
con={}
weight={1:1, 2:2, 3:3}
for r in range(1,4):
    con[r] = model.addResource(name=f"Constraint{r}", rhs=0, direction="<=", weight=weight[r])
    for i in duration:
        con[r].addTerms(1,act[i],mode[i,r])
        
model.addTemporal(act[1],act[9])
for i in range(5,9):
    model.addTemporal(act[4],act[i])
    model.addTemporal(act[i],act[10])
model.Params.TimeLimit=1
model.Params.OutputFlag=True
model.Params.Makespan=True
model.optimize()

例題22: Excel出力用の例題

例題4に再生不能資源を追加したものを考える.

model=Model()
duration ={1:3, 2:2, 3:2, 4:2, 5:4, 6:4, 7:4, 8:4, 9:11, 10:2 }
duedate = {1:3, 2:10, 3:10, 4:10, 5:10, 6:14, 7:14, 8:14, 9:11, 10:13 }
res=model.addResource("作業員", capacity=3)
act={}
mode={}

for i in duration:
    act[i]=model.addActivity(f"作業[{i}]", duedate=duedate[i])
    if i==1:
        mode[1,1]=Mode("モード[1_1]",3)
        mode[1,1].addResource(res,1)
        mode[1,2]=Mode("モード[1_2]",2)
        mode[1,2].addResource(res,2)
        mode[1,3]=Mode("モード[1_3]",1)
        mode[1,3].addResource(res,3)
        act[i].addModes(mode[1,1],mode[1,2],mode[1,3])
    else:
        mode[i]=Mode(f"モード[{i}]", duration[i])
        mode[i].addResource(res,1)
        act[i].addModes(mode[i])
        
model.addTemporal(act[1],act[9])
for i in range(5,9):
    model.addTemporal(act[4],act[i])
    model.addTemporal(act[i],act[10])

res=model.addResource("money",rhs=0,direction="<=",weight=1)
for i in range(1,4): #モードの費用(1日短縮に1万円)
    res.addTerms(i,act[1],mode[1,i])

model.Params.TimeLimit=1
model.Params.Makespan=False
model.optimize()
act_df, res_df, mode_df, act_mode_df, mode_res_df, temp_df, non_res_df, non_lhs_df, state_df = convert(model)
name ="ex22"
act_df.to_csv(folder+name+"_act.csv")
res_df.to_csv(folder+name+"_res.csv")
mode_df.to_csv(folder+name+"_mode.csv")
act_mode_df.to_csv(folder+name+"_act_mode.csv")
mode_res_df.to_csv(folder+name+"_mode_res.csv")
temp_df.to_csv(folder+name+"_temp.csv")
non_res_df.to_csv(folder+name+"_non_res.csv")
non_lhs_df.to_csv(folder+name+"_non_lhs.csv")
state_df.to_csv(folder+name+"_state.csv")

例題23: モードに依存した段取り時間

時間制約に対してモードに依存した時間制約を定義できる. この例では,先行作業と後続作業のモードに依存した時間遅れを入力する.

model = Model()
duration = {1: 13, 2: 25, 3: 15, 4: 27, 5: 22}
act = {}
mode = {}
res=model.addResource("worker",capacity=1)
for i in duration:
    act[i] = model.addActivity(f"Act[{i}]")
    mode[i,1] = Mode(f"Mode[{i},{1}]", duration[i])
    mode[i,2] = Mode(f"Mode[{i},{2}]", duration[i])
    mode[i,1].addResource(res,requirement=1)
    act[i].addModes(mode[i,1], mode[i,2])
        
# temporal constraints
model.addTemporal(act[1], act[2], delay = 20, pred_mode = mode[1,1], succ_mode =mode[2,1])
model.addTemporal(act[1], act[2], delay = 30, pred_mode = mode[1,2], succ_mode =mode[2,2])
model.addTemporal(act[1], act[2], delay = 40, pred_mode = mode[1,1], succ_mode = mode[2,2])
model.addTemporal(act[1], act[2], delay = 50, pred_mode = mode[1,2], succ_mode = mode[2,1])
model.addTemporal(act[1], act[2], delay = 20)
model.addTemporal(act[1], act[3], delay = 20)
model.addTemporal(act[2], act[4], delay=10)
model.addTemporal(act[2], act[5], delay = 8)
model.addTemporal(act[3], act[4], delay =10)
model.addTemporal("source", act[1], delay =5, succ_mode = mode[1,1])
model.addTemporal(act[4], "sink",  delay =5, pred_mode = mode[4,1])
model.addTemporal(act[4], "sink",  delay =15, pred_mode = mode[4,2])

model.Params.TimeLimit = 1
model.Params.Makespan = True
model.optimize(cloud=False)

例題24: 納期遅れに対する2次のペナルティ

納期遅れの例題(例題6)において,作業3の納期遅れペナルティを2乗関数にする.

model=Model()
due={1:5,2:9,3:6,4:4}
duration={1:1, 2:2, 3:3, 4:4 }

res=model.addResource("writer")
res.addCapacity(0, "inf", 1)

act={}
mode={}

for i in duration:
    if i==3:
        act[i]=model.addActivity(f"Act[{i}]", duedate=due[i], quadratic = True)
    else:
        act[i]=model.addActivity(f"Act[{i}]", duedate=due[i])
    mode[i]=Mode(f"Mode[{i}]", duration[i])
    mode[i].addResource(res,1)
    act[i].addModes(mode[i])

model.Params.TimeLimit=1
model.Params.OutputFlag=True
model.Params.Makespan=False
model.optimize()

例題25: 実践例 (1)

https://production-scheduling.com/education/tutorials/ からダウンロードした例題を解いて, システム作成の基本手順を示す.

durations = [7, 12, 4, 5, 8]
model = Model()
machine = model.addResource(capacity = 1)
act, mode = {},{}
for i,d in enumerate(durations):
    act[i] = model.addActivity(f"act[{i}]", duedate =24)
    mode[i] = Mode(f"Mode[{i}]", duration =d)
    mode[i].addResource(machine, 1)
    act[i].addModes(mode[i])
#print(model)
model.Params.TimeLimit=1
model.Params.OutputFlag = True
model.optimize()
 ================ Now solving the problem ================ 


output:
# reading data ... done: 0.00(s)
# random seed: 1
# tabu tenure: 1
# cpu time limit: 1.00(s)
# iteration limit: 1073741823
# computing all-pairs longest paths and strongly connected components ... done
#scc 7
objective value = 23 (cpu time = 0.00(s), iteration = 0)
0: 0.00(s): 23/23
objective value = 19 (cpu time = 0.00(s), iteration = 1)
objective value = 17 (cpu time = 0.00(s), iteration = 2)
objective value = 12 (cpu time = 0.00(s), iteration = 5)

--- best solution ---
source,---, 0 0
sink,---, 36 36
act[0],---, 4 4--11 11
act[1],---, 24 24--36 36
act[2],---, 0 0--4 4
act[3],---, 19 19--24 24
act[4],---, 11 11--19 19
--- tardy activity ---
act[1]: 12
--- resource residuals ---
__r0: [0,36] 0 

--- best activity list ---
source ---
act[2] ---
act[0] ---
act[4] ---
act[3] ---
act[1] ---
sink ---

objective value = 12
cpu time = 0.00/1.00(s)
iteration = 6/30443


Solutions:
    source   ---     0     0
      sink   ---    36    36
    act[0]   ---     4    11
    act[1]   ---    24    36
    act[2]   ---     0     4
    act[3]   ---    19    24
    act[4]   ---    11    19
visualize(model)
G cluster[act[0]] cluster[act[1]] cluster[act[2]] cluster[act[3]] cluster[act[4]] __r0 __r0 Mode[0] Mode[0] Mode[0]->__r0 act[0] act[0] act[0]->Mode[0] Mode[1] Mode[1] Mode[1]->__r0 act[1] act[1] act[1]->Mode[1] Mode[2] Mode[2] Mode[2]->__r0 act[2] act[2] act[2]->Mode[2] Mode[3] Mode[3] Mode[3]->__r0 act[3] act[3] act[3]->Mode[3] Mode[4] Mode[4] Mode[4]->__r0 act[4] act[4] act[4]->Mode[4]
model.write("sample.txt")
#Excel
model.writeExcel("sample.csv")
#Plotly
fig = make_gannt(model)
plotly.offline.plot(fig);
#Notion
import datetime as dt
start = dt.datetime.today()
df = make_gannt_for_notion(model,start=start,period="hours")
df.to_csv("gannt.csv")
for a in model.act:
    print(a.name, a.start, a.completion)

例題26: 実践例 (2)

https://production-scheduling.com/education/tutorials/ からダウンロードした例題を解いて, システム作成の基本手順を示す.

4つの作業を2つのワークセンターのいずれかで処理する. ワークセンター1よりワークセンター2の方が処理時間が短い. また,順序依存の段取り時間がかかり,段取りはワークセンター1の方が高速である.

初期状態は製品0を生産したものと仮定したとき,最大完了時刻を最小にする.

ワークセンターごとに状態変数を準備し, 作業の番号を状態とする. 段取り作業と本作業の両者を定義し, その間を時間制約でつなぐ.

model = Model()
n, m = 4, 2 #number of jobs and number of work centers
setup1 = [
    [0.00, 0.50, 0.50, 1.25],
    [2.00, 0.00, 0.75, 1.00],
    [2.00, 2.00, 0.00, 0.75],
    [2.10, 1.75, 1.50, 0.00]
]

setup2 = [
    [0.00, 1.25, 1.25, 2.75],
    [4.25, 0.00, 1.75, 2.50],
    [4.25, 4.25, 0.00, 1.75],
    [5.00, 4.50, 3.50, 0.00]
]

units_per_hour =[
    [80, 140],
    [55, 105],
    [72, 135],
    [65, 110]
]

quantity = [450, 650, 1500, 1300]

duration ={}
for i, q in enumerate(quantity):
    for j in range(m):
        duration[i,j] = int(q/units_per_hour[i][j] * 60)

act, mode, res, state= {},{},{},{}
for j in range(m):
    res[j] = model.addResource(name=f"wc[{j}]", capacity = 1)
    state[j] = model.addState(name=f"state[{j}]") 
    state[j].addValue(time=0, value=0) #both work centers are now producing A
    
mode_setup = {}
for j in range(m):    
    for i in range(n):
        for k in range(n):
            if j==0:
                setuptime = int(setup1[i][k]*60)
            else:
                setuptime = int(setup2[i][k]*60)
            mode_setup[i, k, j] = Mode(f"Mode_setup[{i},{k},{j}]", setuptime )
            mode_setup[i, k, j].addState(state[j], i, k)
            if setuptime >0:
                mode_setup[i, k, j].addResource(res[j], 1 )

act_setup = {}
for k in range(n):
    act_setup[k] = model.addActivity(f"Setup[{k}]", autoselect=True)
    for i in range(n):
        for j in range(m):
            act_setup[k].addModes(mode_setup[i, k, j])

for i in range(n):
    act[i] = model.addActivity(f"act[{i}]")
    for j in range(m):
        mode[i,j] = Mode(f"Mode[{i},{j}]", duration= duration[i,j])
        mode[i,j].addResource(res[j], 1)
        mode[i, j].addState(state[j], i, i)
    act[i].addModes(*[mode[i,j] for j in range(m)])    

for i in range(n):
   model.addTemporal(act_setup[i], act[i], "CS")
   model.addTemporal(act[i], act_setup[i], "SC")
#print(model)
model.Params.TimeLimit=1
model.Params.OutputFlag = True
model.Params.Makespan = True
model.optimize()
 ================ Now solving the problem ================ 


output:
# reading data ... done: 0.00(s)
# random seed: 1
# tabu tenure: 1
# cpu time limit: 1.00(s)
# iteration limit: 1073741823
# computing all-pairs longest paths and strongly connected components ... done
#scc 6
objective value = 1000000004 (cpu time = 0.00(s), iteration = 0)
0: 0.00(s): 1000000004/1000000004
objective value = 2134 (cpu time = 0.01(s), iteration = 1)
objective value = 1497 (cpu time = 0.01(s), iteration = 7)
objective value = 1409 (cpu time = 0.17(s), iteration = 125)

--- best solution ---
source,---, 0 0
sink,---, 1409 1409
Setup[0],Mode_setup[0_0_0], 0 0
Setup[1],Mode_setup[0_1_1], 192 192--267 267
Setup[2],Mode_setup[1_2_1], 638 638--743 743
Setup[3],Mode_setup[0_3_0], 1 1--76 76
act[0],Mode[0_1], 0 0--192 192
act[1],Mode[1_1], 267 267--638 638
act[2],Mode[2_1], 743 743--1409 1409
act[3],Mode[3_0], 76 76--1276 1276
--- tardy activity ---
sink: 1409
--- resource residuals ---
wc[0]: [0,1] 1 [1,1276] 0 [1276,4611686018427387903] 1 
wc[1]: [0,1409] 0 

--- best activity list ---
source ---
Setup[0] Mode_setup[0_0_0]
act[0] Mode[0_1]
Setup[3] Mode_setup[0_3_0]
act[3] Mode[3_0]
Setup[1] Mode_setup[0_1_1]
act[1] Mode[1_1]
Setup[2] Mode_setup[1_2_1]
act[2] Mode[2_1]
sink ---

objective value = 1409
cpu time = 0.17/1.00(s)
iteration = 126/786


Solutions:
    source   ---     0     0
      sink   ---  1409  1409
  Setup[0] Mode_setup[0_0_0]     0     0
  Setup[1] Mode_setup[0_1_1]   192   267
  Setup[2] Mode_setup[1_2_1]   638   743
  Setup[3] Mode_setup[0_3_0]     1    76
    act[0] Mode[0_1]     0   192
    act[1] Mode[1_1]   267   638
    act[2] Mode[2_1]   743  1409
    act[3] Mode[3_0]    76  1276
visualize(model)
G cluster[Setup[0]] cluster[Setup[1]] cluster[Setup[2]] cluster[Setup[3]] cluster[act[0]] cluster[act[1]] cluster[act[2]] cluster[act[3]] wc[0] wc[0] wc[1] wc[1] Mode_setup[1_0_0] Mode_setup[1_0_0] Mode_setup[1_0_0]->wc[0] Mode_setup[1_0_1] Mode_setup[1_0_1] Mode_setup[1_0_1]->wc[1] Mode_setup[2_0_0] Mode_setup[2_0_0] Mode_setup[2_0_0]->wc[0] Mode_setup[2_0_1] Mode_setup[2_0_1] Mode_setup[2_0_1]->wc[1] Mode_setup[3_0_0] Mode_setup[3_0_0] Mode_setup[3_0_0]->wc[0] Mode_setup[3_0_1] Mode_setup[3_0_1] Mode_setup[3_0_1]->wc[1] Setup[0] Setup[0] Setup[0]->Mode_setup[1_0_0] Setup[0]->Mode_setup[1_0_1] Setup[0]->Mode_setup[2_0_0] Setup[0]->Mode_setup[2_0_1] Setup[0]->Mode_setup[3_0_0] Setup[0]->Mode_setup[3_0_1] Mode_setup[0_0_0] Mode_setup[0_0_0] Setup[0]->Mode_setup[0_0_0] Mode_setup[0_0_1] Mode_setup[0_0_1] Setup[0]->Mode_setup[0_0_1] act[0] act[0] Setup[0]->act[0] Mode_setup[0_1_0] Mode_setup[0_1_0] Mode_setup[0_1_0]->wc[0] Mode_setup[0_1_1] Mode_setup[0_1_1] Mode_setup[0_1_1]->wc[1] Mode_setup[2_1_0] Mode_setup[2_1_0] Mode_setup[2_1_0]->wc[0] Mode_setup[2_1_1] Mode_setup[2_1_1] Mode_setup[2_1_1]->wc[1] Mode_setup[3_1_0] Mode_setup[3_1_0] Mode_setup[3_1_0]->wc[0] Mode_setup[3_1_1] Mode_setup[3_1_1] Mode_setup[3_1_1]->wc[1] Setup[1] Setup[1] Setup[1]->Mode_setup[0_1_0] Setup[1]->Mode_setup[0_1_1] Setup[1]->Mode_setup[2_1_0] Setup[1]->Mode_setup[2_1_1] Setup[1]->Mode_setup[3_1_0] Setup[1]->Mode_setup[3_1_1] Mode_setup[1_1_0] Mode_setup[1_1_0] Setup[1]->Mode_setup[1_1_0] Mode_setup[1_1_1] Mode_setup[1_1_1] Setup[1]->Mode_setup[1_1_1] act[1] act[1] Setup[1]->act[1] Mode_setup[0_2_0] Mode_setup[0_2_0] Mode_setup[0_2_0]->wc[0] Mode_setup[0_2_1] Mode_setup[0_2_1] Mode_setup[0_2_1]->wc[1] Mode_setup[1_2_0] Mode_setup[1_2_0] Mode_setup[1_2_0]->wc[0] Mode_setup[1_2_1] Mode_setup[1_2_1] Mode_setup[1_2_1]->wc[1] Mode_setup[3_2_0] Mode_setup[3_2_0] Mode_setup[3_2_0]->wc[0] Mode_setup[3_2_1] Mode_setup[3_2_1] Mode_setup[3_2_1]->wc[1] Setup[2] Setup[2] Setup[2]->Mode_setup[0_2_0] Setup[2]->Mode_setup[0_2_1] Setup[2]->Mode_setup[1_2_0] Setup[2]->Mode_setup[1_2_1] Setup[2]->Mode_setup[3_2_0] Setup[2]->Mode_setup[3_2_1] Mode_setup[2_2_0] Mode_setup[2_2_0] Setup[2]->Mode_setup[2_2_0] Mode_setup[2_2_1] Mode_setup[2_2_1] Setup[2]->Mode_setup[2_2_1] act[2] act[2] Setup[2]->act[2] Mode_setup[0_3_0] Mode_setup[0_3_0] Mode_setup[0_3_0]->wc[0] Mode_setup[0_3_1] Mode_setup[0_3_1] Mode_setup[0_3_1]->wc[1] Mode_setup[1_3_0] Mode_setup[1_3_0] Mode_setup[1_3_0]->wc[0] Mode_setup[1_3_1] Mode_setup[1_3_1] Mode_setup[1_3_1]->wc[1] Mode_setup[2_3_0] Mode_setup[2_3_0] Mode_setup[2_3_0]->wc[0] Mode_setup[2_3_1] Mode_setup[2_3_1] Mode_setup[2_3_1]->wc[1] Setup[3] Setup[3] Setup[3]->Mode_setup[0_3_0] Setup[3]->Mode_setup[0_3_1] Setup[3]->Mode_setup[1_3_0] Setup[3]->Mode_setup[1_3_1] Setup[3]->Mode_setup[2_3_0] Setup[3]->Mode_setup[2_3_1] Mode_setup[3_3_0] Mode_setup[3_3_0] Setup[3]->Mode_setup[3_3_0] Mode_setup[3_3_1] Mode_setup[3_3_1] Setup[3]->Mode_setup[3_3_1] act[3] act[3] Setup[3]->act[3] Mode[0_0] Mode[0_0] Mode[0_0]->wc[0] Mode[0_1] Mode[0_1] Mode[0_1]->wc[1] act[0]->Setup[0] SC act[0]->Mode[0_0] act[0]->Mode[0_1] Mode[1_0] Mode[1_0] Mode[1_0]->wc[0] Mode[1_1] Mode[1_1] Mode[1_1]->wc[1] act[1]->Setup[1] SC act[1]->Mode[1_0] act[1]->Mode[1_1] Mode[2_0] Mode[2_0] Mode[2_0]->wc[0] Mode[2_1] Mode[2_1] Mode[2_1]->wc[1] act[2]->Setup[2] SC act[2]->Mode[2_0] act[2]->Mode[2_1] Mode[3_0] Mode[3_0] Mode[3_0]->wc[0] Mode[3_1] Mode[3_1] Mode[3_1]->wc[1] act[3]->Setup[3] SC act[3]->Mode[3_0] act[3]->Mode[3_1]
fig = make_gannt(model)
plotly.offline.plot(fig);
make_result_df(model)

例題27: 配送計画問題

運搬車の現在地点を状態とすることによって,(最大完了時刻の最小化を目的とした)配送計画問題を解くことができる. この問題は, 巡回修理人問題 (traveling repairman problem)の拡張と考えられる. このテクニックを使うことによって, 資源が地点間を移動するタイプのスケジューリング問題のモデル化が可能になる.

以下の例では,運搬車の容量は考慮していないが,各作業の前に伸び縮みするダミーの作業を配置し,開始時刻を $0$ に,終了時刻を作業の開始時刻に固定し, ダミーの作業が資源を使用すると定義することによってモデル化することができる.

5つの地点(0,1,2,3,4)を2台の運搬車で巡回することを考える. 点 $0$ をデポとする. 最後の顧客への訪問時刻を最小化するための,各運搬車の巡回順を求める.

n = 5 #number of nodes
m = 2 #number of vehicles
# travel time
D = [ [0,1,1,1,1],
      [1,0,1,2,3],
      [1,1,0,1,2],
      [1,2,1,0,1],
      [1,3,2,1,0] ]
model = Model()
state = {}    #状態
resource ={ }
for k in range(m):
    state[k] = model.addState(f"State{k}")
    state[k].addValue(time=0, value =0) #開始時刻には点 0 (デポ)にいる
    resource[k] = model.addResource(f"vehicle{k}", 1)
act = {}
mode_move = {}
for j in range(n):
    if j==0:
        continue
    act[j] = model.addActivity(f"Act[{j}]", autoselect=True)
    for i in range(n):
        if i==j: 
            continue
        for k in range(m):
            mode_move[i, j, k] = Mode(f"Mode_move[{i},{j},{k}]", D[i][j] )
            mode_move[i, j, k].addState(state[k], i, j)
            mode_move[i, j, k].addResource(resource[k], 1)
            act[j].addModes(mode_move[i,j,k])
model.optimize()
 ================ Now solving the problem ================ 


Solutions:
    source   ---     0     0
      sink   ---     2     2
    Act[1] Mode_move[0_1_0]     0     1
    Act[2] Mode_move[1_2_0]     1     2
    Act[3] Mode_move[4_3_1]     1     2
    Act[4] Mode_move[0_4_1]     0     1
visualize(model)
G cluster[Act[1]] cluster[Act[2]] cluster[Act[3]] cluster[Act[4]] vehicle0 vehicle0 vehicle1 vehicle1 Mode_move[0_1_0] Mode_move[0_1_0] Mode_move[0_1_0]->vehicle0 Mode_move[0_1_1] Mode_move[0_1_1] Mode_move[0_1_1]->vehicle1 Mode_move[2_1_0] Mode_move[2_1_0] Mode_move[2_1_0]->vehicle0 Mode_move[2_1_1] Mode_move[2_1_1] Mode_move[2_1_1]->vehicle1 Mode_move[3_1_0] Mode_move[3_1_0] Mode_move[3_1_0]->vehicle0 Mode_move[3_1_1] Mode_move[3_1_1] Mode_move[3_1_1]->vehicle1 Mode_move[4_1_0] Mode_move[4_1_0] Mode_move[4_1_0]->vehicle0 Mode_move[4_1_1] Mode_move[4_1_1] Mode_move[4_1_1]->vehicle1 Act[1] Act[1] Act[1]->Mode_move[0_1_0] Act[1]->Mode_move[0_1_1] Act[1]->Mode_move[2_1_0] Act[1]->Mode_move[2_1_1] Act[1]->Mode_move[3_1_0] Act[1]->Mode_move[3_1_1] Act[1]->Mode_move[4_1_0] Act[1]->Mode_move[4_1_1] Mode_move[0_2_0] Mode_move[0_2_0] Mode_move[0_2_0]->vehicle0 Mode_move[0_2_1] Mode_move[0_2_1] Mode_move[0_2_1]->vehicle1 Mode_move[1_2_0] Mode_move[1_2_0] Mode_move[1_2_0]->vehicle0 Mode_move[1_2_1] Mode_move[1_2_1] Mode_move[1_2_1]->vehicle1 Mode_move[3_2_0] Mode_move[3_2_0] Mode_move[3_2_0]->vehicle0 Mode_move[3_2_1] Mode_move[3_2_1] Mode_move[3_2_1]->vehicle1 Mode_move[4_2_0] Mode_move[4_2_0] Mode_move[4_2_0]->vehicle0 Mode_move[4_2_1] Mode_move[4_2_1] Mode_move[4_2_1]->vehicle1 Act[2] Act[2] Act[2]->Mode_move[0_2_0] Act[2]->Mode_move[0_2_1] Act[2]->Mode_move[1_2_0] Act[2]->Mode_move[1_2_1] Act[2]->Mode_move[3_2_0] Act[2]->Mode_move[3_2_1] Act[2]->Mode_move[4_2_0] Act[2]->Mode_move[4_2_1] Mode_move[0_3_0] Mode_move[0_3_0] Mode_move[0_3_0]->vehicle0 Mode_move[0_3_1] Mode_move[0_3_1] Mode_move[0_3_1]->vehicle1 Mode_move[1_3_0] Mode_move[1_3_0] Mode_move[1_3_0]->vehicle0 Mode_move[1_3_1] Mode_move[1_3_1] Mode_move[1_3_1]->vehicle1 Mode_move[2_3_0] Mode_move[2_3_0] Mode_move[2_3_0]->vehicle0 Mode_move[2_3_1] Mode_move[2_3_1] Mode_move[2_3_1]->vehicle1 Mode_move[4_3_0] Mode_move[4_3_0] Mode_move[4_3_0]->vehicle0 Mode_move[4_3_1] Mode_move[4_3_1] Mode_move[4_3_1]->vehicle1 Act[3] Act[3] Act[3]->Mode_move[0_3_0] Act[3]->Mode_move[0_3_1] Act[3]->Mode_move[1_3_0] Act[3]->Mode_move[1_3_1] Act[3]->Mode_move[2_3_0] Act[3]->Mode_move[2_3_1] Act[3]->Mode_move[4_3_0] Act[3]->Mode_move[4_3_1] Mode_move[0_4_0] Mode_move[0_4_0] Mode_move[0_4_0]->vehicle0 Mode_move[0_4_1] Mode_move[0_4_1] Mode_move[0_4_1]->vehicle1 Mode_move[1_4_0] Mode_move[1_4_0] Mode_move[1_4_0]->vehicle0 Mode_move[1_4_1] Mode_move[1_4_1] Mode_move[1_4_1]->vehicle1 Mode_move[2_4_0] Mode_move[2_4_0] Mode_move[2_4_0]->vehicle0 Mode_move[2_4_1] Mode_move[2_4_1] Mode_move[2_4_1]->vehicle1 Mode_move[3_4_0] Mode_move[3_4_0] Mode_move[3_4_0]->vehicle0 Mode_move[3_4_1] Mode_move[3_4_1] Mode_move[3_4_1]->vehicle1 Act[4] Act[4] Act[4]->Mode_move[0_4_0] Act[4]->Mode_move[0_4_1] Act[4]->Mode_move[1_4_0] Act[4]->Mode_move[1_4_1] Act[4]->Mode_move[2_4_0] Act[4]->Mode_move[2_4_1] Act[4]->Mode_move[3_4_0] Act[4]->Mode_move[3_4_1]

例題28: リスケジューリング

モデルのパラメータ model.Params のInitialをTrueにすると,前回求解したときの最良解を初期値とした探索を行うことができる. 最良解の情報は作業の順序と選択されたモードとしてファイル名 optseq_best_act_data.txtに保管されている. このファイルを書き換えることによって,異なる初期解から探索を行うことも可能である.

例として,例題15で用いたジョブショップスケジューリング問題を用いる.

最初の最適化は10秒の制限時間で求解するが,2回目はパラメータ Initial をTrueにし,前回の最良解を初期値として探索するため,制限時間1秒で最適解に到達する.

model = ex15("../data/optseq/ft06.txt")
model.Params.OutputFlag = True 
model.Params.TimeLimit = 10
model.optimize()

model.Params.TimeLimit = 1
model.Params.Initial = True #前回の最適順序の情報を用いてリスケジューリング
model.optimize()

デバッグのコツ

ここでは,デバッグのコツについて述べる.

OptSeqでは,(モデルを含む)すべてのオブジェクトをprint関数で表示することができる. プログラムを少しずつ書き, printでオブジェクトが意図通りになっているかを出力して確認することが重要である.

例として例題1に変更を加えた以下の例題を考える

model = Model()
duration = {1: 13.5, 2: 25, 3: 15, 4: 27, 5: 22}
act = {}
mode = {}
for i in duration:
    act[i] = model.addActivity("Act[{0}]".format(i))
    mode[i] = Mode("Mode[{0}]".format(i), duration[i])
    act[i].addModes(mode[i])

mode[1].addParallel(1,1,3.5)

# temporal (precedense) constraints
model.addTemporal(act[1], act[3])
model.addTemporal(act[2], act[4])
model.addTemporal(act[2], act[5])
model.addTemporal(act[3], act[4])

model.Params.TimeLimit = 1
model.Params.Makespan = True
model.optimize()

これをそのまま実行すると "infeasible solution" と表示される. これは,答えが見つからないことを意味する.

OptSeqは,Pythonからテキストファイルを生成して,それを実行ファイルに入れて求解する.入力ファイル名は optseq_input.txt で出力ファイル名は optseq_output.txt である. まずは,出力ファイルを適当なテキストエディタで開いてみると,以下のようになっていることが確認できる.

# reading data ...
line 2: parse error befor/at `.'

no feasible schedule found.

これは,入力データの2行目にエラーがあることを示している.入力ファイルを開くと,以下のようになっている.

activity Act[1] 
 mode  duration 13.5   
activity Act[2] 
 mode  duration 25   
activity Act[3] 
 mode  duration 15   
activity Act[4] 
 mode  duration 27   
activity Act[5] 
 mode  duration 22   
temporal Act[1] Act[3]  type CS delay 0  
temporal Act[2] Act[4]  type CS delay 0  
temporal Act[2] Act[5]  type CS delay 0  
temporal Act[3] Act[4]  type CS delay 0  
activity sink duedate 0

2行目 duration が13.5と小数になっている.OptSeqにおける数値はすべて整数である必要がある.小数を整数に直して解き直してみると最適解55が得られる.

ここでは,小さい例題でデバッグしたが,実際の問題を解く場合でも,簡単な例からはじめて徐々に問題を複雑化していくことを推奨する.

ターミナル(コマンドプロンプト)での実行

デバッグ時だけでなく, 大規模問題例を解くときや,アルゴリズムのログを確認しながら実験したい場合には,ターミナル(コマンドプロンプト)からの実行を推奨する.

コマンドはOSによって異なるが,optseq-mac (Mac), optseq-linux (linux), optseq (Windows) を以下の形式で実行する.

./optseq-mac   < optseq_input.txt
./optseq-linux < optseq_input.txt
optseq         < optseq_input.txt

オプションの引数は, 「-オプション名 引数」の形式で追加する. optseq --help で表示されるオプションは,以下の通りである.

-backtrack #                     set max number of backtrack (default: 1000)
-data                                                   print input data and terminate immediately
-initial f                               set initial solution file (default: not specified)
-iteration #                     set iteration limit (default: 18446744073709551615)
-neighborhood #         set neighborhood size (default: 20)
-report #                                       set report interval (default: 18446744073709551615)
-seed #                                         set random seed (default: 1)
-tenure #                                       set tabu tenure (default: 1)
-time #                                         set cpu time limit in second (default: 600)
-weightcontrol #         set weight control interval (default: 20)

たとえば,実行時のログを1反復ごとに表示させたい場合には,

./optseq-mac   -report 1 < optseq_input.txt
./optseq-linux -report 1 < optseq_input.txt
optseq         -report 1 < optseq_input.txt

とすれば良い.

練習問題

練習問題 1:楽観値と悲観値

以下ような作業に対して,問いに答えよ.

先行作業と作業時間(楽観値,平均値,悲観値)
作業名 先行作業 楽観値 平均値 悲観値
A なし 1 2 3
B なし 2 3 4
C A 1 2 3
D B 2 4 6
E C 1 4 7
F C 1 2 3
G D,E 3 4 5
H F,G 1 2 3
  • 作業時間の楽観値に対して作業 H が完了する最早時刻を求めよ.
  • 作業時間の平均値に対して作業 H が完了する最早時刻を求めよ.
  • 作業時間の悲観値に対して作業 H が完了する最早時刻を求めよ.
  • 作業時間が楽観値と悲観値の間の一様分布と仮定したときの,作業 H が完了する最早時刻の分布をmatplotlibを用いて描け.

練習問題 2:並列ショップ(改)

例題3の並列ショップスケジューリングの例題に対して,以下のような変更を行ったときのスケジュールを求めよ.

  1. 作業員4人で作業を行うとした場合
  2. 作業間の時間制約をなくしたと仮定した場合
  3. 作業時間をすべて $1$秒短縮したと仮定した場合

練習問題 3:お家を造ろう(改)

例題5の資源制約付きスケジューリングの例題に対して, 2階を建てる作業(作業時間は2人で2日)と, 2階の内装を行う作業(作業時間は1人で2日)を追加した場合のスケジュールを求めよ. ただし,2階を建てる作業は,1階の壁を取り付けた後でないと開始できず, 屋根の取り付けと2階の内装は,2階を建てた後でないと開始できないものと仮定する.

練習問題 4:クリティカルパス法(改)

例題7で,作業時間と短縮したときの費用が,以下のように設定されている場合を考え,予算が $0$ から $4$万円に 変化したときの最早完了時刻を求めよ.

  • 作業1: 乗客降ろし $13$ 分.$12$ 分に短縮可能で,$1$ 万円必要.$11$ 分に短縮するには,さらに $1$ 万円必要.
  • 作業2: 荷物降ろし $25$ 分.$23$ 分に短縮可能で,$1$ 万円必要.$21$ 分に短縮するには,さらに $1$ 万円必要.
  • 作業3: 機内清掃 $15$ 分.$13$ 分に短縮可能で, $1$ 万円必要.$11$ 分に短縮するには,さらに $1$ 万円必要.
  • 作業4: 新しい乗客の搭乗 $27$ 分.$26$ 分に短縮可能で, $1$ 万円必要.$25$ 分に短縮するには,さらに $1$ 万円必要.
  • 作業5: 新しい荷物の積み込み $22$ 分.$21$ 分に短縮可能で,$1$ 万円必要.$20$ 分に短縮するには,さらに $1$ 万円必要.

練習問題 5: 重み付き納期遅れ和

あなたは6つの異なる得意先から製品の製造を依頼された製造部長だ. 製品の製造は特注であり,それぞれ $1,4,2,3,1,4$ 日の製造日数がかかる. ただし,製品の製造に必要な材料の到着する日は,それぞれ $4,0,2,4,1,5$ 日後と決まっている. 得意先には上得意とそうでもないものが混在しており,それぞれの重要度は $3,1,2,3,1,2$ と推定されている.製品が完成する日数に重みを乗じたものの和を なるべく小さくするように社長に命令されているが,さてどのような順序で 製品を製造したら良いのだろう?

練習問題 6: 途中中断と並列処理

例題3の並列ショップスケジューリングに対して,以下のような変更を行ったときのスケジュールを求めよ.

  1. すべての作業が途中中断可能と仮定した場合
  2. すべての作業が並列処理可能と仮定した場合

練習問題 7:日本食レストラン

あなたは日本食レストランのオーナーだ. あなたは,明日の元旦に向けて,3人のお客様に特製おせち料理を出さなければならない. この特製おせちは,3人の料理人の流れ作業によって作られる. 最初の料理人は包丁担当で,これは彼ならではのテクニックで材料を切り刻む. 2番目の料理人は煮込み担当で,3番目の料理人は飾り付け担当だ. 当然,流れ作業なので,切りの後に煮込み,煮込みの後に飾り付けが行われ, 作業の途中中断はできないものと仮定する. それぞれの工程の作業時間は,以下のようになっている. さて,どのようにしたらなるべく早く料理を終えることができるだろうか?

工程の作業時間 (単位は時間)
お客さんの番号 1 2 3
包丁担当の作業時間 2 4 1
煮込み担当の作業時間 3 2 4
飾り付け担当の作業時間 1 3 1

練習問題8: フローショップスケジューリング問題のベンチマーク問題例

例題15のジョブショップスケジューリング問題において, 各ジョブのオペレーション数が機械の台数 $m$ と一致し, 各ジョブ $J_j$ のオペレーションが $O_{1j},O_{2j},\cdots,O_{mj}$ の順で処理されなけばならず, かつ各オペレーションが処理される機械がすべて異なり,かつその順序が同一のとき,フローショップスケジューリング問題とよばれる.

OR-Lib.(http://people.brunel.ac.uk/~mastjjb/jeb/orlib/flowshopinfo.html) にあるベンチマーク問題例を読み込んで解け.

たとえば,Carlier 11x5 の問題例(ファイル名はcar1.txt)は,以下のようなデータである.

 11 5
 0 375 1  12 2 142 3 245 4 412
 0 632 1 452 2 758 3 278 4 398
 0  12 1 876 2 124 3 534 4 765
 0 460 1 542 2 523 3 120 4 499
 0 528 1 101 2 789 3 124 4 999
 0 796 1 245 2 632 3 375 4 123
 0 532 1 230 2 543 3 896 4 452
 0  14 1 124 2 214 3 543 4 785
 0 257 1 527 2 753 3 210 4 463
 0 896 1 896 2 214 3 258 4 259
 0 532 1 302 2 501 3 765 4 988

データの説明は以下の通り.

Each instance consists of a line of description, a line containing the 
number of jobs and the number of machines, and then one line for each job,
listing the machine number and processing time for each step of the job. 
The machines are numbered starting with 0.

注意: この問題はトライアル版では解けない.

練習問題9: オープンショップスケジューリング問題のベンチマーク問題例

例題15のジョブショップスケジューリング問題において,各ジョブ $J_j$ のオペレーションが処理される機械がすべて異なり, $J_j$ のオペレーション $O_{1j},O_{2j},\cdots,O_{mj}$ の処理順があらかじめ決められていないとき,オープンショップスケジューリング問題とよばれる.

http://mistic.heig-vd.ch/taillard/problemes.dir/ordonnancement.dir/ordonnancement.html にあるベンチマーク問題例を読み込んで解け.

たとえば,最も小さい問題例(ファイル名はtail04.txt)は,以下のようなデータである.

number of jobs, number of machines, time seed, machine seed, upper bound, lower bound :
           4           4  1166510396   164000672         193         186
processing times :
 54 34 61  2
  9 15 89 70
 38 19 28 87
 95 34  7 29

何故か下界より良い解を得てしまう.元の論文にバグがあるのかもしれない.

注意: この問題はトライアル版では解けない.

モデルオブジェクトをデータフレームに変換する関数 convert

注)この関数はSCMOPTに含まれるスケジューリング最適化システム用関数です.ソルバー版のOptSeqでは利用できません.

モデルを入れると、以下のデータフレームを返す関数を準備する。

引数:

  • OptSeqのモデルオブジェクト

返値:

OptSeqのデータを格納したデータフレーム群

  • act_df : 作業データフレーム
  • res_df : 資源データフレーム
  • mode_df : モードデータフレーム
  • act_mode_df : 作業・モードデータフレーム
  • mode_res_df : モード・資源データフレーム
  • temp_df : 時間制約データフレーム
  • non_res_df : 再生不能資源の右辺定数と制約の向きを表すデータフレーム
  • non_lhs_df : 再生不能資源の項(係数、作業、モードの組)を表すデータフレーム
  • state_df : 状態データフレーム

convert[source]

convert(model)

convert OptSeq model object to dataframes

convert関数の使用例

model = ex1()
act_df, res_df, mode_df, act_mode_df, mode_res_df, temp_df, non_res_df, non_lhs_df, state_df = convert(model)
act_df.head()

全ての例題のデータフレームをcsvファイルに出力

folder = "../data/optseq/"
ex_list = [ ex1(), ex2(), ex3(), ex4(), ex5(), ex6(), ex7(), ex8(), ex9(), ex10(), 
           ex11(), ex12(), ex13(), ex14(),  ex15(),  ex16(), ex16(), ex17(), ex18(), ex19(), ex20()  ]
#ex_list = [ ex1() ]
ex_name =[ "ex"+str(i) for i in range(1,21)  ]
for name, ex in zip(ex_name, ex_list):
    model = ex
    act_df, res_df, mode_df, act_mode_df, mode_res_df, temp_df, non_res_df, non_lhs_df, state_df = convert(model)
    
    act_df.to_csv(folder+name+"_act.csv")
    res_df.to_csv(folder+name+"_res.csv")
    mode_df.to_csv(folder+name+"_mode.csv")
    act_mode_df.to_csv(folder+name+"_act_mode.csv")
    mode_res_df.to_csv(folder+name+"_mode_res.csv")
    temp_df.to_csv(folder+name+"_temp.csv")
    non_res_df.to_csv(folder+name+"_non_res.csv")
    non_lhs_df.to_csv(folder+name+"_non_lhs.csv")
    state_df.to_csv(folder+name+"_state.csv")

データフレームの列名の解説

上で生成したcsvファイルから生成されるデータフレームを示し,列の意味を解説する.

作業データ

作業の属性を保管

  • name: 作業名
  • duedate: 納期
  • backward: 後詰めのときtrue
  • weight:納期遅れペナルティ
  • autoselect: 状態変数を使っているとき true
name ="ex11"
pd.read_csv(folder+name+"_act.csv", index_col=0).head()

モードデータ

作業の実行法

  • name: モード名
  • duration: 作業時間
  • brekable: 途中中断情報を表す
  • parallel: 並列実行を表す
  • state: モードによる状態変化を表す
pd.read_csv(folder+name+"_mode.csv", index_col=0).head()

資源データ

資源の容量

  • name: 資源名
  • capacity: 資源使用可能量上限を表す
pd.read_csv(folder+name+"_res.csv", index_col=0).head()

作業・モードデータ

作業とモードの関係

  • activity: 作業名
  • mode: モード名
pd.read_csv(folder+name+"_act_mode.csv", index_col=0).head()

モード・資源データ

モードの資源使用量

  • mode: モード名
  • resource: 資源名
  • type: 資源タイプ; 通常の資源(nan)か中断中(‘break’)か並列実行時の最大量(‘max’)を入れる
  • requirement : 資源必要量
pd.read_csv(folder+name+"_mode_res.csv", index_col=0).head()

時間制約データ

作業間の時間制約

  • pred: 先行作業
  • succ: 後続作業
  • type: 時間制約タイプ;'SS'(開始,開始),'SC'(開始,完了),'CS'(完了,開始),'CC'(完了,完了)のいずれか
  • delay: 時間遅れ
pd.read_csv(folder+name+"_temp.csv", index_col=0).head()

再生不能資源(制約)データ

作業のモード割り当てに対する線形制約

  • name: 再生不能資源名
  • rhs: 右辺定数
  • direction: 制約の向き; '<=', '>=', '='のいずれか
  • weight: 制約逸脱ペナルティ
pd.read_csv(folder+name+"_non_res.csv", index_col=0)

再生不能資源(制約)左辺データ

作業のモード割り当てに対する線形制約の左辺情報

  • res_name: 再生不能資源名
  • term: 係数
  • act_name: 作業名
  • mode: モード名
pd.read_csv(folder+name+"_non_lhs.csv", index_col=0)

状態データ

状態の定義

  • state_name:状態名
  • time_value: 時刻における状態値の情報
name = "ex13"
pd.read_csv(folder+name+"_state.csv", index_col=0)

最適化関数 optimize_optseq

注)この関数はSCMOPTに含まれるスケジューリング最適化システム用関数です.ソルバー版のOptSeqでは利用できません.

与えられたデータを元に、スケジューリング最適化を行う関数

引数:

  • makespan : Trueのとき最大完了時刻(メイクスパン)を最小化し、Falseのとき、重み付き納期遅れペナルティの和を最小化する。
  • cpu : 最大計算時間
  • act_df : 作業データフレーム
  • res_df : 資源データフレーム
  • mode_df : モードデータフレーム
  • act_mode_df : 作業・モードデータフレーム
  • mode_res_df : モード・資源データフレーム
  • temp_df : 時間制約データフレーム
  • non_res_df : 再生不能資源の右辺定数と制約の向きを表すデータフレーム
  • non_lhs_df : 再生不能資源の項(係数、作業、モードの組)を表すデータフレーム
  • state_df : 状態データフレーム

返値:

  • model: モデルオブジェクト

optimize_optseq[source]

optimize_optseq(makespan, cpu, act_df, mode_df, res_df, act_mode_df, mode_res_df, temp_df, non_res_df=None, non_lhs_df=None, state_df=None, cloud=False)

make a model and optimize using: act_df,res_df,mode_df,act_mode_df,mode_res_df,temp_df, non_res_df, non_lhs_df, state_df

optimize_optseq関数の使用例

計算時間1秒で、例題1を最小化する。

model = ex1()
num = 1 
act_df, res_df, mode_df, act_mode_df, mode_res_df, temp_df, non_res_df, non_lhs_df, state_df = convert(model)
# act_df = pd.read_csv(folder + f"ex{num}_act.csv", index_col=0)
# mode_df = pd.read_csv(folder + f"ex{num}_act.csv", index_col=0)
# res_df = pd.read_csv(folder + f"ex{num}_res.csv", index_col=0)
# mode_res_df = pd.read_csv(folder + f"ex{num}_mode_res.csv", index_col=0)
model = optimize_optseq(1,1,act_df,mode_df, res_df, act_mode_df, mode_res_df, temp_df,cloud=True)

最適化の結果を入れたデータフレームを返す関数 make_result_df

注)この関数はSCMOPTに含まれるスケジューリング最適化システム用関数です.ソルバー版のOptSeqでは利用できません.

make_result_df[source]

make_result_df(model)

最適化した結果を入れたデータフレームを生成する関数

make_result_df関数の使用例

result_df = make_result_df(model)
result_df.head()

Excel簡易インターフェイス

プロジェクトスケジューリング用のExcel簡易入力テンプレートを出力する関数 optseq_project_excel

注)この関数はSCMOPTに含まれるスケジューリング最適化システム用関数です.ソルバー版のOptSeqでは利用できません.

optseq_project_excel[source]

optseq_project_excel(res_list)

res_list =[ {"resource_name": "機械", "seq_dependent": True}, {"resource_name": "作業員", "seq_dependent": False} ] 
wb = optseq_project_excel(res_list)
wb.save("optseq-project.xlsx")

生産スケジューリング optseq_production_excel

注)この関数はSCMOPTに含まれるスケジューリング最適化システム用関数です.ソルバー版のOptSeqでは利用できません.

生産スケジューリングの場合のExcelテンプレートを生成する関数

返値:

  • Excel Workbook

optseq_production_excel[source]

optseq_production_excel()

optseq_production_excel関数の使用例

wb = optseq_production_excel()
wb.save("optseq-production.xlsx")

生産スケジューリング用の資源Excelファイル生成関数 optseq_resource_excel

注)この関数はSCMOPTに含まれるスケジューリング最適化システム用関数です.ソルバー版のOptSeqでは利用できません.

日タイプ別の資源上限入力用のExcelファイルの生成

資源は,カレンダー(休日),平日稼働時間,土曜稼働時間,休日稼働時間などを入れてデータベースに保管

それをもとに,作業シートを生成してダウンロード,その後記入して,アップロード

day_dfで計画期間内の日と日タイプの紐付けを行い,資源量上限を設定し,最適化

引数

  • wb: OptSeq基本Workbook
  • start: 開始日
  • finish: 終了日
  • period: 期を構成する単位期間の数;既定値は $1$
  • period_unit: 期の単位 (時,日,週,月から選択); 既定値は日; periodとあわせて期間の生成に用いる. たとえば,既定値だと1日が1期となる.

返値:

  • wb: 日別の資源使用可能量条件設定用のシートを加えたWorkbook

optseq_resource_excel[source]

optseq_resource_excel(wb, start, finish, period=1, period_unit='時')

optseq_resource_excel関数の使用例

basic_wb = load_workbook("optseq-production.xlsx")
period_unit = "時"
period = 1 
start = "0:00"
finish = "0:00"
#res_list =[ {"resource_name": "機械", "seq_dependent": True}, {"resource_name": "作業員", "seq_dependent": False} ] #DBから
wb = optseq_resource_excel(basic_wb, start, finish, period, period_unit)
wb.save("optseq-resource.xlsx")

ExcelのWorkbookをデータフレームに変換する関数 prepare_df_for_optseq

注)この関数はSCMOPTに含まれるスケジューリング最適化システム用関数です.ソルバー版のOptSeqでは利用できません.

引数:

  • wb: OptSeqの基本Workbookオブジェクト
  • resource_wb: 日タイプ別の資源使用可能量上限を入れたWorkbook
  • day_wb: 日情報を入れたWorkbook

返値:

  • act_df : 作業データフレーム
  • time_df : 時間制約データフレーム
  • usage_df: 資源使用量データフレーム
  • resource_df_dic : 日タイプごとの資源使用可能量上限のデータフレームを入れた辞書
  • day_df: 日データフレーム

prepare_df_for_optseq[source]

prepare_df_for_optseq(wb, resource_wb, day_wb)

prepare_df_for_optseq関数の使用例

wb = load_workbook("optseq-ex1.xlsx")
resource_wb = load_workbook("optseq-resource.xlsx")
day_wb = load_workbook("optseq-day.xlsx")

act_df, resource_df, time_df, usage_df, res_df_dic, day_df = prepare_df_for_optseq(wb, resource_wb, day_wb)

期ごとの資源使用可能量上限を準備する関数 prepare_capacity

注)この関数はSCMOPTに含まれるスケジューリング最適化システム用関数です.ソルバー版のOptSeqでは利用できません.

引数:

  • res_df_dic: 日タイプごとの資源使用可能量上限のデータフレームを入れた辞書
  • day_df: 日データフレーム
  • start: 基準時刻

返値:

  • capacity: 資源使用可能量上限を入れた辞書

prepare_capacity[source]

prepare_capacity(res_df_dic, day_df, start)

prepare_capacity関数の使用例

start = dt.datetime(2021,1,1,0,0)
capacity = prepare_capacity(res_df_dic, day_df, start)
print(capacity)

結果Workbookから固定情報の抽出関数 extract_fix_optseq

注)この関数はSCMOPTに含まれるスケジューリング最適化システム用関数です.ソルバー版のOptSeqでは利用できません.

引数:

  • wb: ガントチャートのWorkbookオブジェクト(作業の開始時刻と終了時刻の固定情報が入っている)
  • start: 基準時刻

返値:

  • fix_start: 作業の開始時刻の固定情報
  • fix_finish: 作業の終了時刻の固定情報

extract_fix_optseq[source]

extract_fix_optseq(wb, start)

extract_fix_optseq関数の使用例

start = dt.datetime(2021,5,1,0,0)
wb = load_workbook("optseq-result.xlsx")
fix_start, fix_finish = extract_fix_optseq(wb, start)
fix_start, fix_finish

生産スケジューリング用のExcelファイルを読み込んでモデルを生成する関数 make_model_for_optseq_production

注)この関数はSCMOPTに含まれるスケジューリング最適化システム用関数です.ソルバー版のOptSeqでは利用できません.

引数:

  • act_df : 作業データフレーム
  • resource_df : 資源データフレーム
  • time_df : 時間制約データフレーム
  • usage_df: 資源使用量データフレーム
  • capacity: 資源使用可能量上限を入れた辞書
  • start: 基準時刻
  • fix_start: 作業の開始時刻の固定情報
  • fix_finish: 作業の終了時刻の固定情報

返値:

  • model: OptSeqモデルオブジェクト

make_model_for_optseq_production[source]

make_model_for_optseq_production(act_df, resource_df, time_df, usage_df, capacity, start, fix_start=None, fix_finish=None)

make_model_for_optseq_production関数の使用例

#resource_wb = load_workbook("optseq-resource.xlsx")
#day_wb = load_workbook("optseq-day.xlsx")

wb = load_workbook("optseq-master-ex1.xlsx")
resource_wb = load_workbook("optseq-resource-ex1.xlsx")
day_wb = load_workbook("optseq-day.xlsx")

act_df, resource_df, time_df, usage_df, res_df_dic, day_df = prepare_df_for_optseq(wb, resource_wb, day_wb)

start = dt.datetime(2021,1,1,0,0)
capacity = prepare_capacity(res_df_dic, day_df, start)

#model = make_model_for_optseq_production(act_df, resource_df, time_df, usage_df, capacity, start, fix_start, fix_finish)
model = make_model_for_optseq_production(act_df, resource_df, time_df, usage_df, capacity, start)
print(model)
model.Params.TimeLimit =10
model.optimize()
fig = make_gannt(model,start=start, period="minutes")
plotly.offline.plot(fig);
fig = make_resource_graph(model, scale=60) #分でなく時間単位にする!
plotly.offline.plot(fig);

生産スケジューリング用のガントチャート生成関数 make_gannt_for_production

注)この関数はSCMOPTに含まれるスケジューリング最適化システム用関数です.ソルバー版のOptSeqでは利用できません.

引数:

  • model: OptSeqモデルインスタンス(最適化後)
  • capacity: 資源使用可能量上限を入れた辞書
  • start: 開始日

返値:

  • wb: ガントチャートのWorkbook

make_gannt_for_production[source]

make_gannt_for_production(model, capacity, start='2020/1/1 00:00:00')

Excelのガントチャートを生成する関数

make_gannt_for_production関数の使用例

wb = make_gannt_for_production(model, capacity, start="2021/1/1 00:00:00")
wb.save("optseq-gannt.xlsx")