Scheduling Solver OptSeq

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

YouTubeVideo("Nue61nhu9PE")

Parameter クラス

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=0.

  • 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.

Mode クラス

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.addState[source]

Mode.addState(state, fromValue=0, toValue=0)

Adds a state change information to the mode.

- Arguments:
    - state: State object to be added to the mode.
    - fromValue: the value from which the state changes by the mode
    - toValue:  the value to which the state changes by the mode

- Example usage:

>>> mode.addState(state1,0,1)

defines that state1 is changed from 0 to 1.

Mode.addResource[source]

Mode.addResource(resource, requirement=None, rtype=None)

Adds a resource to the mode.

- Arguments:
    - resurce: Resource object to be added to the mode.
    - requirement: Dictionary that maps intervals (pairs of start time and finish time) to amounts of requirement.
                   It may be an integer; in this case, requirement is converted into the dictionary {(0,"inf"):requirement}.
    - rtype (optional): Type of resource to be added to the mode.
    None (standard resource type; default), "break" or "max."

- Example usage:

>>> mode.addResource(worker,{(0,10):1})

defines worker resource that uses 1 unit for 10 periods.

>>> mode.addResource(machine,{(0,"inf"):1},"break")

defines machine resource that uses 1 unit during break periods.

>>> mode.addResource(machine,{(0,"inf"):1},"max")

defines machine resource that uses 1 unit during parallel execution.

Mode.addBreak[source]

Mode.addBreak(start=0, finish=0, maxtime='inf')

Sets breakable information to the mode.

- Arguments:
    - start(optional): Earliest break time. Non-negative integer. Default=0.
    - finish(optional): Latest break time.  Non-negative integer or "inf." Default=0.
        Interval (start,finish) defines a possible break interval.
    - maxtime(optional): Maximum break time. Non-negative integer or "inf." Default="inf."

- Example usage:

>>> mode.addBreak(0,10,1}

defines a break between (0,10) for one period.

Mode.addParallel[source]

Mode.addParallel(start=1, finish=1, maxparallel='inf')

Sets parallel information to the mode.

- Arguments:
    - start(optional): Smallest job index executable in parallel. Positive integer. Default=1.
    - finish(optional): Largest job index executable in parallel. Positive integer or "inf." Default=1.
    - maxparallel(optional): Maximum job numbers executable in parallel. Non-negative integer or "inf." Default="inf."

- Example usage:

>>> mode.addParallel(1,1,2}

Activity クラス

class Activity[source]

