I. One machine scheduling enviornment
In the one machine schedling
enviornment we have a set J of n jobs, numbered 1,2,....,n and a single
machine that can process at most one job at a time.
Each job j has a processing requirement pj
- namely, it requires processing for a total of pj units
of time on the machine- and an arrival time aj. If each
job must be
processed in an uninterrupted fashion, we have a nonpreemptive
scheduling model, whereas if a job may be processed for a period of time,
interrupted and continued
at a later point in time, we have a preemptive model.
A schedule S for the set J specifies, for each job j, which pj
units of time the machine uses to process
job j. Given a schedule S, we denote the completion
time of job j in schedule S by Cj.
The goal of a scheduling algorithm is to produce a "good
"schedule. Some example metrics for scheduling are:
1.The average completion time of a schedule. This
comes down to minimizing the sum of all the completion times Cj.
2. The makespan of the schedule. The makespan is
defined as Cmax = maxj Cj.
So we want to minimize Cmax.
3. The sum-flow metric. We define the flow time
of a job j as Fj = Cj- aj.
The sum-flow is the sum over j of Fj. The SRPT (Shortest
Remaining Processor Time)
algorithm produces an optimum schedule
for the sum-flow metric.
4. The max-flow metric. We define the max flow
time of a schedule as maxj Fj.
5. The max-stretch metric. We define the stretch
of a job j in a schedule as Fj / pj. The max-stretch
is defined as maxj Fj / pj.
There are many metrics for scheduling. The above
are just a few. For a good introduction to scheduling algorithms
see the below link. Also to find out about
stretch and flow metrics for sceduling see the below
paper.
Some scheduling links:
1. A survey paper
on schedling algorithms. This is a good introduction.
2. On-Line Scheduling -- A Survey
Some papers to read:
1.Michael A. Bender, Soumen Chakrabarti, and S.
Muthukrishnan. Flow and stretch metrics for scheduling continuous job streams.
In Proceedings of the Ninth Annual
ACM-SIAM Symposium on Discrete
Algorithms, pages 270-279, San Francisco, California, 25-27 January 1998.