There are several scheduling procedures in use.
We take the following scheduling example:
1. Shortest Processing Time (SPT) Procedure:
A schedule obtained by sequencing jobs for production in non-decreasing order of processing times is called a shortest processing time (SPT) schedule. This schedule minimizes mean flow time F̅. In addition, the SPT rule also minimizes mean lateness and means waiting time. In the above table, the SPT schedule is,
< 3, 1, 2, 4 >
This shows that job 3 is processed first, followed by jobs, 1, 2, and 4 in that order.
In table 9.2, the calculations for obtaining the flow time for each job are shown. Job 3 is first in the sequence; hence, its completion time is 2 days. Job 1 is started after job 3 is finished and takes 4 days. Thus, the completion time for job 1 is 6 days. The completion times for the remaining jobs are similarly computed. Since all the jobs are available at time zero, the flow time for each job is identical to its completion time. Simply adding the flow time for each job and dividing by 4 compute the mean flow time.
It can be verified that no other sequence can produce a better mean flow time than the sequence obtained by the SPT rule. The optimality of SPT rule can be mathematically proved. By finishing the shorter jobs first, both the turnaround time and the work-in process inventory are reduced. The SPT procedure is simple to implement and provides good results even in the more complex scheduling situations.
2. Due Date (DD) Procedure:
In this procedure, jobs for production are sequenced for production in the order of non-decreasing due dates. In the above example job 2 will be sequenced first because it has the earliest due date. The sequence obtained by this rule is,
< 1, 2, 4, 3 >
The due date procedure minimizes the maximum tardiness. In table 9.3, the computations for individual job tardiness, for the due date sequences are shown. The maximum tardiness is 2 days. No other schedule can produce a tardiness of less than 2 days. For comparison, the maximum tardiness for the SPT schedule is 4 days, as shown in table 9.3.
3. Moore Procedure:
The number of jobs tardy for the SPT schedule is 2 (Table 9.2), and for the DD schedule, it is 3 (Table 9.3). The Moore procedure minimizes the total number of tardy jobs.
This procedure is described in the following steps:
Arrange the jobs in non-decreasing order of their due dates (DD schedule). If this sequence yields one or zero tardy jobs, then the DD schedule is optimal and the procedure stops. In the example, 3 jobs are tardy in the DD schedule (Table 9.3), so we proceed to step 2.
Identify the first tardy job in the DD schedule.
In our example, the first tardy job in the DD schedule is job 2, which is marked by an asterisk (*) in the following schedule:
Identify the longest job for production from among the jobs including and to the left of the job marked with the * in the schedule in step 2. That is, we pick the longest job among the jobs that are completed no later than the completion time of the first tardy job in step 2. In the example, job 1 and 2 are candidates, and since job 2 has the longer processing time of the two, it is identified.
The identified job is removed and the completion times for the remaining jobs are revised:
We now repeat step 2. In our example, all the jobs are now on time, so we terminate the procedure. The Moore Schedule is,
<1, 4, 3, 2 >
which is obtained by simply putting the jobs removed in step 3 at the end of the schedule.
4. Weighted Shortest Processing Time (WSPT) Procedure:
If jobs for production are not of equal importance, then it may be more appropriate to minimize the weighted flow time where wi is the weight associated with the flow time of job i. The weights reflect the relative importance of individual job flow time. For example, if w1 = 1 and w2 = 2, it is as desirable to reduce the flow time of job 1 and 2 days as it is to reduce the flow time of job 2 by 1 day. Considerations of the relative costs of each job, the importance of the customer requiring a job, and so forth will influence the determination of wi, s.
A simple procedure to minimize the weighted flow time is to compute the weighted processing time, pi /wi, for each job. Now, the job with the smallest pi/wi is scheduled first in the sequence. From the remaining jobs for production, the job with the lowest pi/wi is selected and is placed in the second position in the schedule. The procedure is repeated until all of the jobs are scheduled. Essentially, the schedule is obtained by arranging the jobs in order of non-decreasing pi /wi ratios.