Single-machine scheduling problems with job rejection, deterioration effects and past-sequence-dependent setup times

ABSTRACT

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.

Keywords:

• Scheduling
• deterioration effect
• job rejection
• past-sequence-dependent setup times

Disclosure statement

No potential conflict of interest was reported by the authors.

Data availability statement

The data used to support the findings of this study are available from Mengqi Liu upon reasonable request.

Additional information

Funding

This article was supported by the National Natural Science Foundation of China [grant numbers 71871091, 71471057]; the Natural Science Foundation of Liaoning Province [grant number 2020-MS-233].