Letter to the Editor—A Proof of the Optimality of the Shortest Remaining Processing Time Discipline
From MaRDI portal
Publication:5647712
DOI10.1287/opre.16.3.687zbMath0237.60039OpenAlexW2028301248MaRDI QIDQ5647712
Publication date: 1968
Published in: Operations Research (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1287/opre.16.3.687
Related Items
Optimal control of a single server in a finite-population queueing network ⋮ The impact of processing order on performance: a taxonomy of semi-FIFO policies ⋮ Stochastically minimizing the number of customers in exponential queueing systems ⋮ SEH: size estimate hedging for single-server queues ⋮ SRPT applied to bandwidth-sharing networks ⋮ Optimal choice of threshold in two level processor sharing ⋮ Heavy-tailed limits for medium size jobs and comparison scheduling ⋮ Round robin scheduling of heterogeneous parallel servers in heavy traffic ⋮ GEODIS: towards the optimization of data locality-aware job scheduling in geo-distributed data centers ⋮ Diffusion limits for shortest remaining processing time queues ⋮ Stationary deterministic flows: II. The Single-server queue ⋮ Minimizing the mean slowdown in a single-server queue ⋮ Limits on stationary queue length under various service disciplines ⋮ Handling load with less stress ⋮ Fluid Limits for Multiple-Input Shortest Remaining Processing Time Queues ⋮ A large-deviations analysis of the GI/GI/1 SRPT queue ⋮ Whittle index approach to size-aware scheduling for time-varying channels with multiple states ⋮ Approximability of single machine scheduling with fixed jobs to minimize total completion time ⋮ \(M/G/1/\mathrm{MLPS}\) compared with \(M/G/1/\mathrm{PS}\) within service time distribution class IMRL ⋮ SPT is optimally competitive for uniprocessor flow ⋮ Non-myopic vehicle and route selection in dynamic DARP with travel time and workload objectives ⋮ SCHEDULING IN A SINGLE-SERVER QUEUE WITH STATE-DEPENDENT SERVICE RATES ⋮ Instability of SRPT, SERPT and SJF multiclass queueing networks ⋮ Fluid limits for shortest job first with aging ⋮ Minimality of EDF networks with resource sharing ⋮ Online speed scaling based on active job count to minimize flow plus energy ⋮ Instability of LAS multiclass queueing networks ⋮ Ergodicity bounds for the Markovian queue with time-varying transition intensities, batch arrivals and one queue skipping policy ⋮ Invariance of fluid limits for the shortest remaining processing time and shortest job first policies ⋮ Optimal size-based opportunistic scheduler for wireless systems ⋮ The expected asymptotical ratio for preemptive stochastic online problem ⋮ Edge minimality of EDF resource sharing networks ⋮ Single machine batch scheduling with release times and delivery costs ⋮ Minimizing the mean slowdown in the M/G/1 queue ⋮ Diffusion limits for shortest remaining processing time queues under nonstandard spatial scaling ⋮ Instability of LRTF multiclass queueing networks ⋮ A foreground-background queueing model with speed or capacity modulation ⋮ PERFORMANCE OF NON-COOPERATIVE ROUTING OVER PARALLEL NON-OBSERVABLE QUEUES ⋮ Open Problem—M/G/k/SRPT Under Medium Load ⋮ Open Problem—M/G/1 Scheduling with Preemption Delays ⋮ Unnamed Item ⋮ Single-machine scheduling with no idle time and release dates to~minimize a regular criterion ⋮ Heavy-Traffic Analysis of Sojourn Time Under the Foreground–Background Scheduling Policy ⋮ Size- and state-aware dispatching problem with queue-specific job sizes ⋮ On reducing time spent in M/G/1 systems ⋮ Recent sojourn time results for multilevel processor‐sharing scheduling disciplines ⋮ Unary NP-hardness of preemptive scheduling to minimize total completion time with release times and deadlines ⋮ Scheduling problems in master-slave model ⋮ Branch-and-bound method for minimizing the weighted completion time scheduling problem on a single machine with release dates ⋮ Discrete-time \(MAP/G/1/\infty\) system with inversive probabilistic servicing discipline ⋮ On the average sojourn time under \(M/M/1/\)SRPT ⋮ On-line scheduling to minimize average completion time revisited. ⋮ A review of exact solution methods for the non-preemptive multiprocessor flowshop problem ⋮ The asymptotic performance ratio of an on-line algorithm for uniform parallel machine scheduling with release dates ⋮ A flexible flowshop problem with total flow time minimization ⋮ On the Gittins index in the M/G/1 queue ⋮ Multi-queue scheduling of two tasks ⋮ Minimizing flow time on a constant number of machines with preemption ⋮ Asymptotic analysis of an on-line algorithm for the single machine completion time problem with release dates ⋮ Central processor scheduling using I/O behaviour models ⋮ Minimizing makespan in a two-machine flowshop with dynamic arrivals allowed ⋮ Multi-layered round robin routing for parallel servers ⋮ Asymptotic analysis of online algorithms and improved scheme for the flow shop scheduling problem with release dates ⋮ Multiple feedback at a single-server station ⋮ Single-machine hierarchical scheduling with release dates and preemption to minimize the total completion time and a regular criterion ⋮ Singleton Acyclic Mechanisms and Their Applications to Scheduling Problems ⋮ Sojourn times in (discrete) time shared systems and their continuous time limits ⋮ Last in line ⋮ A note on single-machine scheduling to tradeoff between the number of tardy jobs and the start time of machine ⋮ Open problems in queueing theory inspired by datacenter computing ⋮ Achievable Performance of Blind Policies in Heavy Traffic ⋮ On the Control of Fork-Join Networks ⋮ A class of on-line scheduling algorithms to minimize total completion time ⋮ From Preemptive to Non-preemptive Scheduling Using Rejections ⋮ Heavy traffic scaling limits for shortest remaining processing time queues with heavy tailed processing time distributions ⋮ A Tight 2-Approximation for Preemptive Stochastic Scheduling ⋮ BMAP/G/1/\(\infty \) system with last come first served probabilistic priority ⋮ On the Gittins index for multistage jobs ⋮ Local edge minimality of SRPT networks with shared resources ⋮ Approximately optimal scheduling of an \(\mathrm{M}/\mathrm{G}/1\) queue with heavy tails ⋮ Online scheduling FIFO policies with admission and push-out ⋮ Heavy traffic analysis for single-server SRPT and LRPT queues via EDF diffusion limits ⋮ On n/1/?? dynamic deterministic problems
This page was built for publication: Letter to the Editor—A Proof of the Optimality of the Shortest Remaining Processing Time Discipline
