Operations Research 09D: Job Shop Scheduling Problem

Textbooks:
amzn.to/2VgimyJ
amzn.to/2CHalvx
amzn.to/2Svk11k
In this video, I'll talk about how to solve the job shop scheduling problem using the branch and bound method.
----------------------------------------
Smart Energy Operations Research Lab (SEORL): binghamton.edu/...
RUclips CHANNEL: / yongtwang

[@YongWang]

Hi Guys, please comment and let me know what you think about this Operations Research Open Course. Your feedback is really appreciated. If you enjoy the video, please subscribe and share. All my replies here are only related to the content in my own videos. I am afraid I won't be able to answer other questions. Thanks for your understanding.

[@ultralooter]

You are a legend! Making good education accessible for everyone. The example is minimalistic, understandable, complete, and reproducible. Also, you have taken the time into not wasting the time of your audience by keeping your video's compact. 10/10.

[@junminnie]

is it possible to solve this problem using linear programming on excel solver?

[@KingZeeOfficial]

So you basically just sort them by closest due date? What's the goal of using the B&B and make it look this complicated?

[@YongWang]

Zakkari, Thanks for the comments and this is a great question. I'll pin it to the top.
Let's see another example. We can change the due date of Job A from day 8 to day 3. That means Job A is doomed to be late because the duration is still 6 days.
Do we process Job A, then Job B, and then Job C? Or is there a better way with a shorter total delay? If you follow the same branch and bound procedure, you will find that the sequence B, A, C, which leads to a total delay of 10 days, is better than the sequence A, B, C, which leads to a total delay of 12 days.
That is why we shouldn't just use the due date to determine the best sequence.

[@KingZeeOfficial]

Thanks for your reply. I never said I sorted the jobs by due date, but specifically by "closest due date". Closest means the difference between each job duration and its due date.
For the example in the video, that would be :
|8 - 6|= 2
|4 - 4| = 0
|12 - 5| = 7
Making it B,A,C like the result in the video.
Maybe I should have explained better, but it also works for the example in your comment :
|3-6| = 3
|4-4| = 0
|12-5| = 7
Making the optimal solution still B,A,C.
Here's a visualization of how my algorithm works :
gfycat.com/SplendidSmoothAndalusianhorse

[@alberthebe9710]

For this problem, the Earliest Due Date (EDD)-Priorityrule only leads to optimal schedules when the due dates of all jobs are equal to 0.

[@rrMaxwell]

thanks man understood in one go

[@backofloca5326]

How to do this in AMPL?

[@ozgekayaa]

Thank you soo much

[@divarepro]

Thanks for the video but i have a question. Is this solution linear or not?

[@antywirus222]

No, it's not. It's linear only in optimistic scenario where the greedy approach yields the optimum (with this method you can verify this by comparing the result with lower bounds on other branches). However, most of the time you'll be forced to check other branches, so that means comparing some fraction of all of the branches, which leads to O(n!) complexity.

[@hsankram1637]

goood very thanks

[@YongWang]

Thanks

[@adarshbhat857]

BCA is the optimum sequence.
B = 0 (4-4)
C = -3(9-12)
A = 7(15-8)
=> 0+7-3 = 4

[@cristianriossedano921]

No, it's not. A negative delay is considered zero when you sum all delays. It does not matter if you finish a job earlier, it does not compensate the delay of the other jobs :)

[@alberthebe9710]

If a job is finished earlier than its due date, you set his delay to zero. The delay can't be negative.

[@fadelramadan6646]

how can you apply this when you have for example 15 job with multiple due dates and duration I think it will be really complicated dealing with much inputs

[@YongWang]

Fadel, Thanks for the comments. We just use this simple example is to manually illustrate the algorithm for solving this type of problems. You may have to rely on computer software for larger problems.

[@atohtheo5605]

you need to use a programming software like Python on Gantt Programming.

[@laxmanMarathe]

Prof Wang - How do you know the due dates of the jobs even before scheduling them? You are in a catch 22 situation. Due date is decided by limited capacity the factory to process jobs. I have already cracked the scheduling problem for any complex job shops that starts with due date prediction that is predicted considering existing job load.
A job shop is an ongoing concern - jobs keep coming in regularly with already a set of existing jobs under execution. Factor manager must first confirm a delivery date before accepting any new job. A static solution like you suggest is worthless in real life.