Sequencing problem using Johnson’s algorithm of scheduling n-jobs on 2-machines [Sol]

What Is Johnson’s algorithm?

Objective

Johnson’s algorithm finds an optimal sequence of jobs to reduce both the span and the amount of idle time between two work centers.

Precondition

This kind of problem has the following conditions:

The time for each job must be constant;
Job sequence does not have an impact on job times;
All jobs must go through the first work center before going through the second work center;
There must be no job priorities.

Problem

Here’s an example to explain how Johnson’s algorithm works. Suppose that Andrew and Julie work together to write reports for projects every month. They forgot to check their calendar this month and it turned out that they need to finish as soon as possible. Assume that Andrew writes and edits reports while Julie collates data and draws all the necessary graphs. Julie starts her work on a report as soon as Andrew finishes his part. And Andrew works continuously. Times for the reports (in hours) are as follows. What is the order of the tasks using Johnson’s rule?

Projects	Andrew	Julie
A	4	2
B	3	5
C	5	1
D	7	3
E	8	6

Solve Using Johnson’s rule

We need to list the jobs and their times at each work center. Since above table already gives us the required information. I will move forward to the next step.

The smallest time in Work Center B (Julie in our problem) is located in Job C (1 hour). The smallest time in work center A (Andrew in our case) is located in Job B (3 hours) after eliminating Job C. Therefore, job B will be scheduled first, and Job C will be scheduled last.

Find the next two smallest times after eliminating Job B and C, we will get the below sequence. Please note that this process should be repeated until only one job or no job is left.

The only job left to be considered is Job D and the final job sequence is as below.

Logic to Get Target Cells

There are three elements essential for the Excel solver: target cell, by changing cell, and constraints. If you have already read this article (Deal with sequencing problems using Excel Solver), you will know the job sequence is the “by changing cell” and above preconditions are constraints. The only left thing is, how to get the total time?

The left panel in Figure 2.1 shows you the job sequences of the above problem and their corresponding times. The right panel illustrates the total time. One square represents one hour. For example, Andrew needs 3 hours to finish Job B and we put 3 yellow squares at the beginning of the second row. Since Julie needs 5 hours to finish Job B and she can only start after Andrew finishes Job B, 5 yellow squares were placed after 3 white squares for the third row. White squares represent idle time.

Andrew can only be idle when he finishes all those five jobs and when he is idle, Julie is working. Therefore, the sum of total hours that Julie spends on working and total hours that Julie is idle determines the total time. We already know the total time that Julie will spend on work per the problem. How to calculate Julie’s idle time?

Situation 1

Look at Figure 2.1. When Andrew works on his first job, Julie will be idle. Thus, the time of the first Job for Andrew should be taken into consideration when computing Julie’s idle time. In the 9th hour, Julie is idle again and that state lasts for 3 hours. Since she already finishes her first job and has to wait for Andrew to finish the second job. Well, it seems that time of the second job for Andrew minus the time of the first job for Julie will be the idle time for Julie after she finishes her first job. Similarly, we can use the same logic to get the length of other idle time for Julie.

Situation 2

So far, it looks like that we already get the logic and we can set up our model now. But wait, please. What if Andrew starts the n-th job while Julie is still working on her (n-1)-th job? Figure 2.2 gives you another job sequence.

Look at the job A and job C. 5 hours (that Andrew needs to finish Job C) minus 2 hours (that Julie needs to finish Job A) equals to 3 hours. Per our previous logic, Julie should be idle for 3 hours after she finishes Job A. But if you look at Figure 2.2, you will find that Julie has been idle for only 1 hour. What happened? When Andrew starts on job C, Julie is still working on Job E. 4 hours (that Andrew needs to finish Job A) minus 6 hours (that Julie needs to finish Job E) equals to -2 hours. We need to add -2 and 3 together to get the right idle time.

Situation 3

Let’s move on and see the last kind of situation. 7 hours (that Andrew needs to finish the 5th job) minus 1 hour (that Julie needs to finish the 1st job) equals to 6 hours. 5 hours (that Andrew needs to finish the 4th job) minus 2 hours (that Julie needs to finish the 3rd job) is 3 hours. We don’t need to add 3 into 6 since 3 is greater than 0 per the first kind of situation. Therefore, the idle time will be 6 hours. But Figure 2.3 tells that Julie should finish Job C 5 hours earlier than Andrew finishes Job D. What’s wrong?

Look at Figure 2.3 again, Julie finishes job A (third job) 1 hour later than Andrew finishes job C (fourth job). It means that Julie’s idle time is -1 hour after she finishes job A. if we add 6 and -1 together, we will get 5 hours. Well, what we need to add is minus idle time.

