A Quantum Optimization Algorithm for Single Machine Total Weighted Tardiness Minimization

Abstract

Since quantum computers were proposed in the 1980’s, quantum computing has attracted widespread interest as it appears to be more powerful than classical computing, especially for certain types of problems. One such example of quantum computing’s power is Grover’s quantum algorithm for unstructured searches. Grover’s search algorithm uses quantum mechanics principles to search an unstructured list, in which items are arranged in a completely random manner and no knowledge about the structure of the solution is assumed or used. The algorithm identifies the item in the list satisfying a given condition as the solution. For the unstructured search problem, while the computational complexity of classical algorithms grows at least at the order of the list size, the computational complexity of Grover’s quantum search algorithm only grows at most at the order of the square root of the list size. For this type of problem, quantum computing is more efficient than classical computing. Furthermore, there is another class of search problems in which quantum computing excels, and this class is called the combinatorial search problem or combinatorial optimization problem. In these problems, a cost value is associated with each item in the searching list and the goal is to find the item associated with the minimum (or maximum) cost value. This type of problem is NP-hard and has no known solution using classical computers that has computational complexity increasing in a polynomial relationship to the searching list size. While multiple suboptimal classical algorithms were developed based on classical computers, hoping to find suboptimal solutions with polynomial computational complexity, Trugenberger’s quantum optimization algorithm was proposed for unconstrained combinatorial search problems based on quantum mechanics principles. Its idea, like that of Grover’s quantum search algorithm, is to manipulate quantum parallelism so that the desired solution can be measured with a higher probability compared with nonsolutions. The computational complexity of this quantum optimization algorithm is independent of the list size. However, combinatorial optimization problems with constraints occur in certain practical applications. For example, the total weighted tardiness (TWT) minimization problem, which is a well-known NP-hard problem, can be found in operational planning. This problem requires the construction of a schedule for a single machine with a fixed start time and multiple tasks with various due times that minimizes the sum of weighted tardiness of tasks relative to their respective due times. The problem can be formulated as a constrained combinatorial optimization problem. To solve the TWT minimization problem, we propose a novel efficient quantum optimization algorithm based on Grover’s quantum search algorithm and Trugenberger’s quantum optimization algorithm to ensure that the desired solution satisfying the searching constraints and showing the minimal TWT value in the searching list will be measured with the highest probability. In the proposed quantum optimization algorithm, a more powerful cost function normalization method is also proposed.