Engineering Optimization · 2021 · 15 citations · 20 references
ManagementComputer ScienceOperations ManagementAlgorithmsOptimizationSchedulingJob SchedulingJob SequencingMachine SchedulingMakespan MinimizationResource-constrained SchedulingScheduling TheoryDeteriorating JobsScheduling With Sequence-dependent Setup TimesSequence SchedulingSequence-dependent Setup TimesSetup TimesSingle Machine Makespan MinimizationSingle-machine SchedulingSum Of Absolute Differences
This article considers single-machine problems in which the actual processing time of a job is a function of its position in a sequence (i.e. position-dependent deterioration effects). In this model, a job is either accepted or rejected. If the job is accepted, it is processed on a single machine, but if the job is rejected, a penalty (cost) is imposed. The goal is to minimize the sum of the given scheduling objectives, including the makespan, the total completion time, the total absolute differences in completion times and the total absolute differences in waiting times of the accepted jobs and total rejection penalty of the rejected jobs. It is illustrated that these problems remain polynomially solvable under the proposed models. Finally, computational results demonstrate that the proposed algorithms can solve instances of various size problems in attractive times. An extension to the problems is offered by assuming time-dependent deterioration effects.
20
A survey on offline scheduling with rejection
Dvir Shabtay, Nufar Gaspar, Moshe Kaspi · Journal of Scheduling · 2012 · 284 citations