Scheduling Problem
 Instructions
 Definitions
 Machine Environments
 Algorithms
 Objectives
 Try It! 

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 non-preemption.  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.