n Jobs and Three Machines

The scheduling problem of n jobs and three machines is a common problem in operations management. The goal is to determine the order in which the jobs should be processed on each machine to minimize the total processing time.

One approach to solve this problem is the Johnson’s algorithm for three machines. The algorithm works as follows:

For each job, determine the processing time on each of the three machines.

Create three lists, one for each machine, and sort the jobs in each list based on their processing time on that machine.

Identify the job with the minimum processing time on the first and third machines.

If the minimum processing time is on the first machine, schedule the job first on the first machine, and then on the second machine. If the minimum processing time is on the third machine, schedule the job last on the third machine, and then on the second machine.

Remove the scheduled job from all three lists.

Repeat steps 3-5 until all jobs have been scheduled.

Let’s illustrate the Johnson algorithm for three machines with an example:

Suppose we have four jobs with their respective processing times on three machines as follows:

diff

Job | Machine 1 | Machine 2 | Machine 3

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

1 | 2 | 3 | 5

2 | 1 | 2 | 3

3 | 3 | 1 | 4

4 | 4 | 2 | 1

We start by creating three lists, one for each machine, and sort the jobs in each list based on their processing time on that machine.

For machine 1, we have:

diff

Job | Machine 1

——|———-

2 | 1

1 | 2

3 | 3

4 | 4

For machine 2, we have:

diff

Job | Machine 2

——|———-

3 | 1

2 | 2

4 | 2

1 | 3

For machine 3, we have:

diff

Job | Machine 3

——|———-

4 | 1

2 | 3

1 | 5

3 | 4

Next, we identify the job with the minimum processing time on the first and third machines. In this case, it is job 2, with processing times of 1 on the first machine and 2 on the third machine.

Since the minimum processing time is on the first machine, we schedule job 2 first on the first machine, and then on the second machine. We then remove job 2 from all three lists.

For machine 1, we have:

diff

Job | Machine 1

——|———-

1 | 2

3 | 3

4 | 4

For machine 2, we have:

diff

Job | Machine 2

——|———-

3 | 1

4 | 2

1 | 3

For machine 3, we have:

diff

Job | Machine 3

——|———-

4 | 1

1 | 5

3 | 4

Two Jobs and m- Machine Problems

The scheduling problem of two jobs and m machines is a simple case of job scheduling, where we have to determine the order in which two jobs should be processed on m machines to minimize the total processing time.

One approach to solve this problem is to use brute-force, which involves generating all possible schedules and selecting the one with the minimum total processing time. However, this approach is not practical for large values of m.

Another approach is to use a heuristic algorithm, such as the Johnson’s algorithm, which we can use to schedule two jobs on m machines. The algorithm works as follows:

For each job, determine the processing time on each of the m machines.

Create two lists, one for each job, and sort the machines in each list based on their processing time for that job.

Identify the machine with the minimum processing time for both jobs.

Schedule the job with the minimum processing time on that machine.

Remove the scheduled job from both lists.

Repeat steps 3-5 until all jobs have been scheduled.

Let’s illustrate the Johnson algorithm for two jobs and three machines with an example:

Suppose we have two jobs with their respective processing times on three machines as follows:

diff

Job | Machine 1 | Machine 2 | Machine 3

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

1 | 2 | 1 | 3

2 | 3 | 2 | 1

We start by creating two lists, one for each job, and sort the machines in each list based on their processing time for that job.