The Scheduling Problem


  RIOT HOME

 Scheduling Problem
 Instructions
 Definitions
 Machine Environments
 Algorithms
 Objectives
 Try It!

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