Title

An R vertical bar vertical bar C-max quantum scheduling algorithm

Authors

Authors

F. Lu;D. C. Marinescu

Comments

Authors: contact us about adding a copy of your work at STARS@ucf.edu

Abbreviated Journal Title

Quantum Inf. Process.

Keywords

quantum algorithm; scheduling problem; Grover search; MACHINES; Physics, Multidisciplinary; Physics, Mathematical

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 vertical bar vertical bar C-max problem. R vertical bar vertical bar 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 vertical bar vertical bar 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 O(root M-N) while the complexity of its classical counterpart is O(M-N)

Journal Title

Quantum Information Processing

Volume

6

Issue/Number

3

Publication Date

1-1-2007

Document Type

Article

Language

English

First Page

159

Last Page

178

WOS Identifier

WOS:000246769700002

ISSN

1570-0755

Share

COinS