Modeling the Parallel Machine Scheduling Problem with Step Deteriorating Jobs

• New formulations for parallel machine scheduling with step deteriorating jobs.
• Transformation of the Parallel Machine Scheduling Problem with Step Deteriorating Jobs to the set partitioning problem.
• Considerable improvements in running time and solution quality over earlier approaches.

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.