The Scheduling Problem 
RIOT HOME
Scheduling Problem 
Algorithms
A brief explanation of each algorithm available on this site is provided
below. List
Scheduling Algorithms
This class of algorithms arranges jobs on a list according to some rule.
The next job on the list is then assigned to the first available machine.
The following are the rules that are available on this site. Random
List
This list is made according to a random permutation. Longest
Processing Time (LPT)
The longest processing time rule orders the jobs in the order of
decreasing processing times. Whenever
a machine is freed, the largest job ready at the time will begin processing.
This algorithm is a heuristic used for finding the minimum makespan of a
schedule. It schedules the longest
jobs first so that no one large job will "stick out" at the end of the
schedule and dramatically lengthen the completion time of the last job.
Shortest
Processing Time (SPT)
The shortest processing time rule orders the jobs in the order of
increasing processing times. Whenever
a machine is freed, the shortest job ready at the time will begin processing.
This algorithm is optimal for finding the minimum total completion time
and weighted completion time. In
the single machine environment with ready time at 0 for all jobs, this algorithm
is optimal in minimizing the mean flow time, minimizing the mean number of jobs
in the system, minimizing the mean waiting time of the jobs from the time of
arrival to the start of processing, minimizing the maximum waiting time and the
mean lateness. Weighted
Shortest Processing Time (WSPT)
The weighted shortest processing time rule is a variation of the SPT
rule. Let t[i] and w[i] denote the
processing time and the weight associated with the ith job to be done in the
sequence ordered by the WSPT rule. WSPT
sequences jobs such that the following inequality holds,
t[1]/w[1] <= t[2]/w[2] <= … <=t[n]/w[n]
In the single machine environment with ready time set at 0 for all jobs,
the WSPT minimizes the weighted mean flow time. Earliest
Due Date (EDD)
In the single machine environment with ready time set at 0 for all jobs,
the earliest due date rule orders the sequence of jobs to be done from the job
with the earliest due date to the job with
the latest due date. Let d[i]
denote the due date of the ith job in the ordered sequence .
EDD sequences jobs such that the following inequality holds,
d[1] <= d[2] <= …d[n]
EDD, in the above setting, finds the optimal schedule when one wants to
minimize the maximum lateness, or to minimize the maximum tardiness. Minimum
Slack Time (MST)
The minimum slack time rule measures the "urgency" of a job by
its slack time. Let d[i] and t[i] denote the due date and the processing time
associated with the ith job to be done in the ordered sequence.
MST sequences jobs such that the following inequality holds,
d[1]t[1] <= d[2]t[2] <= … <= d[n]t[n]
In the single machine environment with ready time set at 0, MST maximizes
the minimum lateness. Other
Algorithms Hodgson's
Algorithm
Hodgson's Algorithm minimizes the number of tardy jobs in the single
machine environment with ready time equal to zero.
Let E denote the set of early jobs and L denote the set of late jobs.
Initially, all jobs are in set E and set L is empty.
Step 1: Order all jobs in the set E using EDD rule.
Step 2: If no jobs in E are late, stop; E must be optimal.
Otherwise, find the first late job in E.
Let this first late job be the k^{th} job in set E, job [k].
Step 3: Out of the first k jobs, find the longest job.
Remove this job from E and put it in L.
Return to step 2. Johnson's
Algorithm
Johnson's Algorithm minimizes the makespan in a flow shop with two
machines, given all ready times equal to zero and nonpreemption.
In a flow shop with two machines, the optimal schedule has the same
ordering of jobs on each machine.
This algorithm is based on the theorem that says that job i should
precede before job j if min {t_{i1}, t_{j2}} <= min {t_{i2},
t_{j1}}, where t_{i1} is the processing time of job i on machine
1, t_{i2} is the processing time of job i on machine 2.
Step 1: Find min i {t_{i1}, t_{i2}}
Step 2a: If t_{k1} <= t_{k2}, place job k in the
first available position for processing.
Step 2b: If t_{k1} > t_{k2}, place job k in the
last available position for processing.
Step 3: remove job k form list of jobs to be scheduled.
Return to step 1.
A heuristic version of this algorithm has been adopted on this web site
for problems with more than two machines.
The algorithm outputs an order of jobs that is to be implemented on all
machines. It follows the exact
steps as above with the exception that the index 2, referring to machine 2, is
replaced by the index n, the index of the last machine.
