Maximizing the Percentage of On-Time Jobs with Sequence Dependent Deteriorating Process Times




Ruiz-Torres, Alex J.
Paletta, Giuseppe
Perez-Roman, Eduardo

Journal Title

Journal ISSN

Volume Title


IGI Global


The paper addresses the problem of maximizing the percentage of on-time jobs in a parallel machine environment with sequence dependent deterioration. The deterioration of each machine (and therefore of the job processing times) is a function of the sequence of jobs that have been processed by the machine. Two machine loading strategies are combined with a set of list scheduling algorithms to solve the identical and unrelated machine versions of the problem. The proposed solutions approaches are tested using a large set of problem instances that consider various levels of the number of jobs and machines, the due date tightness, and the deterioration effect. The results indicate that the approach based on loading considering all machines simultaneously and assigns jobs by due date is the most effective.



identical machines, job deterioration, list scheduling heuristics, machine deterioration, number of late jobs, on-time jobs, parallel machine scheduling, unrelated machines, Ingram School of Engineering


Ruiz-Torres, A., Paletta, G., & Perez-Roman, E. (2015). Maximizing the percentage of on-time jobs with sequence dependent deteriorating process times. International Journal of Operations Research and Information Systems, 6(3), pp. 1-18.


Rights Holder

Rights License

Rights URI