Modeling the Parallel Machine Scheduling Problem with Step Deteriorating Jobs

Eduardo Lalla-Ruiz and Stefan Voß

European Journal of Operational Research, 2016, vol. 255, issue 1, 21-33

Abstract: 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.

Keywords: Machine scheduling; Step deterioration; Mathematical programming; Parallel machine scheduling with step deteriorating jobs; Set-partitioning formulations (search for similar items in EconPapers)
Date: 2016
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (3)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221716302296
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:ejores:v:255:y:2016:i:1:p:21-33

DOI: 10.1016/j.ejor.2016.04.010

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().