Scheduling Deteriorating Jobs on a Single Processor

TLDR

In single‑machine scheduling, jobs deteriorate while waiting, making their processing times non‑exchangeable and the expected makespan dependent on the chosen schedule. The study analyzes deterioration schemes and derives optimal policies that minimize expected makespan and, in some models, its variance. The authors model random setup and detaching times and evaluate scheduling policies under various deterioration schemes. The results are applied to optimal inventory issuing policies, and extensions are explored.

Abstract

N jobs are to be processed sequentially on a single machine. While waiting for processing, jobs deteriorate, causing the random processing requirement of each job to grow at a job-specific rate. Under such conditions, the actual processing times of the jobs are no longer exchangeable random variables and the expected makespan is no longer invariant under any scheduling strategy that disallows idleness. In this paper, we analyze the effects of different deterioration schemes and derive optimal scheduling policies that minimize the expected makespan, and, for some models, policies that minimize the variance of the makespan. We also allow for random setup and detaching times. Applications to optimal inventory issuing policies are discussed and extensions are considered.