SELECTING JOBS FOR SCHEDULING ON A MACHINE SUBJECT TO FAILURE

Abstract

A fixed number n of jobs has to be selected from a set of possible jobs; then the chosen jobs have to be ordered for processing on a single machine which is subject to breakdown. The probability that the machine fails while working on some job J depends on J. To each job there corresponds a reward and a discount factor diminishing the virtual value of future jobs. The objective is to maximize the expected sum of all rewards earned until breakdown. Two algorithms for choosing the n jobs optimally and a method for ordering them are derived.