Schedule a workflow of tasks — an instance of the workflow scheduling problem, a known NP-hard class of scheduling problems — for an industrial use case, in a way that can be represented and solved by quantum, classical, and hybrid quantum-classical algorithms.
QUBOworkflow schedulingNP-harddecomposition methodindustrial use case
Atlas stars stay in the public catalog. Saving this entry to your workspace starts an unstarred private copy.
Schedule a workflow of tasks — an instance of the workflow scheduling problem, a known NP-hard class of scheduling problems — for an industrial use case, in a way that can be represented and solved by quantum, classical, and hybrid quantum-classical algorithms. Pakhomchik, Yudin, Perelshtein, Alekseyenko and Yarkoni investigate the workflow scheduling problem, which they describe as a known NP-hard class of scheduling problems, using problem instances they derive from an industrial use case. They compare several quantum, classical, and hybrid quantum-classical algorithms against those instances. To make the problem solvable by quantum and hybrid methods, they develop a novel QUBO formulation to represent the scheduling problem, and they show how the resulting QUBO's complexity depends on the input problem. To manage that complexity for their specific application, they derive and present a decomposition method, which they say mitigates the complexity, and they report that they demonstrate the effectiveness of the approach. The abstract does not say which of the compared algorithms performs best, or by how much.
Circuit & simulation
problem
encodetransform
algorithm
transformmeasure
readout
measure
What this takes and returns
TakesNothingWhat joins here
No input port at this edge: the record publishes no gate sequence and no register, so there is nothing here to read one off — and unlike a declared hole, nothing has been recorded about what belongs here.
Nothing in the Atlas meets this end.
ReturnsNothingWhat joins here
No output port at this edge: the record publishes no gate sequence and no register, so there is nothing here to read one off — and unlike a declared hole, nothing has been recorded about what belongs here.
Nothing in the Atlas meets this end.
This record publishes no gate sequence and no register, so there is nothing here to read an interface off. Absent rather than empty. See all 152 →
How it works
Pakhomchik, Yudin, Perelshtein, Alekseyenko and Yarkoni investigate the workflow scheduling problem, which they describe as a known NP-hard class of scheduling problems, using problem instances they derive from an industrial use case. They compare several quantum, classical, and hybrid quantum-classical algorithms against those instances. To make the problem solvable by quantum and hybrid methods, they develop a novel QUBO formulation to represent the scheduling problem, and they show how the resulting QUBO's complexity depends on the input problem. To manage that complexity for their specific application, they derive and present a decomposition method, which they say mitigates the complexity, and they report that they demonstrate the effectiveness of the approach. The abstract does not say which of the compared algorithms performs best, or by how much. The Classiq library carries this subject under applications · logistics. The sources read state no complexity bound for this record (The abstract of arXiv:2205.04844, the only source read for this record, states no complexity expression, no big-O bound and no resource count for the algorithm it presents. It names the general problem class as "a known NP-hard class of scheduling problems", presented as an established fact about workflow scheduling in general, not a bound this paper proves. It also states that "the QUBO complexity depends on the input problem", naming a dependency without stating what it is: no formula, no scaling law, and no measure of QUBO size (variable count, term count) is quoted. Its comparison claim is: "We derive problem instances from an industrial use case and compare against several quantum, classical, and hybrid quantum-classical algorithms" — naming that a comparison was run but stating no outcome, no winner, and no number for any of the algorithms compared. Its closing claim is that the authors "demonstrate the effectiveness of the approach", stated without a metric, a number, or a comparison figure. The Classiq index entry this record covers, applications/logistics/task_scheduling_problem, gives a directory path and a file list and states no bound. The field is left empty on purpose rather than filled with a bound written from memory.).
Implementation
Unsupported
workflow-scheduling-qubo.txt
ALGORITHM: Workflow scheduling by QUBO modeling
PROBLEM: Schedule a workflow of tasks — an instance of the workflow scheduling problem, a known NP-hard class of scheduling problems — for an industrial use case, in a way that can be represented and solved by quantum, classical, and hybrid quantum-classical algorithms.
IDEA: Pakhomchik, Yudin, Perelshtein, Alekseyenko and Yarkoni investigate the workflow scheduling problem, which they describe as a known NP-hard class of scheduling problems, using problem instances they derive from an industrial use case. They compare several quantum, classical, and hybrid quantum-classical algorithms against those instances. To make the problem solvable by quantum and hybrid methods, they develop a novel QUBO formulation to represent the scheduling problem, and they show how the resulting QUBO's complexity depends on the input problem. To manage that complexity for their specific application, they derive and present a decomposition method, which they say mitigates the complexity, and they report that they demonstrate the effectiveness of the approach. The abstract does not say which of the compared algorithms performs best, or by how much.
REPORTED COST: Not stated by the sources read
BASIS: The abstract of arXiv:2205.04844, the only source read for this record, states no complexity expression, no big-O bound and no resource count for the algorithm it presents. It names the general problem classas"a known NP-hard class of scheduling problems", presented as an established fact about workflow scheduling in general, not a bound this paper proves. It also states that "the QUBO complexity depends on the input problem", naming a dependency without stating what it is: no formula, no scaling law, and no measure of QUBO size (variable count, term count) is quoted. Its comparison claim is: "We derive problem instances from an industrial use case and compare against several quantum, classical, and hybrid quantum-classical algorithms" — naming that a comparison was run but stating no outcome, no winner, and no number for any of the algorithms compared. Its closing claim is that the authors "demonstrate the effectiveness of the approach", stated without a metric, a number, or a comparison figure. The Classiq index entry this record covers, applications/logistics/task_scheduling_problem, gives a directory path and a file list and states no bound. The field is left empty on purpose rather than filled with a bound written from memory.
DEMONSTRATED BY: the Classiq library entry applications/logistics/task_scheduling_problem
PRIMARY SOURCE: A. I. Pakhomchik, S. Yudin, M. R. Perelshtein, A. Alekseyenko, S. Yarkoni (2022), Solving workflow scheduling problems with QUBO modeling — https://arxiv.org/abs/2205.04844
This is a literature reference record, not an executable circuit.
A reference record, not runnable source. Leona cannot execute it, so it cannot be saved to your Library as a circuit.
Quantum vs classical
Classical baseline
Compare Optimization · Ising encoding with the strongest classical method for the same instance, input budget, and output metric.
Quantum claim
This reference exposes a quantum circuit pattern; it does not imply an application-level speedup without a matched benchmark.
How to compare
Report input loading, circuit depth, repetitions, classical preprocessing, post-processing, and wall-clock time together.
Declared gaps
Nobody has reviewed this record for gaps yet.
Literature & references
Solving workflow scheduling problems with QUBO modeling2022 · A. I. Pakhomchik, S. Yudin, M. R. Perelshtein, A. Alekseyenko, S. Yarkoni
Primary source: it investigates the workflow scheduling problem as a known NP-hard class, derives problem instances from an industrial use case, compares several quantum, classical, and hybrid quantum-classical algorithms against them, develops a novel QUBO representation whose complexity it shows depends on the input problem, and presents a decomposition method to mitigate that complexity. Consult it for the QUBO formulation itself, the decomposition method, the industrial instances, and the comparison's outcome, none of which the abstract states.