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 C_i denote the completion time of the i^th job in a batch of n jobs given.  The makespan, C_max, is defined as,

            C_max = max (C₁, C₂, … , C_n)

            The makespan is the completion time of the last job.

            A common problem of interest is to minimize C_max, 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 C_i denote the completion time of the i^th job in a batch of n jobs given.  The total completion time is defined as,

            _n

            S   C_i

            ⁱ⁼¹

                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 w_i denote the weight assigned to the i^th job in the a batch of n jobs given.  The total weighted completion time is defined as,

            _n

            S w_iC_i

            ⁱ⁼¹

                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 F_i denote the flow time of the i^th job in a batch of n jobs given, the mean flow time is defined as ,

                      _n

1/n *  S F_i

              ⁱ⁼¹

                Let w_i denote the weight assigned to the i^th job in a batch of n jobs given, the weighted mean flow time is defined as,

                       _{n                       n}

            (1/n * S w_iF_i) / (S w_i)

                      ^{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 W_i denote the waiting time of the i^th job.  The mean waiting time is defined as,

                     _n

            1/n * S W_i

                               ⁱ⁼¹

                Some of the problems of interest are:

1.     Minimizing the mean waiting time.

2.     Minimizing the maximum waiting time: Min (max (W_i))

Lateness

            Some of the problems involving lateness are:

1.     Minimizing the total lateness.  The total lateness is defined as,

            _n

            S L_i

            ⁱ⁼¹

2.     Minimizing the total weighted lateness.  Let w_i denote the weight assigned to the i^th job.  The total weighted lateness is defined as,

                        _n

                        S w_i L_i

                        ⁱ⁼¹

3.     Minimizing the maximum lateness, L_max.  L_max is defined as,

            L_max = max (L₁, L₂, … , L_n)

4.     Minimizing the mean lateness.  The mean lateness is defined as,

                     _n

            1/n * S L_i

                               ⁱ⁼¹

5.     Maximizing the minimum lateness.

            Max (min (L_i))

Tardiness

            Some of the problems involving tardiness are:

1.     Minimizing the maximum tardiness

            Min (max (T_i))

2.     Minimizing the number of tardy jobs.  The number of tardy jobs is defined as,

                   _n

            N_T=S d(T_i)

                                              ⁱ⁼¹

                                where d( x) = 1 if x > 0

                                   d( x) = 0 otherwise