Quantum job sequencing algorithm

This repository contains sample code for solving job sequencing problem (JSP) with deadlines using quantum annealing.

Key features include:

• JSP to QUBO converter,
• JSP to linear programming converter,
• Brute-force solver (small scale refence),
• PULP solver (linear programming),
• DWave solver (quantum annealer).

Problem formulation

Input:

• There exists n tasks and 1 worker,
• Worker can execute only 1 task at a time,
• Each task has deadline d_i, runtime t_i and reward p_i,
• Reward is given for each task that completes before deadline,
• Tasks can be executed in any order. Target:
• Find optimal job sequence, that maximizes total reward.

Quick-start

Install dependencies

Prepare random task instance and compute schedule using LP solver (pulp)

You can find job schedule results dict or in

For quantum annealer backend register on D-Wave Leap and insert your API_KEY below: