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.

Performance measures

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

  • Tardiness
  • Earliness –
  • Lateness –
  • Flowtime

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

References

    gollark: no.
    gollark: Maybe your networking setup has been infected with coronavirus.
    gollark: They're already trying to snoop on everyone's private communications with the rather evil "EARN IT" (we need to stop these acronyms) thing.
    gollark: We don't control earthquakes (much), but the world is increasingly connected and biotechnology is improving, so pandemics might get worse... climate change remains a problematic longer-term thing...
    gollark: I want 2019 back. All these disastrous things are ~~quite bad for the economy~~ worrying, and I wonder if this is going to become a general trend.
    This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.