Activity(name='', duedate='inf', weight=1, autoselect=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."
        - 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.addModes[source]

Activity.addModes(*modes)

Adds a mode or modes to the activity.

- Arguments:
    - modes: One or more mode objects.

- Example usage:

>>> activity.addModes(mode1,mode2)

Resource クラス

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 ">=".
     - 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.addCapacity[source]

Resource.addCapacity(start=0, finish=0, amount=1)

Adds a capacity to the resource.

- Arguments:
    - start(optional): Start time. Non-negative integer. Default=0.
    - finish(optional): Finish time. Non-negative integer. Default=0.
     Interval (start,finish) defines the interval during which the capacity is added.
    - amount(optional): The amount to be added to the capacity. Positive integer. Default=1.

- Example usage:

>>> manpower.addCapacity(0,5,2)

Resource.printConstraint[source]

Resource.printConstraint()

Returns the information of the linear constraint.

The constraint is expanded and is shown in a readable format.

Resource.addTerms[source]

Resource.addTerms(coeffs=None, vars=None, values=None)

Add new terms into left-hand-side of nonrenewable resource constraint.

- Arguments:
    - coeffs: Coefficients for new terms; either a list of coefficients or a single coefficient.
    The three arguments must have the same size.
    - vars: Activity objects for new terms; either a list of activity objects or a single activity object.
    The three arguments must have the same size.
    - values: Mode objects for new terms; either a list of mode objects or a single mode object.
    The three arguments must have the same size.

- Example usage:

>>> budget.addTerms(1,act,express)

adds one unit of nonrenewable resource (budget) if activity "act" is executed in mode "express."

Resource.setDirection[source]

Resource.setDirection(direction='<=')

Resource.setRhs[source]

Resource.setRhs(rhs=0)

Sets the right-hand-side of linear constraint.

- Argument:
    - rhs: Right-hand-side of linear constraint.

- Example usage:

>>> L.setRhs(10)

Temporal クラス

class Temporal[source]

Temporal(pred, succ, tempType, delay)

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.

- 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.

State クラス

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.addValue[source]

State.addValue(time=0, value=0)

Adds a value to the state

- Arguments:
    - time: the time at which the state changes.
    - value: the value that the state changbes to

- Example usage:

>>> state.addValue(time=5,value=1)

Modelクラス

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.addActivity[source]

Model.addActivity(name='', duedate='inf', weight=1, autoselect=False)

Add an activity to the model.

- Arguments:
    - name: Name for new activity. A string object except "source" and "sink." Remark that strings in OptSeq are restricted to a-z, A-Z, 0-9,[],_ and @.
    - duedate(optional): Duedate of activity. A non-nagative integer or string "inf."
    - 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.

- Return value: New activity object.

- Example usage:

>>> a = model.addActivity("act1")

>>> a = model.addActivity(name="act1",duedate=20,weight=100)

>>> a = model.addActivity("act1",20,100)

Model.addResource[source]

Model.addResource(name='', capacity=None, rhs=0, direction='<=', weight='inf')

Add a resource to the model.

- Arguments:
    - name: Name for new 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.
    - rhs (optional): Right-hand-side constant of nonrenewable resource constraint.
    - direction (optional): Rirection (or sense) of nonrenewable resource constraint; "<=" (default) or ">=" or "=".
    - weight (optional): Weight of resource. Non-negative integer or "inf" (default).

- Return value: New resource object.

- Example usage:

>>> r=model.addResource("res1")

>>> r=model.addResource("res1", {(0,10):1,(12,100):2} )

>>> r=model.addResource("res2",rhs=10,direction=">=")

Model.addState[source]

Model.addState(name='')

Add a state to the model.

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

- Return value: New state object.

- Example usage:

>>> a = model.addState("state1")

Model.addTemporal[source]

Model.addTemporal(pred, succ, tempType='CS', delay=0)

Add a temporal constraint to the model.

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.

- Return value: New temporal object.

- Example usage:

>>> t=model.addTemporal(act1,act2)

>>> t=model.addTemporal(act1,act2,type="SS",delay=-10)

To specify the start time of activity act is exactly 50, we use two temporal constraints:

>>> t=model.addTemporal("source",act,type="SS",delay=50)

>>> t=model.addTemporal(act,"source",type="SS",delay=50)

Model.optimize[source]

Model.optimize()

Optimize the model using optseq.exe in the same directory.

- Example usage:

>>> model.optimize()

Model.write[source]

Model.write(filename='optseq_chart.txt')

Output the gantt's chart as a text file.

- Argument:
    - filename: Output file name. Default="optseq_chart.txt."

- Example usage:

>>> model.write("sample.txt")

Model.writeExcel[source]

Model.writeExcel(filename='optseq_chart.csv', scale=1)

Output the gantt's chart as a csv file for printing using Excel.

- Argument:
    - filename: Output file name. Default="optseq_chart.csv."

- Example usage:

>>> model.writeExcel("sample.csv")

例題を返す関数

例題1 PERT

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

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

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 = ex1()
model.optimize()
model.write(folder + "chart1.txt")
#!less chart1.txt
 ================ 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

例題2 資源制約付きPERT

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

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

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 = ex2()
model.optimize()
model.write(folder +"chart2.txt")
 ================ 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 = 0/64689


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

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

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

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

各作業には,作業時間のほかに, この作業が終わらないと次の作業ができないといったような時間制約がある. 作業時間と時間制約は,図~¥ref{fig:F1} のようになっている.

TODO: 図はどうするか?

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

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 = ex3()
model.optimize()
model.write(folder +"chart3.txt")
 ================ 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 12
objective value = 14 (cpu time = 0.00(s), iteration = 0)
0: 0.00(s): 14/14

--- best solution ---
source,---, 0 0
sink,---, 14 14
Act[1],---, 0 0--3 3
Act[2],---, 0 0--2 2
Act[3],---, 0 0--2 2
Act[4],---, 2 2--4 4
Act[5],---, 8 8--12 12
Act[6],---, 4 4--8 8
Act[7],---, 8 8--12 12
Act[8],---, 4 4--8 8
Act[9],---, 3 3--14 14
Act[10],---, 12 12--14 14
--- tardy activity ---
sink: 14
--- resource residuals ---
worker: [0,2] 0 [2,4] 1 [4,12] 0 [12,14] 1 

--- best activity list ---
source ---
Act[1] ---
Act[2] ---
Act[9] ---
Act[3] ---
Act[4] ---
Act[8] ---
Act[6] ---
Act[5] ---
Act[7] ---
Act[10] ---
sink ---

objective value = 14
cpu time = 0.00/1.00(s)
iteration = 0/13487


Solutions:
    source   ---     0     0
      sink   ---    14    14
    Act[1]   ---     0     3
    Act[2]   ---     0     2
    Act[3]   ---     0     2
    Act[4]   ---     2     4
    Act[5]   ---     8    12
    Act[6]   ---     4     8
    Act[7]   ---     8    12
    Act[8]   ---     4     8
    Act[9]   ---     3    14
   Act[10]   ---    12    14

例題4 モードの利用

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

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

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

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 = ex4()
model.optimize()
model.write(folder +"chart4.txt")
 ================ 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 12
objective value = 14 (cpu time = 0.00(s), iteration = 0)
0: 0.00(s): 14/14
objective value = 13 (cpu time = 0.00(s), iteration = 6)

--- best solution ---
source,---, 0 0
sink,---, 13 13
Act[1],Mode[1_3], 0 0--1 1
Act[2],---, 1 1--3 3
Act[3],---, 11 11--13 13
Act[4],---, 1 1--3 3
Act[5],---, 3 3--7 7
Act[6],---, 7 7--11 11
Act[7],---, 3 3--7 7
Act[8],---, 7 7--11 11
Act[9],---, 1 1--12 12
Act[10],---, 11 11--13 13
--- tardy activity ---
sink: 13
--- resource residuals ---
worker: [0,12] 0 [12,13] 1 

--- best activity list ---
source ---
Act[1] Mode[1_3]
Act[2] ---
Act[4] ---
Act[7] ---
Act[5] ---
Act[9] ---
Act[6] ---
Act[8] ---
Act[3] ---
Act[10] ---
sink ---

objective value = 13
cpu time = 0.00/1.00(s)
iteration = 6/11174


Solutions:
    source   ---     0     0
      sink   ---    13    13
    Act[1] Mode[1_3]     0     1
    Act[2]   ---     1     3
    Act[3]   ---    11    13
    Act[4]   ---     1     3
    Act[5]   ---     3     7
    Act[6]   ---     7    11
    Act[7]   ---     3     7
    Act[8]   ---     7    11
    Act[9]   ---     1    12
   Act[10]   ---    11    13

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

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

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

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

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

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 = ex5()
model.optimize()
model.write(folder +"chart5.txt")
 ================ 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 = 6 (cpu time = 0.00(s), iteration = 0)
0: 0.00(s): 6/6
--- best solution ---
source,---, 0 0
sink,---, 6 6
Act[1],---, 0 0--1 1
Act[2],---, 1 1--4 4
Act[3],---, 3 3--5 5
Act[4],---, 4 4--6 6
--- tardy activity ---
sink: 6
--- resource residuals ---
worker: [0,6] 0 

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

objective value = 6
cpu time = 0.00/1.00(s)
iteration = 1/46171


Solutions:
    source   ---     0     0
      sink   ---     6     6
    Act[1]   ---     0     1
    Act[2]   ---     1     4
    Act[3]   ---     3     5
    Act[4]   ---     4     6

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

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

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

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 = ex6()
model.optimize()
model.write(folder +"chart6.txt")
 ================ 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 = 3 (cpu time = 0.00(s), iteration = 0)
0: 0.00(s): 3/3

--- best solution ---
source,---, 0 0
sink,---, 10 10
Act[1],---, 4 4--5 5
Act[2],---, 8 8--10 10
Act[3],---, 5 5--8 8
Act[4],---, 0 0--4 4
--- tardy activity ---
Act[2]: 1
Act[3]: 2
--- resource residuals ---
writer: [0,10] 0 

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

objective value = 3
cpu time = 0.00/1.00(s)
iteration = 0/59620


Solutions:
    source   ---     0     0
      sink   ---    10    10
    Act[1]   ---     4     5
    Act[2]   ---     8    10
    Act[3]   ---     5     8
    Act[4]   ---     0     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$単位使用するという条件を付加する.

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 = ex7()
model.optimize()
model.write(folder +"chart7.txt")
 ================ 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 = 45 (cpu time = 0.00(s), iteration = 0)
0: 0.00(s): 45/45

--- best solution ---
source,---, 0 0
sink,---, 45 45
Act[1]_,Mode[1][2], 0 0--10 10
Act[2]_,Mode[2][2], 0 0--20 20
Act[3]_,Mode[3][2], 10 10--20 20
Act[4]_,Mode[4][2], 20 20--45 45
Act[5]_,Mode[5][1], 20 20--42 42
--- tardy activity ---
sink: 45
--- resource residuals ---

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

objective value = 45
cpu time = 0.00/1.00(s)
iteration = 0/140911


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][1]    20    42

