Scheduling Jobs on Unreliable Machines Subject to Linear Risk

Background: This paper addresses a new class of scheduling problems in the context of machines subject to (unrecoverable) interruptions; i.e., when a machine fails, the current and subsequently scheduled work on that machine is lost. Each job has a certain processing time and a reward that is attained if the job is successfully completed. Methods: For the failure process, we considered the linear risk model, according to which the probability of machine failure is uniform across a certain time horizon. Results: We analyzed both the situation in which the set of jobs is given, and that in which jobs must be selected from a pool of jobs, at a certain selection cost. Conclusions: We characterized the complexity of various problems, showing both hardness results and polynomial algorithms, and pointed out some open problems.