An R||C_{max} Quantum Scheduling Algorithm
| dc.creator | Lu, Feng | |
| dc.creator | Marinescu, Dan C. | |
| dc.date | 2005-11-03 | |
| dc.date | 2006-09-29 | |
| dc.date.accessioned | 2026-07-07T06:52:39Z | |
| dc.date.available | 2026-07-07T06:52:39Z | |
| dc.description | 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)$. | |
| dc.description | 15 pages | |
| dc.identifier | https://arxiv.org/abs/quant-ph/0511028 | |
| dc.identifier | http://arxiv.org/abs/quant-ph/0511028 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/105366 | |
| dc.subject | Quantum Physics | |
| dc.title | An R||C_{max} Quantum Scheduling Algorithm | |
| dc.type | text |