Job Shop Scheduling Problem

Max B

May 04, 2021 13:05

I'm currently doing some researching on Binary Quadratic Models and Constraint Satisfaction Problems. Specifically, I have been researching to find out how you could make a program that allows a user to implement the Job Shop Scheduling problem to create some schedule.

The program would take in multiple constraints such as the time each job can start, what each job depends on, the length of jobs etc, and find out the most optimized schedule for the day.

I have limited experience making CSPs and BQMs, so I am wondering how hard it would be to create a model that can then be turned into a QUBO and sent to the D-Wave solver. Are problems with this many constraints very complex and take a lot of research?

As a complete noob to this kind of maths, I am wondering if this is worth pursuing any further and if I should instead just use the current D-Wave implementation of a JSP.

Thanks!

Comments

2 comments

Sukhraan S (Report)
May 12, 2021 22:52
Hi Max,

Once you have all your constraints well defined along with the objective you are trying to achieve, you can easily transform a complex constraint satisfaction problem into a BQM (QUBO), without a lot of research. Later, the formulated BQM can be optimized via tuning the parameters as per the QPU's capabilities to produce optimal results (schedules, in the case of Job Shop Scheduling).

For creating schedules with constraints as you mentioned, in addition to reusing the current Job Shop Scheduling implementation (based on the paper present here), I would highly recommend also check the following resources:
- Problem Formulation Guide explains how to incorporate objective and multiple constraints into a single BQM.
- Nurse Scheduling Example generates schedules, incorporating different constraint types
- Building an employee schedule; shows using DQM (Discrete Quadratic Model), instead of BQM, along with Leap's hybrid solver to generate schedules.
- Hybrid Quantum Annealing Heuristic Method for Solving Job Shop Scheduling Problem, by Kurowski K., Wȩglarz J., Subocz M., Różycki R., Waligóra G. (2020), describes another implementation of job-shop scheduling on a D-Wave QPU solver
Lastly, various user-developed scheduling examples on D-Wave's quantum applications page might interest you as well.

I hope this helps! Please let me know if you have any questions.
0

Comment actions Permalink
Marek S (Report)
March 13, 2022 09:19 (Edited March 13, 2022 09:19)

Hi, I'm an author of the Hybrid Quantum Annealing Heuristic Method for Solving Job Shop Scheduling Problem. We have provided an open-source repository with all the code we used. It might be hard to find on your own, so here it is: https://github.com/mareksubocz/QuantumJSP. Hope this helps!

Also, if you need any help, feel free to contact me: marek.subocz@man.poznan.pl.

0

Comment actions Permalink

Please sign in to leave a comment.

Didn't find what you were looking for?

New post