Sequencing, task failures, and capacity when failures are driven by a non-homogeneous Poisson process

2025/06/07 by Lingjiong Zhu, Zhu, Lingjiong, Anand Paul +3
Business, Management and Accounting · Computer Science · Engineering · #Advanced Queuing Theory Analysis #FOS: Mathematics #Probability (math.PR) #Real-Time Systems Scheduling #Scheduling and Optimization Algorithms

paper · pdf · doi:10.48550/arxiv.2506.06900

openalex publication_date 2025/06/07 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We study the optimal sequencing of a batch of tasks on a machine subject to random disruptions driven by a non-homogeneous Poisson process (NHPP), such that every disruption requires the interrupted task to be re-processed from scratch, and partially completed work on a disrupted task is wasted. The NHPP models random disruptions whose frequency varies systematically with time. In general the time taken to process a given batch of tasks depends on the order in which the tasks are processed. We find conditions under which the simplest possible sequencing rules - shortest processing time first (SPT) and longest processing time first (LPT) - suffice to minimize the completion time of a batch of tasks.

Citations

• Asymptotic Behavior of Total Times For Jobs That Must Start Over If a Failure Occurs

Related

• On the universal properties of stochastic processes under optimally tuned Poisson restart
• On Resolving Non-Preemptivity in Multitask Scheduling: An Optimal Algorithm in Deterministic and Stochastic Worlds
• Flowshop Machine Scheduling: Markov Modeling, Optimal Schedules and Heuristics
• On the Effect of Task-to-Worker Assignment in Distributed Computing Systems with Stragglers
• Asymptotic efficiency of restart and checkpointing