Sequencing jobs on a non-Markovian machine with random disruptions

Abstract

This article considers the problem of sequencing a fixed number of jobs on a single machine subject to random disruptions. If the machine is interrupted in the course of performing a job, it has to restart the job from the beginning. It is assumed that the disruptions arrive according to a renewal process with inter-arrival times that are finite or continuous mixtures of independent exponential distributions, a class of distributions that contains Decreasing Failure Rate (DFR) Weibull, Pareto, and DFR gamma. The machine is non-Markovian in the sense that the expected completion time of a job on a machine depends partly on the history of the machine. It is shown that the shortest processing time first rule minimizes in expectation the total processing time of a batch of jobs, as well as the total waiting time of all of the jobs in the batch. These appear to be the first results in the literature for optimally sequencing an arbitrary number of jobs on a machine with a non-memoryless uptime distribution.

Keywords:

• Stochastic sequencing
• decreasing failure rate service systems