In this video, I'll talk about how to solve the job shop scheduling problem using the
branch and bound method.
The job shop scheduling problem is described as follows.
There are a total of n jobs that must be processed on a single machine.
The duration and the due date of each job are known.
We need to decide the sequence of the jobs to minimize the total delay of all the jobs.
The job shop scheduling problem is a typical combinatorial optimization problem, which
is defined as an optimization problem with a finite number of feasible solutions.
For example, we are trying to process n parts using a cnc machine.
We will feed the parts into the machine in this direction.
We can put any of the n parts in the first position.
That means, we have n options for this position.
We can put any of the n-1 remaining parts in the second position.
That means, we have n-1 options for this position.
Continue in this way.
We have only one remining part for the last position.
Therefore, there are a total of n! feasible solutions for the job shop scheduling problem,
which is a finite number.
Now let's check this example.
Three jobs A, B, C must be processed on a single machine.
The time required to process jobs A, B, and C are 6 days, 4 days, and 5 days, respectively.
The due dates of jobs A, B, and C are on day 8, day 4, and day 12, respectively.
Suppose we will process the jobs in this order, A, B, and C.
The duration of Job A is 6 days.
So it will be completed on Day 6.
The due date of job A is Day 8.
So the delay of the first job, job A, is d1=6-8=-2, which means the job is completed ahead of
time.
So the delay is 0.
Then we start to process Job B.
The duration of Job B is 4 days.
So it will be completed on 6+4, which is Day 10.
The due date of job B is Day 4.
So the delay of the second job, job B, is d2=10-4=6, which means the job is delayed
for 6 days.
After that, we start to process job C. The duration of Job C is 5 days.
So it will be completed on 6+4+5, which is Day 15.
The due date of job C is Day 12.
So the delay of the third job, job C, is d3=15-12=3, which means the job is delayed for 3 days.
The total delay of this sequence is T=d1+d2+d3=9 days.
This is just one feasible sequence.
We need to find the best sequence to process the jobs so that the total delay of the three
jobs is the smallest.
We can solve this problem using the branch and bound method.
First, let's define the decision variables.
xij = 1 if job j is put in the ith position; xij = 0 otherwise.
i denotes the positions, 1, 2, and 3; j denotes the jobs, A, B, and C.
At the beginning, we don't know which job should be put in which position.
We don't know the delay of any job.
We do not know the total delay, either.
Now let's start with the last position, position 3.
We can put job A here.
We can also put job B or job C here.
There are three options.
For this option, we know that no matter what orders are for the first two positons, job
A will always be completed on day 15, which is the sum of the durations of all three jobs,
6+4+5.
Job A is due on Day 8.
So the delay will be 15-8=7 days.
So d3=7 days.
The total delay is d1+d2+d3.
So it must be greater than or equal to 7 days.
Similarly, for this option, we can get d3=11 days, and the total delay must be greater
than or equal to 11 days.
For this option, d3=3 days, and the total delay must be greater than or equal to 3 days.
Next, we will follow this branch and check the second position because the total delay
is smaller and it is highly possible to get a better solution compared to the other two
branches.
There is no guarantee though.
We can put either job A or job B in the second position.
So there are two options.
For this option, we know that the total length of processing these three jobs will be 6+4+5,
which is 15 days.
Job C will need 5 days to process.
So the completion time of job A is 15-5, which is day 10.
Job A is due on Day 8.
So the delay will be 10-8=2 days.
So d2=2 days.
The total delay is d1+d2+d3.
So it must be greater than or equal to 2+3=5 days.
Similarly, for this option, we can get d2=6 days, and the total delay must be greater
than or equal to 6+3=9 days.
We are not done yet.
Next, we will follow this branch and check the first position.
We can only put job B in the first position.
So there is only one option.
For this option, we know that the total length of processing these three jobs will be 15
days.
Job C will need 5 days to process, and job A will need 6 days to process.
So the completion time of job B is 15-5-6= day 4.
Job B is due on Day 4.
So the delay will be 4-4=0 days.
So d1=0 days.
The total delay is d1+d2+d3.
So it is equal to 5 days.
Last, let's check other branches.
We know that 5 days is less than 7 days.
So this branch is fathomed.
Similarly, the other two branches are also fathomed.
This is the optimal solution.
The best order is B, A, and C. The total delay is 5 days.
Okay, that is how to solve the job shop scheduling problem.
Thanks for watching.