Which sequencing rule is generally the best for minimizing job flow time?

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 in the accompanying table along with due dates and the number of operations involved.

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

1. Shortest processing time (SPT)
2. First come first serve (FCFS)
3. Earliest due date (Due Date)
4. Slack time (Slack)
5. Slack per operation (slack/op)
6. Moore's method (Moore)
7. Longest processing time (LPT)
8. 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.

Example 1 - Shortest processing time

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

Job order. A column is displayed that shows when each person (job) will be trained (processed). In example 1 the column shows that Janet will be second, Barry 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, Alexis, Barry Sammy and 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 the 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, a column of completion times is given that includes the starting day (see example 8).

Tardiness or lateness. If due dates are given, 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 that 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.

Gantt Chart

A Gantt chart illustrating the scheduling on the machine is available as seen in the following screen.

Example 2 - First come first served

If the first come first served (FCFS) option is selected, 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. The solution appears below.

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 next, Moore's method leads to the sequence Janet, Ernie, Lisa, Sammy, Alexis, Barry which has three 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, completion 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 completion time. The job is one day late.

Two Machine Scheduling

Consider the following problem. A typing center needs to type and print jobs for seven customers. The length of time that each job requires for final corrections (typing) and for printing are displayed in the table. Each job must first have the typing finished before it can be duplicated.

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

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; it is displayed at the bottom. In this example, it will take 290 minutes to finish the work.

Johnson's method steps

A secondary output for this submodel is the display of the order in which jobs were chosen according to Johnson's method. This is displayed in the following screen.

The smallest time among the 14 times was 11 minutes for Dara on Duplicating. Thus, Dara is scheduled last since duplicating is the second machine. The next smallest time among all customers except Dara is 12 for Sharon on Typing. Since Typing is the first process, Sharon is scheduled first. The method continues to find the smallest time of all unscheduled customers and schedules the customer as soon as possible if the time is on Typing and as late as possible if the time is on Duplicating.

A two machine Gantt chart can be displayed also as shown below. If the name of the job is too long for the bar in the chart then it will be truncated. For example, see Sharon on machine 1.

What is the best sequencing rule?

Which rule of sequencing has the shortest job going first?

Which rule chooses the job with least processing time?

Which scheduling rule is expected to give lowest average lateness of job?