例題8 時間制約

OptSeqでは,通常の先行制約の他に,様々な時間に関する制約が準備されている. 時間制約を用いることによって,実際問題で発生する様々な付加条件をモデル化することができる.

時間制約の適用例として,最初に示したPERTの例題において, 作業3と作業5の開始時刻が一致しなければならないという制約を考えてみる.

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

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

たとえば,作業5(名前はact[5])の開始時刻を $50$分に固定したい場合には,

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

と時間制約を追加する.

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 = ex8()
model.optimize()
model.write(folder +"chart8.txt")
 ================ 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 = 92 (cpu time = 0.00(s), iteration = 0)
0: 0.00(s): 92/92

--- best solution ---
source,---, 0 0
sink,---, 92 92
Act[1],---, 0 0--13 13
Act[2],---, 0 0--25 25
Act[3],---, 50 50--65 65
Act[4],---, 65 65--92 92
Act[5],---, 50 50--72 72
--- tardy activity ---
sink: 92
--- resource residuals ---

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

objective value = 92
cpu time = 0.00/1.00(s)
iteration = 0/93592


Solutions:
    source   ---     0     0
      sink   ---    92    92
    Act[1]   ---     0    13
    Act[2]   ---     0    25
    Act[3]   ---    50    65
    Act[4]   ---    65    92
    Act[5]   ---    50    72

