納期付き機械スケジューリングを QUBO で解く

サンプルかランダムな注文を読み込み、チャートや表で編集して Solve を押します。QUBO++ が、すべての納期を守りつつ処理時間の合計が最小になるように、注文を機械に割り当てます。

解説: relu() と cons(): C++ 版· Python 版

orders
Total processing time–
Late orders–
Total lateness–
Unassigned–
Makespan–
Lower bound–
Drag an order to move it to another machine or to another position. QUBO++ places the orders of each machine in due-date order.

Orders 0

Times are in minutes (multiples of 5, up to 600). Leave a machine blank if it cannot process the order.

# Due Machine 1 Machine 2 Machine 3 Assigned Start – End Status
How it works

Each order is processed on exactly one machine that can handle it. The processing time depends on the machine. Every order should finish by its due date; when that is impossible, every order is still assigned and the total lateness is minimized first. Among the assignments with the smallest total lateness, the total processing time (the sum of the processing times on the chosen machines) is minimized. Putting every order on its fastest machine gives the lower bound, but usually some orders then miss their due dates.

QUBO++ processes the orders of each machine in due-date order, which is always the best way to meet the due dates, so only the assignment has to be decided (you can still reorder them by hand). With a binary variable y[j][m] that is 1 when order j is processed on machine m, order j finishes on machine m at C[j][m] = Σi ≤ j p[i][m]·y[i][m], where i ≤ j runs over the orders with due dates no later than that of j.

  • Each order on exactly one machine: cons(Σm y[j][m] == 1)
  • Lateness of order j on machine m: relu(C[j][m] − d[j] − H[j][m]·(1 − y[j][m])). H[j][m] is the largest possible lateness, so the term is 0 when the order is not on machine m.
  • Objective: minimize W·(total lateness) + Σ p[j][m]·y[j][m]. The weight W makes 5 minutes of lateness cost more than any change in the total processing time, so due dates come first.

QUBO++ handles cons() and relu() directly, so the model has only the assignment variables: no slack variables are needed. The search stops early when it reaches the lower bound, which proves optimality.

QUBO++ model 
Press Solve to build the model.

使い方

このデモは資源の限られた AWS Lambda 上で動いています。 デスクトップ PC 上の QUBO++ は数倍速く動きます。

スケジュールを QUBO にする

注文 $j$ には納期 $d_j$ と、処理できる機械 $m$ ごとの処理時間 $p_{j,m}$ があります。 このデモでは、ありうる組ごとに 1 つのバイナリ変数を使います。 $y_{j,m}=1$ は、注文 $j$ を機械 $m$ で処理することを表します。

各機械では、注文を納期の早い順に処理します。 ある機械の注文をどう並べればすべての納期に間に合うなら、納期の早い順でも間に合います。 したがって、すべての納期を守るスケジュールを取りこぼすことはなく、決めるのは割当てだけになります。 注文を納期の早い順に番号付けすると、注文 $j$ が機械 $m$ で終わる時刻は次のとおりです。

\[C_{j,m} = \sum_{i \le j} p_{i,m}\, y_{i,m}\]

モデルは次のとおりです。

\[\text{最小化}\quad \sum_{j,m} p_{j,m}\, y_{j,m} \;+\; W \sum_{j,m} \mathrm{relu}\big(C_{j,m} - d_j - H_{j,m}(1-y_{j,m})\big) \qquad\text{制約}\quad \sum_{m} y_{j,m} = 1 \ \text{（すべての注文 } j\text{）}\]

ここで $\mathrm{relu}(z)=\max(z,0)$ です。 relu の項は、注文 $j$ を機械 $m$ で処理したときの遅れです。 $H_{j,m}$ はありうる最大の遅れなので、注文が機械 $m$ にないときこの項は 0 になります。 重み $W$ は、5 分の遅れが処理時間の合計のどんな変化よりも大きくなるように選んであります。 そのため、まず納期を守ることが優先され、その次に処理時間の合計が小さくなります。

QUBO++ では、遅れを relu() で、割当てを cons() で書きます。ソルバーはどちらも直接扱います。 そのため、モデルの変数は割当ての変数だけで、スラック変数はありません。 このモデルを、QUBO++ の ABS3 ソルバーが CPU 上で解きます。 探索が下界に達すると、そのスケジュールが最適であることが示されるので、その時点で止まります。 係数が大きくなることがあるので、このデモでは 64 ビットの係数（c64e64）を使っています。

自分のコンピュータで動かす

QUBO++ の Python 版である PyQBPP は、Linux（x86-64・ARM64）と、WSL 経由の Windows で動きます。

pip install pyqbpp

relu() と cons() は 制約のページ で説明しています。 詳しくは インストール を見てください。 QUBO++ で解く問題は、ほかのデモ にもあります。