Johnson Algorithm for n Jobs and Two Machine

The Johnson algorithm is a method used to solve a scheduling problem involving n jobs and two machines. The goal of the algorithm is to minimize the total processing time.

The Johnson algorithm works as follows:

For each job, determine the processing time on machine 1 and machine 2.

Create a list of all jobs and their processing times on machine 1.

Create a list of all jobs and their processing times on machine 2.

Identify the job with the minimum processing time on both machines. This job will be the first job to be scheduled.

If the minimum processing time is on machine 1, schedule the job first on machine 1. If the minimum processing time is on machine 2, schedule the job last on machine 2.

Remove the scheduled job from both lists.

Repeat steps 4-6 until all jobs have been scheduled.

Let’s illustrate the Johnson algorithm with an example:

Suppose we have four jobs with their respective processing times on machine 1 and machine 2 as follows:

diff

Job | Machine 1 | Machine 2

——|———-|———-

1 | 3 | 5

2 | 1 | 2

3 | 2 | 4

4 | 4 | 1

We start by creating two lists: one for machine 1 and one for machine 2.

For machine 1, we have:

Diff

Job | Machine 1

——|———-

2 | 1

3 | 2

1 | 3

4 | 4

For machine 2, we have:

diff

Job | Machine 2

——|———-

4 | 1

2 | 2

3 | 4

1 | 5

We then identify the job with the minimum processing time on both machines. In this case, it is job 2, with processing times of 1 on machine 1 and 2 on machine 2.

Since the minimum processing time is on machine 1, we schedule job 2 first on machine 1. We then remove job 2 from both lists.

For machine 1, we have:

diff

Job | Machine 1

——|———-

3 | 2

1 | 3

4 | 4

Next, we identify the job with the minimum processing time on both machines, which is job 3. Since the minimum processing time is on machine 1, we schedule job 3 second on machine 1. We then remove job 3 from both lists.

For machine 1, we have:

diff

Job | Machine 1

——|———-

1 | 3

4 | 4

For machine 2, we have:

diff

Job | Machine 2

——|———-

4 | 1

1 | 5

The next job with the minimum processing time on both machines is job 4, with processing times of 4 on machine 1 and 1 on machine 2. Since the minimum processing time is on machine 2, we schedule job