例題9 作業の途中中断

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

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

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

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

例として,納期遅れ最小化問題において,すべての作業がいつでも最大1日だけ中断できる場合を考える.

作業の途中中断は,

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

を用いて追加する.

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

中断中に資源を使用する場合も,通常の資源を追加するのと同様にaddResourceメソッドを用いて追加する. この場合,引数として

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

を入力する.

例題の資源を表す「作家」が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 = ex9()
model.optimize()
model.write(folder +"chart9.txt")
 ================ 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 = 10 (cpu time = 0.00(s), iteration = 0)
0: 0.00(s): 10/10
objective value = 9 (cpu time = 0.00(s), iteration = 1)

--- best solution ---
source,---, 0 0
sink,---, 13 13
Act[1],---, 4 5--6 6
Act[2],---, 6 7--9 9
Act[3],---, 8 9--10 11--13 13
Act[4],---, 0 0--3 4--5 5
--- tardy activity ---
Act[1]: 1
Act[3]: 7
Act[4]: 1
--- resource residuals ---
writer: [0,13] 0 

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

objective value = 9
cpu time = 0.00/1.00(s)
iteration = 1/45169


Solutions:
    source   ---     0     0
      sink   ---    13    13
    Act[1]   ---     4     6
    Act[2]   ---     6     9
    Act[3]   ---     8    13
    Act[4]   ---     0     5

