dorsal/arxiv
View SchemaAn R||C_{max} Quantum Scheduling Algorithm
| Authors | Feng Lu, Dan C. Marinescu |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/0511028 |
| URL | https://arxiv.org/abs/quant-ph/0511028 |
Abstract
Grover's search algorithm can be applied to a wide range of problems; even problems not generally regarded as searching problems, can be reformulated to take advantage of quantum parallelism and entanglement, and lead to algorithms which show a square root speedup over their classical counterparts. In this paper, we discuss a systematic way to formulate such problems and give as an example a quantum scheduling algorithm for an $R||C_{max}$ problem. $R||C_{max}$ is representative for a class of scheduling problems whose goal is to find a schedule with the shortest completion time in an unrelated parallel machine environment. Given a deadline, or a range of deadlines, the algorithm presented in this paper allows us to determine if a solution to an $R||C_{max}$ problem with $N$ jobs and $M$ machines exists, and if so, it provides the schedule. The time complexity of the quantum scheduling algorithm is $\mathcal{O}(\sqrt{M^N})$ while the complexity of its classical counterpart is $\mathcal{O}(M^N)$.
{
"annotation_id": "a4311a25-4c96-4eed-a71f-a9eb3289f0af",
"date_created": "2026-03-02T18:02:20.017000Z",
"date_modified": "2026-03-02T18:02:20.017000Z",
"file_hash": "e3a325139584a7f7aa49c49befedf5bb7d74b1437346bbadf735cca7ef492c07",
"private": false,
"record": {
"abstract": "Grover\u0027s search algorithm can be applied to a wide range of problems; even\nproblems not generally regarded as searching problems, can be reformulated to\ntake advantage of quantum parallelism and entanglement, and lead to algorithms\nwhich show a square root speedup over their classical counterparts.\n In this paper, we discuss a systematic way to formulate such problems and\ngive as an example a quantum scheduling algorithm for an $R||C_{max}$ problem.\n$R||C_{max}$ is representative for a class of scheduling problems whose goal is\nto find a schedule with the shortest completion time in an unrelated parallel\nmachine environment.\n Given a deadline, or a range of deadlines, the algorithm presented in this\npaper allows us to determine if a solution to an $R||C_{max}$ problem with $N$\njobs and $M$ machines exists, and if so, it provides the schedule. The time\ncomplexity of the quantum scheduling algorithm is $\\mathcal{O}(\\sqrt{M^N})$\nwhile the complexity of its classical counterpart is $\\mathcal{O}(M^N)$.",
"arxiv_id": "quant-ph/0511028",
"authors": [
"Feng Lu",
"Dan C. Marinescu"
],
"categories": [
"quant-ph"
],
"title": "An R||C_{max} Quantum Scheduling Algorithm",
"url": "https://arxiv.org/abs/quant-ph/0511028"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "e568db4c-b86f-49fb-9129-76ae374d2cc5",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}