組立てラインバランシングモデル

組立てラインバランシング問題の定式化と解法

ベンチマーク問題例の読み込み

組立ラインバランシング問題（assembly line balancing problem: ALBP）のベンチマーク問題例を用いる．

この問題は以下のように定義される．

タスクの集合を、ステーションと呼ばれるグループにまとめる必要がある。各タスクには一定の処理時間が必要である。 あるタスクが完了していないと実行できないタスク（先行制約）も存在する。 各ステーション内のタスクの処理時間の合計が所定の制限を超えてはならない。 問題の目的、サイクルタイム制約とタスクの順序を満たしながらステーションの数を最小化することである。

---

source

read_instance

 read_instance (instance_file)

---

source

read_elem

 read_elem (filename)

folder = "../data/alb/"
instance_file= "instance_n20_1.alb"
instance_file= "instance_n20_99.alb"
nb_tasks, max_nb_stations, cycle_time, processing_time, successors = read_instance(folder+instance_file)
print("タスク数=", nb_tasks)
print("最大ステーション数=", max_nb_stations)
print("サイクル時間=", cycle_time)
print("処理時間=", processing_time)
print("後続タスク=", successors)

タスク数= 20
最大ステーション数= 20
サイクル時間= 1000
処理時間= [730, 589, 474, 390, 462, 496, 480, 425, 545, 562, 438, 702, 439, 285, 511, 483, 468, 654, 534, 552]
後続タスク= {0: [12], 1: [2, 3, 4, 5], 2: [12], 3: [12], 4: [6, 7], 5: [8, 13], 6: [12], 7: [8, 9, 10, 11], 8: [12], 9: [19], 10: [12, 13, 14], 11: [12], 12: [15, 16, 17, 18], 13: [19]}

定式化と数理最適化ソルバーによる求解

集合

• \(N\): タスクの集合
• \(S\): ステーションの候補の集合
• \(SUCC_i\): タスク \(i\) の後続タスクの集合

パラメータ

• \(CT\): サイクル時間
• \(p_i\): タスク \(i\) の処理時間

変数

• \(y_s\): ステーション \(s\) を開設するとき \(1\) の \(0\)-\(1\) 変数
• \(x_{is}\): タスク \(i\) をステーション \(s\) に割り当てるとき \(1\) の \(0\)-\(1\) 変数

minimize

\[ \sum_{s \in S} s y_s \]

subject to

\[ \sum_{s \in S} x_{is} = 1 \quad \forall i \in N \]

\[ \sum_{i \in N} p_i x_{is} \leq CT y_s \quad \forall s \in S \]

\[ x_{tj} \leq \sum_{s \leq t} x_{si} \quad \forall i \in N, j \in SUCC_i, s \in S \]

---

source

alb

 alb (nb_tasks, max_nb_stations, cycle_time, processing_time, successors)

alb(nb_tasks, max_nb_stations, cycle_time, processing_time, successors)

Gurobi Optimizer version 10.0.0 build v10.0.0rc2 (mac64[x86])

CPU model: Intel(R) Xeon(R) W-2140B CPU @ 3.20GHz
Thread count: 8 physical cores, 16 logical processors, using up to 16 threads

Optimize a model with 580 rows, 420 columns and 7030 nonzeros
Model fingerprint: 0x65067942
Variable types: 0 continuous, 420 integer (420 binary)
Coefficient statistics:
  Matrix range     [1e+00, 1e+03]
  Objective range  [1e+00, 2e+01]
  Bounds range     [1e+00, 1e+00]
  RHS range        [1e+00, 1e+00]
Found heuristic solution: objective 139.0000000
Presolve removed 192 rows and 81 columns
Presolve time: 0.03s
Presolved: 388 rows, 339 columns, 3595 nonzeros
Variable types: 0 continuous, 339 integer (339 binary)

Root relaxation: objective 5.182112e+01, 289 iterations, 0.00 seconds (0.00 work units)

    Nodes    |    Current Node    |     Objective Bounds      |     Work
 Expl Unexpl |  Obj  Depth IntInf | Incumbent    BestBd   Gap | It/Node Time

     0     0   51.82112    0   39  139.00000   51.82112  62.7%     -    0s
H    0     0                      89.0000000   51.82112  41.8%     -    0s
H    0     0                      71.0000000   51.82112  27.0%     -    0s
     0     0   53.18534    0   59   71.00000   53.18534  25.1%     -    0s
H    0     0                      68.0000000   53.18534  21.8%     -    0s
     0     0   53.41056    0   59   68.00000   53.41056  21.5%     -    0s
     0     0   54.04432    0   56   68.00000   54.04432  20.5%     -    0s
     0     0   54.04432    0   53   68.00000   54.04432  20.5%     -    0s
     0     0   54.04432    0   40   68.00000   54.04432  20.5%     -    0s
     0     0   54.04432    0   48   68.00000   54.04432  20.5%     -    0s
     0     0   54.04432    0   38   68.00000   54.04432  20.5%     -    0s
H    0     0                      66.0000000   54.04432  18.1%     -    0s
     0     2   54.04432    0   38   66.00000   54.04432  18.1%     -    0s

Cutting planes:
  Gomory: 15
  Cover: 14
  Implied bound: 1
  Clique: 4
  MIR: 24
  StrongCG: 23
  Flow cover: 18
  Zero half: 11

Explored 1801 nodes (74398 simplex iterations) in 2.40 seconds (1.95 work units)
Thread count was 16 (of 16 available processors)

Solution count 5: 66 68 71 ... 139

Optimal solution found (tolerance 1.00e-04)
Best objective 6.600000000000e+01, best bound 6.600000000000e+01, gap 0.0000%
Opt.value = 66.0
Station 0 : [1, 3] total= 979.0
Station 1 : [4, 5] total= 958.0
Station 2 : [2, 6] total= 954.0
Station 3 : [0] total= 730.0
Station 4 : [7, 9] total= 987.0
Station 5 : [8, 10] total= 983.0
Station 6 : [13, 14] total= 796.0
Station 7 : [11] total= 702.0
Station 8 : [12, 19] total= 991.0
Station 9 : [18] total= 534.0
Station 10 : [15, 16] total= 951.0
Station 11 : [17] total= 654.0

defaultdict(list,
            {0: [1, 3],
             1: [4, 5],
             2: [2, 6],
             3: [0],
             4: [7, 9],
             5: [8, 10],
             6: [13, 14],
             7: [11],
             8: [12, 19],
             9: [18],
             10: [15, 16],
             11: [17]})