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

    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