Modeling the Parallel Machine Scheduling Problem with Step Deteriorating Jobs

Eduardo Lalla-Ruiz, Stefan Voss

    Research output: Contribution to journalArticleAcademicpeer-review

    19 Citations (Scopus)


    This paper addresses the Parallel Machine Scheduling Problem with Step Deteriorating Jobs. This prob- lem 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 com- pletion 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 computa- tional 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.
    Original languageEnglish
    Pages (from-to)21-33
    Number of pages13
    JournalEuropean journal of operational research
    Issue number1
    Publication statusPublished - 16 Nov 2016


    • Machine scheduling
    • Step deterioration
    • Mathematical programming
    • Parallel machine scheduling with step deteriorating jobs


    Dive into the research topics of 'Modeling the Parallel Machine Scheduling Problem with Step Deteriorating Jobs'. Together they form a unique fingerprint.

    Cite this