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 – {\displaystyle max(0,receipt\;date-due\;date)}max(0, receipt\;date – due\;date)
Earliness – {\displaystyle max(0,due\;date-receipt\;date)}max(0, due\;date – receipt\;date)
Lateness – {\displaystyle receipt\;date-due\;date}receipt\;date – due\;date
Flowtime – {\displaystyle end\;date-start\;date}end\;date – start\;date
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
One thought on “Machine Scheduling”