Let’s start from the beginning. The sum of (-3) and (-1) equals to -4. This is inconsistent with Figure 2.3. Julie finishes the second Job 4 hours later than Andrew finishes the third Job. And -4 + 3 equals to -1. This is inconsistent with what we discussed in the previous paragraph.

In summary, there is a chain. We need to start from beginning and compute idle time one after one. When computing, if the previous idle time is less than 0, we need to add previous idle time and results from deduction together.

One more thing that we have to remind you is that minus idle time is only used to compute idle time for the next job. When computing target cell, we need to consider them as 0 since there is no white square.

Summary

Time of the first job in work center A (Andrew in our case) is a default idle time.
Calculate Time of the n-th job in work center A – Time of (n-1)-th job in work center B for n >= 2.
Add the result from step 2 with idle time if the idle time in work center B after (n-1)-thjob finishes is less than 0. Otherwise, the result from step 2 is idle time.
Repeat step 2 and step 3 until we reach the last job in the sequence.
If the idle time computed per above logic is less than 0, the idle time will be considered as 0. Otherwise, leave it as-is.
Add the default idle time and idle time from step 5 to calculate the total idle time.

Case 1 – Get the Order of the Tasks for Students Who Work Together to Write Reports

Problem

The problem here is the same as the above problem which is about writing reports.

Set up the Model

We listed jobs and times in range B2:D7.
In range A3:A7, we will give each job a number. These numbers will be values of “by changing cells”.
Our changing cells are range C10:C14.
Formulas “=VLOOKUP ($B10, $A$2: $D$7, 3, FALSE)” were copied from cell C10 into range C11:C14 to get the time of each job for Andrew.
Formulas “=VLOOKUP ($B10, $A$2: $D$7, 4, FALSE)” was copied from D10 into range D11:D14 to get the time that Julie needs to finish each job.
The formula “=VLOOKUP ($B10, $A$2: $D$7, 2, FALSE)” was copied from A10 into A11:A14 to return the Job name per job number in column B.
The default idle time is C10.
Formulas to compute idle time were listed in range G11:G14.
The formula in range I10:I14 can return 0 if the idle time is less than 0.
The formula “=SUM (D10: D14) + SUM (H10: H14)” in cell D16 is used to get our objective – total time.
Per Johnson’s rule, C10 and D14 should contain the smallest time for Andrew and Julie respectively. The SMALL function was used here to retrieve those two smallest times.

The Fill Solver Parameter dialog box is shown in Figure 3.2. If you don’t know how to open this dialog box, please read this article.
The values in by changing cells should be different from each other. They should be integers between 1 and 5.
The other two constraints are about two smallest times per Johnson’s rule.

Results

After clicking on Solve in the Solver Parameter dialog box, Excel will return results as shown below.
If they work to follow the sequence of B ‑> E ‑> D ‑> A ‑> C, they can finish reports in the least time – 28 hours.
There are a total of 11 hours where Julie will be idle.

Case 2: Get the Order of the Tasks for Companies

Problem

A company is faced with seven tasks that have to be processed through two work centers. Assume the “Center I” works continuously and that they are using Johnson’s rule.

Projects	Center I	Center II
A	2.58	3.47
B	1.66	5.84
C	2.71	2.41
D	5.52	1.99
E	3.38	7.62
F	5.22	1.73
G	2.89	1.11

Set up the Model

Range B12:B18 are ours by changing cells.
The VLOOKUP function was used to retrieve job names into range A12: A18 as the values of “by changing cells”.
The VLOOKUP function was also used to retrieve the time of each job into range C12:C18 and D12:D18 for work center A and work center B, respectively.
Formulas used to get idle time are listed in range G12:G18 and I12:I18.
Our target cell is cell D20.
The SMALL function was used to retrieve two smallest times which will be used as constraints.

The Fill Solver Parameter dialog box is shown below.

Results

After clicking on Solve, Excel will return the results as shown.
The minimized timespan is 25.83 hours. The total idle time for work center B is 1.66 hours.

If you look at results closely, you will find that value in cell C14 is greater than that in cell C15. This violates Johnson’s rule of putting smaller numbers first for work center A. You can try to add some constraints such as “C13 <= C14”, “C14<=C15”, “D17 <= D16” to force Excel to fix this problem automatically. But, we cannot make sure that the constraints are always right or that Solver can return a solution. Additionally, Excel will need more time to return a solution. You can manually change the sequence slightly.

Here are the final results after we exchanged cells C14 and C15. The minimized timespan is still 25.83. This is the final sequence that is the same as per Johnson’s rule.