Mathematics of Operations Research · 1988 · 346 citations · 7 references
ComputingComputer ScienceIndustrial EngineeringAlgorithmsOptimizationSchedulingJob SchedulingJob SequencingSchedule OptimizationScheduling TheoryTardiness MinimizationTask SchedulingScheduling ProblemsSingle-machine SchedulingTardiness Penalty Functions
One‑processor scheduling problems are defined by tasks with specified lengths and preferred start times. The study investigates two cost measures: the sum of absolute deviations from preferred start times and the maximum such deviation. Tasks are scheduled nonpreemptively on a single processor to minimize either the sum or the maximum absolute deviation from their preferred start times. The authors show that minimizing the sum of deviations is NP‑complete, but give polynomial‑time algorithms when all tasks have equal length or a fixed order, and they also provide a general efficient algorithm for minimizing the maximum deviation.
We consider one-processor scheduling problems having the following form: Tasks T 1 , T 2 , …, T N are given, with each T i having a specified length l i and a preferred starting time a i (or, equivalently, a preferred completion time b i ). The tasks are to be scheduled nonpreemptively (i.e., a task cannot be split) on a single processor to begin as close to their preferred starting times as possible. We examine two different cost measures for such schedules, the sum of the absolute discrepancies from the preferred starting times and the maximum such discrepancy. For the first of these, we show that the problem of finding minimum cost schedules is NP-complete; however, we give an efficient algorithm that finds minimum cost schedules whenever the tasks either all have the same length or are required to be executed in a given fixed sequence. For the second cost measure, we give an efficient algorithm that finds minimum cost schedules in general, with no constraints on the ordering or lengths of the tasks.
7
Manuel Blum, Robert W. Floyd, Vaughan Pratt et al. · Journal of Computer and System Sciences · 1973 · 1.2K citations