Single machine scheduling

Performance measures

The performance measures of the tasks in the single machine scheduling problem include:

Tardiness – m a x ( 0 , r e c e i p t d a t e − d u e d a t e )

Earliness – m a x ( 0 , d u e d a t e − r e c e i p t d a t e )

Lateness – r e c e i p t d a t e − d u e d a t e

Flowtime – e n d d a t e − s t a r t d a t e

Solution techniques

Many solution techniques have been applied to solving single machine scheduling problems. Some of them are listed below.

Heuristics

Shortest processing time (SPT)

The SPT schedule is optimal if the objective is to minimize the average flowtime. SPT-order is an order based on processing time. The sequence of remaining jobs in sorted based on non-decreasing processing time.

Earliest due date (EDD)

The EDD schedule is optimal if the objective is to minimize the maximum tardiness. EDD-order is an order based on due date. The sequence of remaining jobs in sorted based on non-decreasing due date.

Note: "Lateness" is any deviation from the due date. Positive lateness is "tardiness," negative lateness is "earliness"

Hodgson's algorithm

Hodgson's algorithm gives an optimal solution if the objective is to minimize the number of jobs with tardiness greater than zero.

Multi-criteria Single machine scheduling

Malakooti (2013) discusses multi-criteria single machine scheduling. The main concept of the proposed algorithm by Malakooti (2013) is that for each objective function uses the appropriate dispatching rule to find the sequence of jobs and then combines the obtained sequence to get the final sequence.

Computational

Genetic algorithms

Neural networks

Simulated annealing

Ant colonies

Tabu Search

References