Title

An R || C Max Quantum Scheduling Algorithm

Keywords

Grover search; Quantum algorithm; Scheduling problem

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 O(√M N)while the complexity of its classical counterpart is O(M N). © Springer Science+Business Media, LLC 2007.

Publication Date

6-1-2007

Publication Title

Quantum Information Processing

Volume

6

Issue

3

Number of Pages

159-178

Document Type

Article

Personal Identifier

scopus

DOI Link

https://doi.org/10.1007/s11128-006-0048-8

Socpus ID

34249666019 (Scopus)

Source API URL

https://api.elsevier.com/content/abstract/scopus_id/34249666019

This document is currently not available here.

Share

COinS