How to use
- Sample data loads 12 orders, and Random generates the given number of orders (3 to 50) for which an assignment meeting every due date exists. In the table you can edit the due date of each order and its processing time on each machine (minutes, multiples of 5; leave a machine blank if it cannot process the order), and + Add order adds one.
- Drag an order on the chart to another machine or position, or choose its machine in the table. Fastest machines puts every order on its fastest machine, and Unassign all clears the assignment.
- Choose the Time (1 to 10 seconds) and press Solve. The chart shows the best schedule found so far while the solver runs.
- Late orders are drawn in red with their due dates. The summary shows the total processing time, the number of late orders and their total lateness, the makespan, and the lower bound (the sum of the fastest processing times). QUBO++ model at the bottom shows the model that was solved.
The demo runs on AWS Lambda with limited resources; QUBO++ on a desktop PC is several times faster.
How the schedule becomes a QUBO model
Each order $j$ has a due date $d_j$ and a processing time $p_{j,m}$ on each machine $m$ that can process it. The demo uses one binary variable per possible pair: $y_{j,m}=1$ if order $j$ is processed on machine $m$.
On each machine the orders are processed in due-date order. If some order of the jobs on a machine meets all their due dates, the due-date order does too, so this loses no schedule that meets every due date, and only the assignment has to be decided. With the orders numbered by due date, order $j$ finishes on machine $m$ at
\[C_{j,m} = \sum_{i \le j} p_{i,m}\, y_{i,m} .\]The model is
\[\text{minimize}\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{subject to}\quad \sum_{m} y_{j,m} = 1 \ \text{for every order } j,\]where $\mathrm{relu}(z)=\max(z,0)$. The relu term is the lateness of order $j$ when it is on machine $m$; $H_{j,m}$ is the largest possible lateness, so the term is 0 when the order is not on machine $m$. The weight $W$ makes 5 minutes of lateness cost more than any change in the total processing time, so meeting the due dates comes first and the total processing time second.
QUBO++ writes the lateness with relu() and the assignment with cons(),
and its solvers handle both directly:
the model has only the assignment variables and no slack variables.
The model is solved by the ABS3 solver of QUBO++ running on the CPU.
The search stops early if it reaches the lower bound, which proves that the schedule is optimal.
Because the coefficients can be large, the demo uses 64-bit coefficients (c64e64).
Run it on your computer
PyQBPP, the Python version of QUBO++, runs on Linux (x86-64 and ARM64) and on Windows through WSL:
pip install pyqbpp
The constraints page explains relu() and cons().
See Installation for details,
and the other demos for more problems solved with QUBO++.