Johnson's Rule

Johnson's rule is a method of scheduling jobs in two work centers. Its primary objective is to find an optimal sequence of jobs to reduce makespan (the total amount of time it takes to complete all jobs). It also reduces the amount of idle time between the two work centers. The method minimizes the makespan in the case of two work centers. Furthermore, the method finds the shortest makespan in the case of three work centers if additional constraints are met.

The technique requires several preconditions:


  • The time for each job must be constant.
  • Job times must be mutually exclusive of the job sequence.
  • All jobs must be processed in the first work center before going through the second work center.
  • All jobs are equally prioritized.

Johnson's rule is as follows:


  1. List the jobs and their times at each work center:
  2. Select the job with the shortest activity time. If that activity time is for the first work center, then schedule the job first. If that activity time is for the second work center then schedule the job last. Break ties arbitrarily.
  3. Eliminate the shortest job from further consideration.
  4. Repeat steps 2 and 3, working towards the center of the job schedule until all jobs have been scheduled.

Example:

Each of five jobs needs to go through work center A and B. Find the optimum sequence of jobs using Johnson's rule.
Job times (hours)
Job
Work center A
Work center B
A
3.2
4.2
B
4.7
1.5
C
2.2
5.0
D
5.8
4.0
E
3.1
2.8

1.     The smallest time is located in Job B (1.5 hours). Since the time is in Work Center B, schedule this job last.
Eliminate Job B from further consideration.
 ?
 ?
 ?
 ?
B

2.     The next smallest time is located in Job C (2.2 hours). Since the time is in Work Center A, schedule this job first.
Eliminate Job C from further consideration.
C
 ?
 ?
 ?
B

3.     The next smallest time after that is located in Job E (2.8 hours). Since the time is in Work Center B, schedule this job last.
Eliminate Job E from further consideration.
C
 ?
 ?
E
B

4.     The next smallest time after is located in Job A (3.2 hours). Since the time is in Work Center A, schedule this job first.
Eliminate Job A from further consideration.
C
A
 ?
E
B

5.     The only job left to consider is Job D.


C
A
D
E
B


So, the jobs must be processed in the order C → A → D → E → B, and must be processed in the same order on both work centers.

Implementation:

GitHub:    https://github.com/nowshad7/Johnsons_Rule_Implementation

Comments

Post a Comment

Popular Posts