QEM – Management ScienceChapter 6/15 Scheduling With Multiple Machines Each job must be processed on several machines Typically np-hard heuristic solution SPT: shortest (total) processing time good for average flow time (optimal for single machine) SOT: shortest operation time good for average flow time (optimal for single machine) SRPT: shortest remaining processing time total processing time on remaining machines often best for average flow time LPT, LOT: longest processing/operation time sometimes good for cycle time Z EDD: (earliest due date) – all due date related objectives Critical ratio: clever variant of EDD rule (remaining time to due date)/(remaining processing time)
{}