Introduction

The field of quantum computing has experienced significant growth and interest in recent years due to its potential to provide exponential speedup for certain tasks. While translating this potential into practical applications has been challenging, quantum computing is believed to have disruptive potential in domains such as machine learning, chemical simulations, and optimization. In this study, we focused on the domain of optimization and investigated the application of quantum and quantum-inspired technology to the transport robot scheduling problem (TRSP).

The TRSP is an NP-hard problem that involves planning a time-efficient schedule for a robot as it transports chemical samples between a rack and multiple machines for experiments. This problem is highly relevant for industrial applications, and solving it using classical computing techniques can be challenging for certain instances. Therefore, we explored the potential advantage of using non-classical techniques for solving this problem.

Study Methodology

To compare the performance of different solvers, we conducted a comprehensive case study on a large set of TRSP instances. We considered three solvers: D-Wave’s hybrid Leap framework which utilizes the D-Wave quantum annealer, Fujitsu’s digital annealer, and the industry-grade Gurobi solver. These solvers were evaluated based on their solution quality and runtime.

One key aspect of our study was the use of three different models for the TRSP, each following different design philosophies. This allowed us to explore the different ways in which the problem can be modeled and the differences in the problem formulations accepted by the solvers. While LBQM, FDA, and FDAh models were restricted to a formulation as a quadratic unconstrained binary optimization (QUBO), Gurobi could utilize a mixed integer program (MIP) with integer and float variables, enabling a meaningful comparison of multiple formulations.

Unique Problem Instance

The TRSP studied in this research is a unique combination of different scheduling problems that have not been considered together before. Scheduling problems have been extensively researched for many decades, with classical algorithms and meta-heuristics typically used for solving them. However, due to the NP-hardness of most industrial-relevant scheduling problems, finding efficient solutions can still be challenging.

Our study extends the typical job shop scheduling problem (JSSP) by introducing a robot and additional restrictions. Specifically, it falls into the category of robotic cell scheduling and automated guided vehicles (AGV) scheduling problems. While previous work has focused on infinite cyclic schedules and other variations, our study introduces the constraint that jobs cannot wait at a machine after completion before being picked up by the robot.

Performance Evaluation

The main focus of our study was to evaluate the performance of non-standard solution approaches using quantum or quantum-inspired solvers. These solvers rely on heuristics, making benchmarks for real-world applications a crucial research area. Quantum optimization approaches can be classified into two major groups: gate-based hardware and annealing-based hardware.

Gate-based approaches use parameterized gates to find the ground state of a Hamiltonian related to the optimization problem’s cost function. Quantum approximate optimization algorithm (QAOA) is an example of a gate-based approach. On the other hand, annealing-based approaches aim to find the ground state of a Hamiltonian by achieving an adiabatic change from an easily prepared initial state.

Conclusion

Our case study on the transport robot scheduling problem explored the potential advantages of quantum and quantum-inspired technology for optimization. We compared different solvers and models, considering solution quality and runtime. Promising results were found for the digital annealer and some opportunities for the hybrid quantum annealer in comparison to the classical solver Gurobi.

By providing insights into the workflow for solving application-oriented optimization problems with different strategies, our study contributes to the evaluation of the strengths and weaknesses of different approaches. This research can be useful for industries and researchers aiming to leverage non-classical techniques for solving complex optimization problems.

FAQ

1. What is the transport robot scheduling problem?
   The transport robot scheduling problem is an optimization task that involves planning a time-efficient schedule for a robot as it transports items between different locations.
2. What are some challenges in solving the transport robot scheduling problem?
   The transport robot scheduling problem is an NP-hard problem, which means that finding optimal solutions can be computationally challenging. Additionally, the problem becomes more complex when considering real-world constraints and limitations.
3. How did the study evaluate the performance of different solvers?
   The study compared the solution quality and runtime of different solvers on a large set of problem instances. The solvers considered were D-Wave’s quantum-classical hybrid framework, Fujitsu’s quantum-inspired digital annealer, and Gurobi’s classical solver.
4. What were the main findings of the study?
   The study found promising results for the digital annealer and identified opportunities for the hybrid quantum annealer compared to the classical solver. This suggests the potential advantages of quantum and quantum-inspired technology for solving the transport robot scheduling problem.
5. How can the study’s insights be useful?
   The study provides insights into the workflow for solving optimization problems with different strategies. This can be valuable for industries and researchers looking to leverage non-classical techniques for solving complex optimization problems.