# Job Shop Scheduling (Sequencing)

The job shop scheduling models are used to solve one and two machine job shop problems. For the one machine problem the available methods are shortest processing time, first come first serve, due date scheduling, Moore's method, slack time, slack per operation, longest processing time and critical ratio. For two machine scheduling, Johnson's method is used to minimize the makespan.

## One machine scheduling

Consider the following one machine scheduling problem. Five employees are to be trained to operate different machines by a single trainer who can train only one person at a time. The time to train each person varies and is given below as well as due dates and the number of operations involved.
 JOB Time Due Date Number of Operations Janet Barry Alexis Sammy Lisa Ernie 3 days 5 4 7 9 2 4 7 13 10 15 5 2 4 1 2 1 3

Both the data and a solution appear in the screen below.

Methods (Priority rules). The rules available for scheduling include

Shortest processing time (SPT)

First Come First Serve (FCFS)

Earliest due date (Due Date)

Slack time (Slack)

Slack per operation (slack/op)

Moore's Method (Moore)

Longest Processing Time (LPT)

Critical ratio (Crit rat)

The data to be entered are:

Job names. Names can be entered for each job.

Machine name. The word "mach 1." at the top of the column can be changed to give the name of the type of machine. In this example the process has been renamed 'training'.

Processing time. The amount of time that each job will take on each machine is entered in the column labeled with the machine name.

Due date. In some instances due dates are used. These are entered here.

Number of operations. In order to use the slack per operation rule it is necessary to give a positive number of operations. For any other method this column can be ignored.

### Solution

Example 1 - Shortest processing time

The results depend on the rule which is chosen. In our first example we have chosen shortest processing time but in going through the examples all of the information which will be displayed is explained. The output for our first example is shown above.

Job order. A column is displayed which displays when each person (job) will be trained (processed). In Example 1 the column shows that Janet will be second, Barry will be fourth, ..., and Ernie will be first.

Sequence. The same sequence is displayed but in a different manner at the bottom of the screen. In this example the sequence is Ernie followed by Janet followed by Alexis followed by Barry followed by Sammy followed by Lisa.

Flow time. The time at which each job ends is given in a column of flow times. In the example Ernie is the first one trained and ends after its processing time of 2 days. Janet is the second trained and ends after 3 more days at time 5. The last job performed, Lisa, ends after 30 days.

Completion time. If the starting day is not 0 then a column of completion times is given that includes the starting day (see example 8).

Tardiness or lateness. If due dates are given then the difference between the flow time and the due date is displayed. This difference will never be below 0. (There is generally no such thing as early in scheduling.)

Totals. For both the flow time and the lateness the totals are computed and displayed.

Averages. More relevant than the totals are the averages. The average flow time represents the speed with which jobs leaves the system after they have entered. The average lateness (tardiness) represents how badly the schedule is performing with respect to our promised due dates.

NOTE: The average lateness is computed based on all jobs - not just the jobs which are late. In the example it is 34/6 even though Ernie was trained on time.

Average number of jobs in the system. This is computed as the total flow time divided by the maximum flow time.

### Example 2 - First come first serve

If the first come first serve (FCFS) option is toggled then the program will schedule the jobs from top of the list to bottom of the list (not shown here). Notice that the order column is 1, 2, 3, 4, 5 and 6 and the sequence at the bottom is in this order - Janet, Barry, Alexis, Sammy, Lisa, Ernie.

### Example 3 - Schedule according to slack

Slack is defined as the due date minus the time required to process a job. In order to use slack the due date must be given. The slack column did not appear before but does now. It is the difference between the due column and the "training" column. For example, Janet must be trained by day 4 but it takes 3 days to train so there is one day of slack. The jobs are scheduled according to increasing order of slack. Janet has the least and is scheduled first while Alexis has the most (9) and is scheduled last.

### Example 4 - Slack time per operation

We have used the data in the number of operations column. The output (not shown) contains a new column titled slack/op which is generated by dividing the slack by the number of operations. For example the 1 day of slack for job 1 is divided by the 2 operations yielding a slack per operation value of .5. Jobs are scheduled according to increasing order of slack per operation. Therefore, Janet is first (.5) and Alexis is last (9). (Ties are broken arbitrarily.)

### Example 5 - Due date scheduling

Janet is the first one due and is scheduled first while Lisa is the last one due and is scheduled last.

### Example 6 - Moore's method

Moore's method minimizes the number of late jobs. In the example shown below, Moore's method leads to the sequence Janet, Ernie, Lisa, Sammy, Alexis, Barry which has 3 jobs late. No schedule will have fewer than three jobs late.

### Example 7 - Longest Processing Time

The LPT method schedules jobs from longest to shortest. This is typically the worst way to perform scheduling. In the example (not shown), LPT yields the sequence Lisa, Sammy, Barry, Alexis, Janet, Ernie which is exactly opposite the SPT schedule of course. This schedule has an average flow time of 21.5. No schedule will have a larger average flow time. This schedule has 4.3 jobs in the system on average. No schedule will have a larger average number of jobs in the system.

### Example 8 - Critical Ratio

The critical ratio is defined as (due date -today)/processing time. This is the first example in which we have used the starting day number above the data. Jobs are scheduled in ascending order of the critical ratio. In this example the schedule is Janet, Barry, Sammy, Ernie, Lisa, Alexis. Notice in the screen that there is an extra column of output. Namely the finish time. Because jobs do not start at time 0, the flow time and the completion time are different. For example, Janet is the first job done and begins today on day 3. Since it take 3 days we work on Janet on days 3, 4 and 5 which becomes the finish time. The job is one day late.

## Two Machine Scheduling

Consider the problem below
 JOB Typing Duplicating Harry Deb Leah Dara Art Sharon Rivka 20 43 37 62 80 12 25 19 27 38 11 52 36 41

In the screen below we demonstrate the two machine problem. Johnson's method is used and the order and sequence are listed as below.

In addition, the time at which each job ends on each machine is displayed. The largest of all of these times is the makespan, or time at which all work is completed and is displayed at the bottom. In this example it will take 290 minutes to finish all of the work.

### Johnson's Method Steps

A two machine Gantt chart can be displayed also.