Dear scheduling researcher,
We are delighted to announce the talk given by Wojciech Bozejko (Poli Wroclawska). The title is "Optimal solving of scheduling problems on D-Wave quantum machines".
The seminar will take place on Zoom on Wednesday, April 12 at 13:00 UTC. Join Zoom Meeting https://cesnet.zoom.us/j/95332759663?pwd=YVNNT3JrWFhzbmQxcFpUczBGM0d4QT09 Meeting ID: 953 3275 9663 Passcode: 208021
You can follow the seminar online or offline on our Youtube channel as well: https://www.youtube.com/channel/UCUoCNnaAfw5NAntItILFn4A The abstract follows. The main disadvantage of calculations on real quantum computers is their non-determinism. For optimization problems, it is possible to get surprisingly good results using Quantum Annealing approach, but without a guarantee of the optimality of the result. Simply put, the quantum machine has not found anything better. In the presentation an approach that provides such a guarantee of optimality is proposed. A solution that is optimal in the strict mathematical sense is generated, without probabilistic considerations. For this purpose, a D-Wave quantum machine is used working as a sampler implementing quantum annealing -- an approach considered as a hardware metaheuristic -- to obtain upper and lower bounds on the value of the objective function of the problem under consideration. Then the mechanism of a Branch and Bound scheme is used and controlled by quantum annealing, which allows us to obtain very quickly -- in constant time for considered instances -- the boundaries of the considered subproblems. The whole idea is an alternately combination of calculations realized on QPU and CPU, allowing us to generate optimal solutions to the NP-hard problems of task scheduling on a single machine with a total weighted tardiness as well as with total number of tardy jobs criteria. The main result is the formulation of the lower bound in a "language" (i.e. mathematical model) understandable by a quantum machine.
The next talk in our series will be: Rainer Kolisch (TU Munich) | April 26 | The Resource-Constrained Project Scheduling Problem with Flexible Resource Profiles: Models, Methods, and Applications. For more details, please visit https://schedulingseminar.com/
With kind regards
Zdenek, Mike and Guohua