Johnson's Rule
From Wikipedia, the free encyclopedia
In operations research Johnson's Rule is a method of scheduling a number of jobs on two successive work centers. The primary objective of Johnson's Rule 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 number of idle time between the two work centers.
Before the technique can be applied, several conditions need to be in place:
- The time for each job must be constant.
- The job times must be mutually exclusive of the job sequence.
- All jobs must go through first work center before going through the second work center.
- There must be no job priorities.
Johnson's Rule is as follows:
- List the jobs and their times at each work center.
- Select the job with the shortest time. If the job is for the first work center, then schedule the job first. If that job is for the second work center then schedule the job last. Break ties arbitrarily.
- Eliminate the job selected from further consideration.
- Repeat steps 2 and 3, working towards the center of the job schedule until all jobs have been scheduled.
In case there is significant idle time at the second work center (from waiting for the job to be finished at the first work center), then job splitting may be used.
[edit] Example
There are 5 jobs. Each job needs to go through work center A and B. Find the optimum sequence of jobs using Johnson's Rule.
| Job | Work Center A | Work Center B |
|---|---|---|
| A | 3.20 | 4.20 |
| B | 4.70 | 1.50 |
| C | 2.20 | 5.00 |
| D | 5.80 | 4.00 |
| E | 3.10 | 2.80 |
1. The smallest time is located in Job B (1.50 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.20 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.80 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.20 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 |
[edit] References
 |
This article does not cite any references or sources. (June 2008) Please help improve this article by adding citations to reliable sources. Unverifiable material may be challenged and removed. |
[edit] Further reading
- S. M. Johnson, Optimal Two- and Three-Stage Production with Setup Times Included, Naval Research Quarterly, (March 1954)
- William J Stevenson, Operations Management 9th Edition, McGraw-Hill/Irwin, 2007
