The Scheduling Problem |
RIOT HOME
Scheduling Problem |
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_{1}, C_{2}, … , 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 } ^{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 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_{i}C_{i } ^{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 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 } ^{ i=1 } ^{
}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_{i}F_{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 } _{ }^{ i=1 } ^{
}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} ^{i=1 } 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} ^{i=1 } 3.
Minimizing the maximum lateness, L_{max}.
L_{max} is defined as,
L_{max} = max (L_{1}, L_{2}, … , L_{n}) 4.
Minimizing the mean lateness. The
mean lateness is defined as, _{ n } 1/n * S L_{i } ^{ i=1 } 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})^{ } ^{ i=1 } ^{
}where
d( x) = 1 if x > 0 d( x) = 0 otherwise^{ }
RIOT HOME |