例題10 作業の並列実行

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

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

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

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

である.

たとえば,

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

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

並列ショップスケジューリング問題において,給油作業(作業時間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 = ex10()
model.optimize()
model.write(folder +"chart10.txt")
 ================ 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 12
objective value = 14 (cpu time = 0.00(s), iteration = 0)
0: 0.00(s): 14/14
objective value = 13 (cpu time = 0.01(s), iteration = 84)

--- best solution ---
source,---, 0 0
sink,---, 13 13
Act[1],---, 0 0--1[3] 1
Act[2],---, 11 11--13 13
Act[3],---, 1 1--3 3
Act[4],---, 1 1--3 3
Act[5],---, 3 3--7 7
Act[6],---, 7 7--11 11
Act[7],---, 7 7--11 11
Act[8],---, 3 3--7 7
Act[9],---, 1 1--12 12
Act[10],---, 11 11--13 13
--- tardy activity ---
sink: 13
--- resource residuals ---
worker: [0,12] 0 [12,13] 1 

--- best activity list ---
source ---
Act[1] ---
Act[9] ---
Act[4] ---
Act[8] ---
Act[5] ---
Act[7] ---
Act[3] ---
Act[6] ---
Act[10] ---
Act[2] ---
sink ---

objective value = 13
cpu time = 0.01/1.00(s)
iteration = 84/12722


Solutions:
    source   ---     0     0
      sink   ---    13    13
    Act[1]   ---     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

例題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 = ex11()
model.optimize()
model.write(folder +"chart11.txt")
 ================ 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 13
objective value = 50 (cpu time = 0.00(s), iteration = 0)
0: 0.00(s): 50/50
objective value = 47 (cpu time = 0.00(s), iteration = 1)
objective value = 45 (cpu time = 0.00(s), iteration = 2)
objective value = 39 (cpu time = 0.00(s), iteration = 3)
objective value = 38 (cpu time = 0.00(s), iteration = 7)

--- best solution ---
source,---, 0 0
sink,---, 38 38
Act[1][1],---, 2 2--3[2] 3--8 8
Act[1][2],Mode[1][2], 8 8--9 10--19 19
Act[1][3],---, 32 32--33 35--38 38
Act[2][1],---, 0 0--9 9
Act[2][2],---, 9 9--10[2] 10--13 13
Act[2][3],Mode[2][3], 21 21--32 32
Act[3][1],---, 14 14--15[2] 15--16 16
Act[3][2],---, 23 23--32 32
Act[3][3],Express, 32 32--33 35--38 38
Act[4][1],Mode[4][1], 0 0--6 6
Act[4][2],---, 10 10--23 23
Act[4][3],---, 23 23--32 32
dummy_activity,---, 8 9
--- tardy activity ---
sink: 38
--- resource residuals ---
machine[1]: [0,2] 1 [2,13] 0 [13,14] 1 [14,16] 0 [16,23] 1 [23,32] 0 [32,1073741823] 1 
machine[2]: [0,6] 0 [6,8] 1 [8,9] 0 [9,10] 1 [10,19] 0 [19,21] 1 [21,33] 0 [33,35] 1 [35,38] 0 
machine[3]: [0,9] 0 [9,10] 1 [10,33] 0 [33,35] 1 [35,38] 0 
manpower: [0,3] 0 [3,5] 2 [5,7] 0 [7,8] 2 [8,9] 1 [9,11] 0 [11,12] 1 [12,15] 0 [15,19] 2 [19,21] 0 [21,23] 1 [23,25] 0 [25,26] 2 [26,28] 0 [28,32] 2 [32,36] 0 [36,40] 2 

--- best activity list ---
source ---
Act[4][1] Mode[4][1]
Act[2][1] ---
Act[1][1] ---
dummy_activity ---
Act[2][2] ---
Act[3][1] ---
Act[1][2] Mode[1][2]
Act[2][3] Mode[2][3]
Act[4][2] ---
Act[3][2] ---
Act[4][3] ---
Act[1][3] ---
Act[3][3] Express
sink ---

objective value = 38
cpu time = 0.00/1.00(s)
iteration = 7/5715


Solutions:
    source   ---     0     0
      sink   ---    38    38
 Act[1][1]   ---     2     8
 Act[1][2] Mode[1][2]     8    19
 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]   ---    14    16
 Act[3][2]   ---    23    32
 Act[3][3] Express    32    38
 Act[4][1] Mode[4][1]     0     6
 Act[4][2]   ---    10    23
 Act[4][3]   ---    23    32
