Johnson's rule
From Wikipedia, the free encyclopedia
From Wikipedia, the free encyclopedia
In operations research, 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.[1]
This article's lead section may be too long. (July 2019) |
The technique requires several preconditions:
Johnson's rule is as follows:
Given significant idle time at the second work center (from waiting for the job to be finished at the first work center), job splitting may be used.
If there are three work centers, Johnson's rules can still be applied if the minimum processing time in the first (and/or the third) work center is not less than the maximum processing time in the second work center. If so, one can create two virtual work center then apply Johnson's rules like for the two work center case.
Each of five jobs 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.2 | 4.2 |
B | 4.7 | 1.5 |
C | 2.2 | 5.0 |
D | 5.8 | 4.0 |
E | 3.1 | 2.8 |
? | ? | ? | ? | B |
C | ? | ? | ? | B |
C | ? | ? | E | B |
C | A | ? | E | B |
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.
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.