Skip to main content

View on GitHub

Open this notebook in GitHub to run it yourself
Consider an optimization problem (based on the formulation in [1]): there are W(t)W(t) available workers or resources and NN jobs, where each job jj requires T(j)T(j) time and takes r(j)r(j) resources to be completed. Given a set of dependencies for each job and that you know which job depends on the completion of others before starting, determine the order of job completion that minimizes the total execution time. Assumptions:
  • A job may occupy only a single timeslot at most: ∀j   T(j)=1\forall j \,\,\, T(j) = 1
  • Given sufficient resources, jobs can start in the same timeslot
  • All resources are identical and the amount of available resources at a current time step is given by the number W(t)W(t)
  • Jobs can only start if all parent jobs are complete
Possible extensions:
  • Separate resources into multiple categories with jobs requiring different types
  • Jobs that take more than one operation

​
Mathematical Modeling

The input of the model is as follows: Define a binary variable for the optimization problem: an tmax×Nt_{max}\times N matrix xx such that xtj={1job j is done on the tth time slot0else\begin{aligned} x_{tj} = \begin{cases} 1 & \text{job } j \text{ is done on the } t_\text{th} \text{ time slot} \\ 0 & \text{else} \end{cases}\\ \end{aligned} Constraints:
  • All jobs must complete exactly once: ∀j∈[1,N]   ∑txtj=1\forall j\in[1,N] \,\,\, \sum_t x_{tj}=1
  • All jobs may use no more than the available resources: ∀t∈[0,tmax]   ∑jxtjrj≤Wt\forall t\in[0,t_{max}] \,\,\, \sum_j x_{tj} r_j \leq W_t
  • Parent jobs must be complete before dependent jobs start: xt1j1xt2j2=0   ∀j1,t1≤t2,j2 depends on j1x_{t_1j_1} x_{t_2j_2} = 0 \,\,\, \forall j_1, t_1\leq t_2, j_2 \text{ depends on } j_1
The objective function to minimize is the total cost function: min⁡x∑txtN⋅t\min_{x} \sum_{t} x_{tN}\cdot t which favors schedules that are done early.

​
Defining the Optimization Model

Visualization helper functions:

​
Initializing a Specific Problem Instance

Create a workflow dependencies graph. For the small instance, all timeslot capacities and workloads are equal to each other:
output This is the resulting Pyomo model:
Output:

​
Optimization Model with Hybrid Classical/Quantum QAOA

​

​
Setting Up the Classiq Problem Instance

To solve the Pyomo model defined above, use the Classiq combinatorial optimization engine. For the quantum part of the Quantum Approximate Optimization Algorithm (QAOA) algorithm (QAOAConfig), define the number of repetitions (num_layers):
For the classical optimization part of the QAOA algorithm, define the maximum number of classical iterations (max_iteration) and the α\alpha-parameter (alpha_cvar) for running CVaR-QAOA, an improved variation of the QAOA algorithm [3]:
Load the model based on the problem and algorithm parameters, which you can use to solve the problem:

​

​
Synthesizing the QAOA Circuit and Solving the Problem

Synthesize and view the QAOA circuit (ansatz) used to solve the optimization problem:
Output:
Output:
Solve the problem by calling the execute function on the quantum program you generated:

​

​
Analyzing the Results

Check the convergence of the run:
output Print the optimization results:
Output:
And the histogram:
Output:
output This is the best solution:
output

​

​
Comparing to a Classical Optimizer Result

Output:
output

​
Large Example

Consider a more elaborate example, involving work with non-uniform workloads and resources:
output
Output:
Output:
Output:
As the search space here is much larger and involves many qubits, the optimizer takes much more time and might not converge to a legal solution. Print the optimization results:
Output:
And the histogram:
Output:
output This is the best solution:
output

​

​
Classical Solution for the Large Problem

Output:
output

​
References

[1] Pakhomchik et. al. (2022). Solving workflow scheduling problems with QUBO modeling. arXiv preprint arXiv:2205.04844.