スケジューリング最適化システム OptSeq

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 以外の文字に限定される．

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

Parameters クラス

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

---

source

Parameters

 Parameters (TimeLimit:typing.Annotated[int,Gt(gt=0)]=600,
             OutputFlag:bool=False, RandomSeed:int=1,
             ReportInterval:typing.Annotated[int,Gt(gt=0)]=1073741823,
             Backtruck:typing.Annotated[int,Gt(gt=0)]=1000,
             MaxIteration:typing.Annotated[int,Gt(gt=0)]=1073741823,
             Initial:bool=False, Tenure:typing.Annotated[int,Gt(gt=0)]=1,
             Neighborhood:typing.Annotated[int,Gt(gt=0)]=20,
             Makespan:bool=False)

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(TimeLimit = -1)
params = Parameters()
params.Makespan = True
print("Time Limit  = ", params.TimeLimit)
print(params)

Time Limit  =  600
 
 TimeLimit = 600 
 OutputFlag = False
 RandomSeed = 1 
 ReportInterval = 1073741823 
 Backtruck = 1000
 Initial = False 
 Tenure = 1
 Neighborhood = 20 
 makespan = True 

State クラス

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

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

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

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

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

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

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

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

---

source

State

 State (name:str='')

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(name="sample state")
# state = State()
state.addValue(time=5, value=1)
print(state)

state sample_state  time 5 value 1 

Mode クラス

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

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

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

コンストラクタの引数の名前と意味は以下の通り． - nameはモードの名前を文字列で与える．ただしモードの名前に’dummy’を用いることはできない． - durationはモードの作業時間を非負の整数で与える．既定値は \(1\)．

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

• 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は並列作業の情報を表す辞書である．辞書のキーはタプル(開始小作業番号,終了小作業番号)であり， 値は最大並列可能数を表す正数値である．

---

source

Mode

 Mode (name:str='', duration:typing.Annotated[int,Gt(gt=0)]=1, requirement
       :Optional[Dict[Tuple[str,Optional[str]],Dict[Tuple[Annotated[int,Ge
       (ge=0)],Annotated[int,Ge(ge=0)]],Annotated[int,Ge(ge=0)]]]]=None, b
       reakable:Optional[Dict[Tuple[Annotated[int,Ge(ge=0)],Annotated[int,
       Ge(ge=0)]],Annotated[int,Gt(gt=0)]]]=None, parallel:Optional[Dict[T
       uple[Annotated[int,Gt(gt=0)],Annotated[int,Gt(gt=0)]],Annotated[int
       ,Gt(gt=0)]]]=None,
       state:Optional[Dict[__main__.State,Tuple[int,int]]]=None)

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(name="test mode", duration=10)
# res = Resource(name = "sample resource", capacity = 1)
# mode.addResource(res,{(0,"inf"):100})
mode.addBreak(0, 10, 1)
mode.addParallel(1, 1, 2)
print(mode)

 duration 10  
 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は探索によって発見された解における作業の実行を表す辞書である．キーは作業の開始時刻と終了時刻のタプル， 値は並列実行数を表す正数値である．

---

source

Activity

 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)
# act2 = Activity()
# act2

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[作業,モード]とすると， 追加される項は， $ 係数 x[作業,モード]
  $ と記述される． addTermsメソッドの引数は以下の通り．

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

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

• nameは資源名である．
• capacityは資源の容量（使用可能量の上限）を表す辞書である． 辞書のキーはタプル (開始時刻, 終了時刻) であり，値は容量を表す正数値である．
• rhsは再生不能資源制約の右辺定数である． 既定値は \(0\)．
• directionは再生不能資源制約の方向を表す．　既定値は ‘<=’．
• termsは再生不能資源制約の左辺を表す項のリストである．各項は (係数,作業インスタンス,モードインスタンス) のタプルである．
• weightは再生不能資源制約を逸脱したときのペナルティの重みを表す． 正数値か絶対制約を表す’inf’を入れる． 既定値は無限大（絶対制約）を表す文字列’inf’である．
• residualは最適化後に計算される資源の余裕量を表す辞書である． 辞書のキーはタプル (開始時刻, 終了時刻) であり，値は残差を表す非負整数値である．

---

source

