Job Shop Scheduling Problem

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.




  • 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:

    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.

    Comment actions Permalink
  • 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: Hope this helps! 

    Also, if you need any help, feel free to contact me:

    Comment actions Permalink

Please sign in to leave a comment.

Didn't find what you were looking for?

New post