For the jobs listed below, which processing sequence would result using Johnsons rule

Purchase a PDF

Purchase this article for $30.00 USD.

How does it work?

1. Select the purchase option.
2. Check out using a credit card or bank account with PayPal.
3. Read your article online and download the PDF from your email or your account.

journal article

Operations Research

Vol. 44, No. 6 (Nov. - Dec., 1996)

, pp. 899-908 (10 pages)

Published By: INFORMS

https://www.jstor.org/stable/171581

Read and download

Log in through your school or library

Purchase article

$30.00 - Download now and later

Abstract

We study a two-machine flowshop in which all processing times are independently and identically distributed, with values known to the scheduler. We are able to describe in detail the expected behavior of the flowshop under optimal and heuristic schedules. Our results suggest that minimizing makespan might be a superfluous objective: random schedules are easier to construct and require significantly less intermediate storage between the machines; moreover, they are known to be asymptotically optimal.

Journal Information

OR professionals in every field of study will find information of interest in this balanced, full-spectrum industry review. Essential reading for practitioners, researchers, educators and students of OR. Computing and decision technology Environment, energy and natural resources Financial services Logistics and supply chain operations Manufacturing operations Optimization Public and military services Simulation Stochastic models Telecommunications Transportation

Publisher Information

With over 12,500 members from around the globe, INFORMS is the leading international association for professionals in operations research and analytics. INFORMS promotes best practices and advances in operations research, management science, and analytics to improve operational processes, decision-making, and outcomes through an array of highly-cited publications, conferences, competitions, networking communities, and professional development services.

Rights & Usage

This item is part of a JSTOR Collection.
For terms and use, please refer to our Terms and Conditions
Operations Research © 1996 INFORMS
Request Permissions

The sequencing problem deals with determining an optimum sequence of performing a number of jobs by a finite number of service facilities (machine) according to some pre-assigned order so as to optimize the output. The objective is to determine the optimal order of performing the jobs in such a way that the total elapsed time will be minimum.

Consider there are jobs 1,2,3,…….,n to be processed through m machines. (Machine A, Machine B, Machine C, ……, Machine n). The objective is to find a feasible solution, such that the total elapsed time is minimum. We can solve this problem using Johnson’s method.  This method provides solutions to n job 2 machines, n job 3 machines, and 2 jobs m machines.

Johnson’s Algorithm:

Johnson’s rule in sequencing problems is as follows:

1. Find the smallest processing time on Machine 1 and Machine 2.
2. a) If the smallest value is in Machine 1 process that job first.
   b) If the smallest value is in the Machine 2  process that job last.
3. a) if the minimum time for both Machine 1 and Machine 2 is equal, then perform the job of Machine 1 first and then the job of Machine 2.
        b) if there is a tie for a minimum time among jobs in Machine 1, select the job corresponding to the minimum of Machine 2 and process it first.
        c) if there is a tie for a minimum time among jobs in Machine 2, select the job corresponding to the minimum of Machine 1 and process it last.
4. And then calculate the total elapsed time( the time interval between starting the first job and completing the last job) and Idle time( the time during which the machine remains idle during the total elapsed time.

In this article, we will understand this problem through n job 2 machines. We have to find the sequence of jobs to be executed in different machines to minimize the total time.

Example:

 Solution: The smallest time is 1 for Machine 1, process it first.

Next, the smallest time is 2 for Machine 2, process it last

The next smallest time is 3 of job 5 but Job 5 is already being processed by Machine 2. Discard it.

Next, the smallest time is 4 for Machine 2, process it last just before J5.

The next smallest time is 5 for job 2  but job 2 is already being processed by Machine 2. Discard it. 

Next, the smallest value is 7 for Machine 2, process it last just before J2.

Next, the smallest value is for Machine 1 & Machine 2, J1 of Machine 1 is already being processed on Machine 2 . So, take J3 of Machine 2 and process it last just before J3.

So, the final sequence of processing the jobs is J4, J3, J1, J2, and J5. 

Total Elapsed Time = 28
Idle time of Machine 1 = 0
Idle time of Machine 2 = 1 (Machine 2 has to wait for Machine 1 for 1 unit during the execution of Job 4.