On preemption redundancy in scheduling unit processing time jobs on two parallel machines

On preemption redundancy in scheduling unit processing time jobs on two parallel machines

0.00 Avg rating0 Votes
Article ID: iaor20021727
Country: Netherlands
Volume: 28
Issue: 5
Start Page Number: 205
End Page Number: 212
Publication Date: Jun 2001
Journal: Operations Research Letters
Authors: ,
Abstract:

McNaughton's theorem states that preemptions in scheduling arbitrary processing time jobs on identical parallel machines to minimize the total weighted completion time are redundant. Du et al. proved that this remains true even though the jobs have precedence constraints in the form of chains. There are known simple counterexamples showing that other extensions of McNaughton's theorem to other criteria or more general precedence constraints such as intrees or outtrees, or different release dates of job, or different speeds of machines, are not true even for equal weights of jobs. In this paper we show that in the case of two machines and unit processing times, preemptions are still advantageous for intrees or machines with different speeds even for equal weights, or outtrees for different weights, but become redundant for outtrees and equal weights even for different release dates. We also conjecture that the latter statement is actually true for any number of machines.

Reviews

Required fields are marked *. Your email address will not be published.