Single-machine scheduling

Single-machine scheduling or single-resource scheduling is the process of assigning a group of tasks to a single machine or resource. The tasks are arranged so that one or many performance measures may be optimized.

## Contents

* 1 Performance measures
* 2 Solution techniques
* 2.1 Heuristics
* 2.2 Computational
* 2.3 References

## Performance measures

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

* Tardiness – max(0,receiptdate−duedate)
* Earliness – max(0,duedate−receiptdate)
* Lateness – receiptdate−duedate
* Flowtime – enddate−startdate

## 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.

### Computational

* Genetic algorithms
* Neural networks
* Simulated annealing
* Ant colony optimization
* Tabu search

### References

0.00

(0 votes)

|

Retrieved from "https://handwiki.org/wiki/index.php?title=Finance:Single-machine_scheduling&oldid=347765"