dummy_activity   ---     8     9

例題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 = ex12()
model.optimize()
model.write(folder +"chart12.txt")
 ================ 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 11
objective value = 45 (cpu time = 0.00(s), iteration = 0)
0: 0.00(s): 45/45

--- best solution ---
source,---, 0 0
sink,---, 17 17
act0,---, 0 0--1 1
act1,---, 1 1--2 2
act2,---, 2 2--3 3
act3,---, 7 7--8 8
act4,---, 8 8--9 9
act5,---, 9 9--10 10
act6,---, 14 14--15 15
act7,---, 15 15--16 16
act8,---, 16 16--17 17
--- tardy activity ---
act0: 1
act1: 1
act2: 1
act3: 5
act4: 5
act5: 5
act6: 9
act7: 9
act8: 9
--- resource residuals ---

--- best activity list ---
source ---
act0 ---
act1 ---
act2 ---
act3 ---
act4 ---
act5 ---
act6 ---
act7 ---
act8 ---
sink ---

objective value = 45
cpu time = 0.00/1.00(s)
iteration = 0/4021


Solutions:
    source   ---     0     0
      sink   ---    17    17
      act0   ---     0     1
      act1   ---     1     2
      act2   ---     2     3
      act3   ---     7     8
      act4   ---     8     9
      act5   ---     9    10
      act6   ---    14    15
      act7   ---    15    16
      act8   ---    16    17

例題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 = ex13()
model.optimize()
model.write(folder +"chart13.txt")
 ================ 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 5
objective value = 100 (cpu time = 0.00(s), iteration = 0)
0: 0.00(s): 100/100

--- best solution ---
source,---, 0 0
sink,---, 100 100
Act_D,---, 30 30--60 60
Act_E,---, 70 70--100 100
Act_F,---, 0 0--30 30
Setup_D,Mode_setup_F_D, 30 30
Setup_E,Mode_setup_D_E, 60 60--70 70
Setup_F,Mode_setup_start_F, 0 0
--- tardy activity ---
sink: 100
--- resource residuals ---
line1: [0,100] 0 

--- best activity list ---
source ---
Setup_F Mode_setup_start_F
Act_F ---
Setup_D Mode_setup_F_D
Act_D ---
Setup_E Mode_setup_D_E
Act_E ---
sink ---

