operations research Operations research () (U.S. Air Force Specialty Code: Operations Analysis), often shortened to the initialism OR, is a branch of applied mathematics that deals with the development and application of analytical methods to improve management and ...

, Johnson's rule is a method of scheduling jobs in two work centers. Its primary objective is to find an optimal

sequence In mathematics, a sequence is an enumerated collection of objects in which repetitions are allowed and order matters. Like a set, it contains members (also called ''elements'', or ''terms''). The number of elements (possibly infinite) is cal ...

of jobs to reduce

makespan In operations research Operations research () (U.S. Air Force Specialty Code: Operations Analysis), often shortened to the initialism OR, is a branch of applied mathematics that deals with the development and application of analytical methods t ...

(the total amount of time it takes to complete all jobs). It also reduces the amount of

idle Idle generally refers to idleness, a lack of motion or energy. Idle or ''idling'', may also refer to: Technology * Idle (engine), engine running without load ** Idle speed * Idle (CPU), CPU non-utilisation or low-priority mode ** Synchronou ...

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.

Algorithm

The

technique Technique or techniques may refer to: Music * The Techniques, a Jamaican rocksteady vocal group of the 1960s * Technique (band), a British female synth pop band in the 1990s * ''Technique'' (album), by New Order, 1989 * ''Techniques'' (album), by ...

requires several preconditions: * The time for each job must be invariant with respect to when it is done. * Job times must be independent of the job

. * All jobs must be processed in the first work center before going through the second work center. * All jobs are equally prioritised. Johnson's rule is as follows: # List the jobs and their times at each work center. # 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. # Eliminate the shortest job from further consideration. # Repeat steps 2 and 3, working towards the center of the job schedule until all jobs have been scheduled. Given significant

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.

Example

Each of five jobs needs to go through work center A and B. Find the optimum sequence of jobs using Johnson's rule. 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.

Notes

References

*{{cite book, url=https://books.google.com/books?id=6ORuBRNk_Z8C&pg=PA302 , title=Heuristic Scheduling Systems: With Applications to Production Systems and ... - Thomas Morton, David W. Pentico - Google Książki , date=2001-07-20 , isbn=9780471578192 , accessdate=2012-09-26, last1=Morton , first1=Thomas , last2=Pentico , first2=David W. j

Algorithm

Example

Notes

References

Further reading