Resource

 Resource (name='', capacity:Union[int,Dict[Tuple[Annotated[int,Ge(ge=0)],
           Annotated[int,Ge(ge=0)]],Annotated[int,Gt(gt=0)]],NoneType]=Non
           e, rhs:int=0, direction:str='<=',
           weight:Union[Annotated[int,Ge(ge=0)],str]='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).
  • residual: Residual dictionary of the renewable (standard) resource.

Resourceクラスの使用例

res = Resource(name="sample resource", capacity={(0, 10): 1})
res.addCapacity(0, 5, 10)

print("renewable resource= \n", res)

print()

mode = Mode(name="test mode", duration=10)
act = Activity("sample activity", duedate=100, backward=True, weight=10)
act.addModes(mode)
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 10 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で，その場合にはモードに依存せず作業に対する時間制約となる．

---

source

Temporal

 Temporal (pred:Union[__main__.Activity,str],
           succ:Union[__main__.Activity,str], tempType:str='CS',
           delay:int=0, pred_mode:Optional[__main__.Mode]=None,
           succ_mode:Optional[__main__.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(name="sample activity2")
temp = Temporal(pred=act, succ=act2)
temp2 = Temporal(pred=act, succ="sink", pred_mode=act.modes[0])
print(temp)
print(temp2)

temporal sample_activity sample_activity2  type CS delay 0 
temporal sample_activity mode test_mode sink mode dummy  type CS delay 0 

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\)	モデルの入力は完了しているが，まだ最適化されていない．

---

source

Model

 Model (name:Optional[str]='')

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

---

source

visualize

 visualize (model)

最適化の描画関数 plot_optseq

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

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

---

source

plot_optseq

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

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

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

与えられたモデルに格納されているスケジュールを、ガントチャートで可視化する。 ただし，一部分を描画したい場合には，開始期間beginと終了期間endならびに資源名の集合resourcesで制御する．

引数：

• model : OptSeqモデルオブジェクト
• start : 開始時刻を表す（pandasの日付時刻型に変換可能な文字列）文字列． 既定値は “2024/1/1”．
• period : 時間の単位を表す文字列． “days”（日）， “seconds”（秒），　“minutes”（分）， “hours（時間）の何れか． 既定値は”days”
• begin: 開始期間（整数）；既定値は \(0\)
• end: 終了期間（整数もしくは”inf”）；既定値は “inf”
• resources: 資源名の集合；既定値はNone

返値：

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

---

source

time_convert_long

 time_convert_long (periods, start='2019/1/1', period='days')

---

source

make_gannt

 make_gannt (model:__main__.Model, start:str='2024/1/1',
             period:str='days', begin:int=0, end:Union[int,str]='inf',
             resources:Optional[Set]=None)

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

make_gannt関数の使用例

# begin = 38
# end = 70
# resources = None #set(["worker"])
# fig = make_gannt(model, start="2024-1-1", period="minutes", begin=begin, end=end, resources=resources)
# plotly.offline.plot(fig);

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

引数： - model: OptSeqモデルファイル - start : 開始時刻を表す（pandasの日付時刻型に変換可能な文字列）文字列． 既定値は “2024/1/1”． - period : 時間の単位を表す文字列． “days”（日）， “seconds”（秒），　“minutes”（分）， “hours（時間）の何れか． 既定値は”days” - scale: 横軸をscale分の1にする．（たとえば分単位を時間単位にする．）既定値は \(1\)． - begin: 開始期間（整数）；既定値は \(0\) - end: 終了期間（整数もしくは”inf”）；既定値は “inf” - resources: 資源名の集合；既定値はNo

返値：

• fig : 資源グラフの図オブジェクト

---

source

make_resource_graph

 make_resource_graph (model:__main__.Model, start:str='2024/1/1',
                      period:str='days', scale:int=1, begin:int=0,
                      end:Union[int,str]='inf',
                      resources:Optional[Set]=None)

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

make_resource_graph関数の使用例

start: str = "2024/1/1"
period: str = "minutes"
scale = 10
begin = 10
end = 70
resources = set(["worker"])
fig = make_resource_graph(
    model,
    start=start,
    period=period,
    scale=10,
    begin=begin,
    end=end,
    resources=resources,
)
# plotly.offline.plot(fig);

OptSeqのモデルをCPのモデルに変換する関数 transform_to_cp

ジョブショップスケジューリングの大規模問題例用に他のソルバーも準備する．ただし，より簡略化したモデルに対する最適化になる． 以下の関数は，機械（資源量上限が1の資源）を特別に扱うので， 大規模問題例ではOptSeqより高速で精度が良い可能性がある． 実務においては，様々なソルバーを準備しておき，すべてで試し， 最も性能が良いものを使う確率を上げていくAutoOptの利用が望ましい．

以下の関数では，CPにより最適化を行い結果をOptSeqのモデルインスタンスに書き込む． 引数のhorizonはなるべく小さい計画期間を事前に計算して設定しておくことが望ましい． ただし，horizonが最適メイクスパンより小さいと実行不能になるので，注意する必要がある． 簡易計算用の関数 compute_horizon も準備しておくが， ベンチマーク問題例では大きくなりすぎるので，別途簡易ヒューリスティクスで解いて設定する．

引数

• model: OptSeqのモデルインスタンス
• horizon: 計画期間

返値

• cpmodel: CPのモデル

---

source

compute_horizon

 compute_horizon (model:__main__.Model)

---

source

transform_to_cp

 transform_to_cp (model:__main__.Model, horizon:int)

transform_to_cpの使用例

TODO: OptSeqのsolveのオプションで切り替える．

horizon = 10000
print("horizon=", horizon)
model.Params.OutputFlag = False

cpmodel = transform_to_cp(model, horizon)

print(model.ObjVal, model.Status)
# for a_name, a in model.activities.items():
#     print(a_name, a.execute)

Shifting Bottleneck法

大規模なジョブショップスケジューリング問題に対する解法としてShifting Bottleneck法を準備する．

1台の機械に対するスケジューリング問題をCPソルバーで解く操作を繰り返すことによって， 複数機械のスケジューリング問題の近似解を算出する．

クラス

• Job: 機械の番号 r と作業時間 p　を引数としたジョブ（正確にはオペレーション）のクラス
• Jobshop: NetworkXの有向グラフクラスから派生させたクラスであり， ジョブをノードとして追加することによって， ジョブショップスケジューリング問題のネットワークを定義する，
• Shift: Jobshopから派生させたShifting Bottleneck法のメインクラス．

上のクラスを用いてShifting Bottleneck法を実行する関数 shifting_bottleneckを構築する．

---

source

shifting_bottleneck

 shifting_bottleneck (js:__main__.Shift, horizon:int=1000000,
                      LOG:bool=False)

/opt/hostedtoolcache/Python/3.9.19/x64/lib/python3.9/site-packages/fastcore/docscrape.py:225: UserWarning: Unknown section Methods
  else: warn(msg)
/opt/hostedtoolcache/Python/3.9.19/x64/lib/python3.9/site-packages/fastcore/docscrape.py:225: UserWarning: Unknown section Properties
  else: warn(msg)

---

source

Shift

 Shift ()

A class that creates a directed graph of a jobshop.

We formulate the tasks of the jobshop as nodes in a directed graph, add the processing times of the tasks as attributes to the task nodes. A flag “dirty” was added so when some topological changes are carried the method “_update” is called first to update the makespan and critical path values. Once the update is finished, the updated makespan is returned.

---

source

Jobshop

 Jobshop ()

A class that creates a directed graph of a jobshop.

We formulate the tasks of the jobshop as nodes in a directed graph, add the processing times of the tasks as attributes to the task nodes. A flag “dirty” was added so when some topological changes are carried the method “_update” is called first to update the makespan and critical path values. Once the update is finished, the updated makespan is returned.

---

source

Job

 Job (Id, r, p)

A class that creates jobs.

shifting _bottleneckの使用例

::: {#cell-65 .cell 0=‘h’ 1=‘i’ 2=‘d’ 3=‘e’}

# js = Shift()

# jobs = {}
# jobs[1] = Job(1, [1,2,3], [10, 8, 4])
# jobs[2] = Job(2, [2,1,4,3], [8,3,5,6])
# jobs[3] = Job(3, [1,2,4], [4,7,3])

# js.addJobs(jobs)
# shifting_bottleneck(js, horizon=100, LOG=False)
# js.output()
#ベンチマークの実験
#name = "ft06.txt"
#name = "tai_j10_m10_1.data"
#name ="tai_j100_m10_1.data"
#name ="tai_j1000_m10_1.data"
#name ="tai_j100_m100_1.data"
name = "tai_j1000_m100_1.data"
#name ="tai_j1000_m1000_1.data"

fname = f"./data/optseq/{name}"

horizon = 1000000
f = open(fname, "r")
lines = f.readlines()
f.close()
n, m = map(int, lines[0].split())
print("n,m=", n, m)

js = Shift()

jobs ={}
for i in range(n):
    L = list(map(int, lines[i + 1].split()))
    machines, durations = [], []
    for j in range(m):
        machines.append( L[2 * j] + 1 )
        durations.append( L[2 * j + 1] )
    jobs[i+1] = Job(i+1, machines, durations)
    
js.addJobs(jobs)

remain = set(js.machines.keys()) #残りの機械
count = 0
while len(remain) > 0:
    js.criticalPath
    #if LOG: js.output()
    
    result = js.computeLmax2(remain, horizon) #use cp-sat
    #print("result=", result) #machine, obj, seq
    max_lmax = -1
    max_machine = -1
    best_seq = None
    for idx, lmax, seq in result:
        if lmax > max_lmax:
            max_lmax = lmax
            max_machine = idx
            best_seq = seq
    print(count, max_machine, max_lmax)

    # if count ==1:
    #     best_seq =[(2, 3), (2, 2), (2, 1)]

    #閉路がある場合には切除平面を追加
    pred = best_seq[0]
    edges = []
    for succ in best_seq[1:]:
        edges.append( (pred, succ) )
        pred = succ
    #print("edges=", edges)   
    while True:
        G = js.copy()
        G.add_edges_from(edges)
        if nx.is_directed_acyclic_graph(G)==True: #閉路がない
            break
            
        #閉路があるかどうかを確認し，あるならカットを追加して再求解
        S = set(js.machines[max_machine])
        G.remove_nodes_from(['U', 'V'])
        #print("before preprocessing", len(G.edges()))
        remove_zero_indegree_nodes(G)
        remove_zero_outdegree_nodes(G)
    
        label, prev = {}, {}
        precedence =[]
        #find shortest paths between 2 jobs on the machine
        for i in S:
            if i not in G:
                continue
            #print("search from", i)
            label[i] = 0
            for (k,j) in nx.bfs_edges(G, source=i):
                label[j] = label[k] + G.nodes[k]['p']
                prev[j] = k
                if i in G[j] and j in S:
                    print("found a cycle", i,j, label[j])
                    precedence.append( (i,j,label[j]) )
                    break #only one cycle
                    
        if len(precedence)>0:
            #カットの追加して再求解
            result = js.computeLmax2([max_machine], horizon, precedence) #use cp-sat
            idx, lmax, best_seq = result[0]
            #print("best_seq=", best_seq)
            pred = best_seq[0]
            edges = []
            for succ in best_seq[1:]:
                edges.append( (pred, succ) )
                pred = succ
            #print("edges=", edges)
            
    # js.add_edges_from(edges) #機械での順序を追加
    count +=1
    # if count ==2:
    #     break
    js.add_edges_from(edges) #
    remain.remove(max_machine)

CPU times: user 1 µs, sys: 1 µs, total: 2 µs
Wall time: 3.1 µs
n,m= 1000 100
0 77 465142
1 1 0
2 2 0
3 3 0
4 4 0
5 37 632

:::

nx.is_directed_acyclic_graph(js._criticalPath)

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

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

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

引数：

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

返値：

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

---

source

make_gannt_for_notion

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

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

make_gannt_for_notion関数の使用例

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

df = make_gannt_for_notion(model, start, period="minutes")
df.to_csv("gannt.csv", index=False)
df.head()

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

make_gannt_for_excelの使用例

# model.optimize()
# start="2020/1/1 00:00:00"
# wb = make_gannt_for_excel(model, start="2020/5/1 00:00:00")
# wb.save("gannt.xlsx")

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

TODO: 順序依存の段取り

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

---

source

optseq_project_excel

 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

---

source

optseq_production_excel

 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期となる．

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

---

source

optseq_resource_excel

 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"
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: 日データフレーム

---

source

prepare_df_for_optseq

 prepare_df_for_optseq (wb, resource_wb, day_wb)

---

source

time_delta

 time_delta (finish, start)

日付時刻もしくは時刻型の差を計算して，秒を返す関数

prepare_df_for_optseq関数の使用例

wb = load_workbook("optseq-master-ex1.xlsx")
resource_wb = load_workbook("optseq-resource-ex1.xlsx")
day_wb = load_workbook("optseq-day-ex1.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: 資源使用可能量上限を入れた辞書

---

source

prepare_capacity

 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)

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

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

引数：

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

返値： - model: OptSeqモデルオブジェクト

---

source

make_model_for_optseq_production

 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関数の使用例

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

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

引数：

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

返値： - fix_start: 作業の開始時刻の固定情報 - fix_finish: 作業の終了時刻の固定情報

---

source

extract_fix_optseq

 extract_fix_optseq (wb, start)

extract_fix_optseq関数の使用例

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

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

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

引数： - model: OptSeqモデルインスタンス（最適化後） - capacity: 資源使用可能量上限を入れた辞書 - start: 開始日

返値： - wb: ガントチャートのWorkbook

---

source

make_gannt_for_production

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

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

make_gannt_for_production関数の使用例

# model.Params.TimeLimit=3
# model.optimize()
# wb = make_gannt_for_production(model, capacity, start="2021/1/1 00:00:00")
# wb.save("optseq-gannt-ex1.xlsx")