Journal of the Operational Research Society · 1994 · 84 citations · 4 references
ManagementComputer ScienceOperations ManagementAlgorithmsParallel ComputingSchedulingDue-date SchedulingJob SchedulingJob Shop SchedulingMachine SchedulingScheduling TheoryTardiness MinimizationParallel Machine SchedulingParallel-machine Tardiness SchedulingPenaltiesTardiness Penalty FunctionsWeighted Tardiness Minimization
We consider the problem of assigning a common due-date and sequencing a set of simultaneously available jobs on several identical parallel-machines. The objective is to minimize some penalty function of earliness, tardiness and due-date values. We show that the problem is NP-hard with either a total or a maximal penalty function. For the problem with a total penalty function, we show that the special case in which all jobs have an equal processing time is polynomially-solvable.
4