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

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

Alex J. Ruiz-Torres (Facultad de Administración de Empresas, Universidad de Puerto Rico – Rio Piedras, San Juan, PR, USA), Giuseppe Paletta (Dipartimento di Economia e Statistica, Universita` della Calabria, Cosenza, Italy), and Eduardo Perez-Roman (Ingram School of Engineering, Texas State University, San Marcos, TX, USA)
DOI: 10.4018/IJORIS.2015070101
OnDemand PDF Download:
No Current Special Offers


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.
Article Preview

1. Introduction

This paper addresses the problem of maximizing the percentage of on-time jobs, which is equivalent to the traditional problem of minimizing the number of tardy jobs, when the job’s processing times increase due to machine deterioration in an environment of parallel machines. In this problem, the deterioration of the machine depends on the job sequence. The problem is relevant for two reasons: first, it considers an environment observed in industrial and service settings and second, it focuses on schedules that take customer requirements as a priority. Several examples are described in Cheng et al. (2004) and Hsu et al. (2011).

The key element of the deteriorating jobs problem is that the processing time of the jobs is a function of their start time or the number of jobs since the start of the schedule (or a maintenance activity). In this paper, we propose a different version of the job deterioration problem where the deterioration of the job processing time depends on the specific jobs that have been previously processed by the machine. This perspective is in line with Yang (2011) and Yang et al. (2012), where the jobs are not per se deteriorating, but instead the machines are the ones deteriorating. This paper considers that the deterioration of the machines (and therefore, the job’s processing times) is a function of the sequence of jobs that have been processed by the a machine, an approach first presented in Ruiz-Torres et al. (2013). This view is distinct from the two addressed in the literature as the specific job sequence is relevant in the deterioration level of the machine resource.

An example is used to illustrate the problem. Two teams have to complete a set of ten independent, non divisible/preemtable non sequence dependent jobs available at the start of the schedule. Each job has a baseline duration (if for example, performed first), a deterioration effect, considered the “wear and tear” in the team’s performance level, and a due date for the job. Figure 1 provides the case data and two possible schedules. The schedule for each team presents the jobs’ sequence, and for each job the team’s performance level (above) and total time at the end of that job (below). The research assumes a performance model equal to: performance after a job = performance before job × (1 – deterioration effect of just completed job). For example, schedule 1 for team 1 has three assigned ordered jobs; 6, 1, and 3. A 100% performance level is assumed at the start of the schedule thus after completing job 6, the team is at 96.32% performance (= 100% × (1 – deterioration effect of job 6)), after completing job 1 the team performance would be 92.5% (= 96.32% × (1 – deterioration effect of job 1)), and by the end of job 3 the team would have a 89.2% performance level (= 92.5% × (1 – deterioration effect of job 3)). The effect on the time to complete jobs of the reduction on performance can be easily noted by comparing the sum of the baseline times for these three jobs (233 time units) versus the total time required under this sequence to complete them (242.8 time units) given the deterioration effects.

Figure 1.

Illustrative example of the problem


The two schedules have different values for the objective function under consideration; schedule 1 results in seven tasks completed on-time (70% on-time) while schedule 2 results in eight tasks completed on-time (80% on-time). Similarly, the schedules provide different values for other criteria of relevance to decision makers. For example, both the makespan (the completion time of the last performed task) and the sum of the machine completion times is lower in schedule 1 (which has fewer on time jobs). Thus a tradeoff exists when considering these other criteria versus on-time percentage. While in this research the makespan or the total sum of machine completion times are not considered in the evaluation of schedule performance, these criteria are frequently considered in the deteriorating jobs literature (Kang and Ng, 2007, Ji and Cheng, 2008, Yang et al., 2012), and thus the possibility of tradeoff solutions between these two criteria is relevant for future research.

Complete Article List

Search this Journal:
Volume 14: 1 Issue (2023): Forthcoming, Available for Pre-Order
Volume 13: 2 Issues (2022)
Volume 12: 4 Issues (2021)
Volume 11: 4 Issues (2020)
Volume 10: 4 Issues (2019)
Volume 9: 4 Issues (2018)
Volume 8: 4 Issues (2017)
Volume 7: 4 Issues (2016)
Volume 6: 4 Issues (2015)
Volume 5: 4 Issues (2014)
Volume 4: 4 Issues (2013)
Volume 3: 4 Issues (2012)
Volume 2: 4 Issues (2011)
Volume 1: 4 Issues (2010)
View Complete Journal Contents Listing