The Scheduling Problem

 RIOT HOME Objectives             A brief explanation for the various quantities of interest and the associated problems is given below.   Makespan             Let Ci denote the completion time of the ith job in a batch of n jobs given.  The makespan, Cmax, is defined as,             Cmax = max (C1, C2, … , Cn)             The makespan is the completion time of the last job.             A common problem of interest is to minimize Cmax, or to minimize the completion time of the last job to leave the system.  This criterion is usually used to measure the level of utilization of the machine.   Total (Weighted) Completion Time             Let Ci denote the completion time of the ith job in a batch of n jobs given.  The total completion time is defined as,             n             S   Ci             i=1                 The total completion time is the sum of all the completion times of the jobs.  It is commonly referred to as the flow time.             Let wi denote the weight assigned to the ith job in the a batch of n jobs given.  The total weighted completion time is defined as,             n             S wiCi             i=1                 A common problem is in minimizing the total (weighted) completion time.  This problem allows one to find an indication to the total holding or inventory caused by the schedule.   (Weighted) Mean Flow Time             Let Fi denote the flow time of the ith job in a batch of n jobs given, the mean flow time is defined as ,                       n 1/n *  S Fi               i=1                 Let wi denote the weight assigned to the ith job in a batch of n jobs given, the weighted mean flow time is defined as,                        n                       n             (1/n * S wiFi) / (S wi)                       i=1                   i=1                 The usual problem considered is minimizing the (weighted) mean flow time.  Note that this is equivalent to minimizing the total flow time.   Mean Waiting Time             The waiting time of the a job is the time from arrival to the start of processing.  Let Wi denote the waiting time of the ith job.  The mean waiting time is defined as,                      n             1/n * S Wi                                i=1                 Some of the problems of interest are: 1.     Minimizing the mean waiting time. 2.     Minimizing the maximum waiting time: Min (max (Wi))   Lateness             Some of the problems involving lateness are: 1.     Minimizing the total lateness.  The total lateness is defined as,             n             S Li             i=1 2.     Minimizing the total weighted lateness.  Let wi denote the weight assigned to the ith job.  The total weighted lateness is defined as,                         n                         S wi Li                         i=1 3.     Minimizing the maximum lateness, Lmax.  Lmax is defined as,             Lmax = max (L1, L2, … , Ln) 4.     Minimizing the mean lateness.  The mean lateness is defined as,                      n             1/n * S Li                                i=1 5.     Maximizing the minimum lateness.             Max (min (Li))   Tardiness             Some of the problems involving tardiness are: 1.     Minimizing the maximum tardiness             Min (max (Ti)) 2.     Minimizing the number of tardy jobs.  The number of tardy jobs is defined as,                    n             NT=S d(Ti)                                               i=1                                 where d( x) = 1 if x > 0                                    d( x) = 0 otherwise [ Scheduling Problem Instructions Definitions Machine Environments Algorithms Objectives Try It! ] RIOT HOME Copyright 1999 Professor Dorit S. Hochbaum