Single Process – Notations, Definition and Objective Functions

Each job in the single processor scheduling model is described by two parameters:

pi= Processing time for job i
di = Due date for job i

In addition, in some cases, ri, the ready time, release time, or arrival time of job i may be useful. In the models discussed here, all jobs are available for processing at time zero and hence ri =0 for all jobs.

The definition of pi includes set up time for job i. If job i is defined as a lot of several identical pieces, then pi will denote the time required to process the complete lot. The due date, di, may be set by customer requirements or by internal planning considerations. We will consider the due date to the time by which a job must be completed; otherwise the job will be deemed late.

Several variables determine the solution of a scheduling decision. Some of the more important of these are

Wi = Waiting time for job i
Ci = Completion time of job i
Fi = Flow time of job i
Li = Lateness of job i
Ti= Tardiness of job i
Ei = Earliness of job i

Wi is the amount of time job i has to wait its processing begins. The first job on the schedule will have zero waiting time, and the second job on the schedule will have to wait by the amount of the processing time of the first job. Ci is simply the time at which the processing of job i is completed. Fi is the amount of time a job spends in the system; thus, Fi = Ci – ri. Since in our case ri = 0, Fi = Ci. Lateness, Li is the amount of time by which the completion time of job i exceeds its due date. Thus Li = Ci – di. Note that Li can be either positive or negative. A positive lateness represents a violation of the due date and is called tardiness, Ti. Similarly, a negative lateness represents the completion of a job before its due date and is called earliness Ei. Thus, the three measures of schedule, Li, Ti and Ei, measure the deviation of the completion time from the date. Since there is often a penalty associated with not meeting due dates, the tardiness measure is usually used. However, in some cases there may be a penalty for being either too early or too late (e.g. crop harvesting), so both tardiness and earliness measures may be useful.

Criteria and objective functions for scheduling:

Several criteria can be employed to evaluate the performance of a schedule. The scheduling criteria chosen in a given situation depend on the objective function of the manager. For example, the underlying objective function or cost function of the company may be such that a penalty is associated with a tardy job, but once a job is delayed, the amount of tardiness does not influence the cost. In this situation, a scheduling criterion that minimizes the number of tardy jobs will be most appropriate for selecting an optimal schedule.

Suppose there are n jobs to be scheduled. Some commonly employed criteria are described in the following material:

Mean flow time = F = 1 / n Σ Fi

Where n = i to 1

This criterion measures the average amount of time that a job spends in the system. Minimization of F is appropriate when rapid turnaround is required and when the objective is to keep a low in-process inventory. Rapid turnaround may provide a competitive advantage to the company when customers are sensitive to fast deliveries.

Mean tardiness = T = 1 / n ΣTi

Where n = i to 1

This criterion is useful when the objective function of the company includes a penalty per unit of time if job completion is delayed beyond a specified due date. For example, a penalty of $ X per day may be imposed for each job that is delayed beyond its specified due date.

Maximum tardiness = Tmax = max { Ti }

To compute maximum tardiness, the tardiness for each job is calculated. The job that has the largest of all the jobs determines Tmax. For example T1 = 3, T2 = 5, T3 = 1, T4 = 4 and Tmax = 5 and is determined by job 2. This criterion is useful when the penalty per day for tardiness increases with the amount of tardiness.

Number of tardy jobs = nT

This criterion simply counts the total number of jobs that are not completed by their due dates.