Question

Suppose we have five jobs to be processed on a single machine. The processing times and the due dates of the jobs are shown below Job 2 3 4 Processing Time 2 6 5 4 Due Date 10 11 15 4 13 Find a schedule that minimizes the number of tardy jobs

Answer 1

Make span = 6+3+5+4+2 = 20

Maximum due date = 15

Maximum due date is less than the Makespan. Therefore, there will be atleast one job, whose flow time will exceed the due date. In other words, there is at least one tardy job, regardless of schedule.

In order to minimize the number of tardy jobs, jobs must be scheduled in such an order that flow time of as many jobs as possible remain less than their due date.

There are two possible schedules, which result in just one tardy job. These schedules are:

(1) 2-3-5-4-1 , and

(2) 2-5-3-4-1

The table showing the calculation of flow time and tardiness is following:

Job Processing Due Flow Time Tardiness time Pidate Di Fi = Di+F-1 Li = MAX(0,Fi-Di) 4 13 3 5 0 0

Flow time of each job is equal to the running sum of processing times of all the jobs from the first job scheduled upto that job. For example, flow time of job 3 in the above sequence = 3+2+5 = 10 . Flow time of Job 1 = 3+2+5+4+6 = 20

Tardiness is the difference between flow time and due date, if flow time is greater than due date, otherwise tardiness is 0

Mathematical formulas are shown in the header.

Using any of these schedules, there is only one tardy job.