Parallel machine scheduling with step deteriorating jobs
Set-partitioning formulations
Beschreibung:
This paper addresses the Parallel Machine Scheduling Problem with Step Deteriorating Jobs. This problem arises from real environments in which processing a job later than at a specific time may require an extra processing time. This time-dependent variation is known in the literature as step deterioration and has several practical applications (production planning, computer programming, medicine treatment, equipment maintenance, etc.). In the problem tackled in this work we aim to minimize the total completion time on identical parallel machines where each job has a deteriorating date and observes a step function for the processing time. For solving it, we propose two novel mathematical models based on the Set Partitioning Problem (SPP) that improve the unique model proposed in the literature. The computational performance of these models implemented in a general purpose solver allows to compete with the best algorithms proposed in the literature. Finally, we provide some insights for managing similar SPP formulations when large-sized instances have to be addressed.