objective value = 100
cpu time = 0.00/1.00(s)
iteration = 0/44772


Solutions:
    source   ---     0     0
      sink   ---   100   100
     Act_D   ---    30    60
     Act_E   ---    70   100
     Act_F   ---     0    30
   Setup_D Mode_setup_F_D    30    30
   Setup_E Mode_setup_D_E    60    70
   Setup_F Mode_setup_start_F     0     0

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

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

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

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

ex14[source]

ex14()

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

model = ex14()
model.optimize()
if model.Status >=0:
    model.write(folder +"chart14.txt")
else:
    print("実行不能")
 ================ Now solving the problem ================ 


Solutions:
    source   ---     0     0
      sink   ---    28    28
    Act[1]   ---     0    13
    Act[2]   ---     3    28
    actDum DumMode1     0    28

Dash App

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

  • 作業 act_df
  • 資源 res_df
  • モード mode_df
  • 作業・モード act_mode_df
  • モード・資源 mode_res_df
  • 時間制約 temp_df
  • 再生不能資源の右辺定数と制約の向き non_res_df
  • 再生不能資源の左辺項の情報 non_lhs_df
  • 状態 state_df

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

引数:

  • 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 = ex13()
act_df, res_df, mode_df, act_mode_df, mode_res_df, temp_df, non_res_df, non_lhs_df, state_df = convert(model)
mode_df.head()
name duration breakable parallel state
0 Mode_D 30 {} {} {}
1 Mode_E 30 {} {} {}
2 Mode_F 30 {} {} {}
3 Mode_setup_E_D 50 {} {} {'Setup_State': [(2, 1)]}
4 Mode_setup_start_D 0 {} {} {'Setup_State': [(0, 1)]}

全ての例題のデータフレームを出力する。

# folder = "../data/optseq/"
# ex_list = [ ex1(), ex2(), ex3(), ex4(), ex5(), ex6(), ex7(), ex8(), ex9(), ex10(), ex11(), ex12(), ex13(), ex14() ]
# #ex_list = [ ex1() ]
# ex_name =[ "ex"+str(i) for i in range(1,15)  ]
# 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")

最適化関数 optimize_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)

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秒で、メイクスパンを最小化する。

num = 8
model = ex8()
act_df, res_df, mode_df, act_mode_df, mode_res_df, temp_df, non_res_df, non_lhs_df, state_df = convert(model)
#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,non_res_df,non_lhs_df,state_df)
 ================ 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 = 92 (cpu time = 0.00(s), iteration = 0)
0: 0.00(s): 92/92

--- best solution ---
source,---, 0 0
sink,---, 92 92
Act[1],---, 0 0--13 13
Act[2],---, 0 0--25 25
Act[3],---, 50 50--65 65
Act[4],---, 65 65--92 92
Act[5],---, 50 50--72 72
--- tardy activity ---
sink: 92
--- resource residuals ---

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

objective value = 92
cpu time = 0.00/1.00(s)
iteration = 0/94353


Solutions:
    source   ---     0     0
      sink   ---    92    92
    Act[1]   ---     0    13
    Act[2]   ---     0    25
    Act[3]   ---    50    65
    Act[4]   ---    65    92
    Act[5]   ---    50    72

ガントチャート生成

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

引数:

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

返値:

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

make_gannt[source]

make_gannt(model)

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

make_gannt関数の使用例

fig = make_gannt(model)
#fig.show()
Image("../figure/make_gannt.png")

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

make_resource_graph[source]

make_resource_graph(model)

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

fig = make_resource_graph(model)
#fig.show()
Image("../figure/make_resource_graph.png")

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

make_result_df[source]

make_result_df(model)

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

make_result_df関数の使用例

result_df = make_result_df(model)
result_df.head()

Divの準備

Dash App 本体