Letter to the Editor—A Proof of the Optimality of the Shortest Remaining Processing Time Discipline
1968; Institute for Operations Research and the Management Sciences; Volume: 16; Issue: 3 Linguagem: Inglês
10.1287/opre.16.3.687
ISSN1526-5463
Autores Tópico(s)Scheduling and Optimization Algorithms
ResumoFree AccessAboutSectionsView PDF ToolsAdd to favoritesDownload CitationsTrack CitationsPermissionsReprints ShareShare onFacebookTwitterLinked InEmail Go to SectionFree Access HomeOperations ResearchVol. 16, No. 3 Letter to the Editor—A Proof of the Optimality of the Shortest Remaining Processing Time DisciplineLinus SchrageLinus SchragePublished Online:1 Jun 1968https://doi.org/10.1287/opre.16.3.687 Previous Back to Top Next FiguresReferencesRelatedInformationCited byOn the Gittins index for multistage jobs7 April 2022 | Queueing Systems, Vol. 102, No. 3-4Local edge minimality of SRPT networks with shared resources7 October 2022 | Mathematical Methods of Operations Research, Vol. 170Size-based scheduling vs fairness for datacenter flowsACM SIGMETRICS Performance Evaluation Review, Vol. 50, No. 2Speed Scaling on Parallel Servers With MapReduce Type Precedence ConstraintsIEEE/ACM Transactions on Networking, Vol. 30, No. 4Heavy traffic scaling limits for shortest remaining processing time queues with heavy tailed processing time distributionsThe Annals of Applied Probability, Vol. 32, No. 4Mitigating long queues and waiting times with service resetting1 July 2022 | PNAS Nexus, Vol. 1, No. 3Fluid limits for shortest job first with aging4 April 2022 | Queueing Systems, Vol. 101, No. 1-2Instability of SRPT, SERPT and SJF multiclass queueing networks17 January 2022 | Queueing Systems, Vol. 101, No. 1-2Size-Based Congestion Control Using Network Utility MaximizationIEEE Transactions on Control of Network Systems, Vol. 9, No. 2Personalized scheduling in service systems16 March 2022 | Queueing Systems, Vol. 100, No. 3-4Minimizing the mean slowdown in a single-server queue28 March 2022 | Queueing Systems, Vol. 100, No. 3-4Heavy traffic analysis for single-server SRPT and LRPT queues via EDF diffusion limits19 January 2021 | Annals of Operations Research, Vol. 310, No. 2Minimizing the sum of makespan on multi-agent single-machine scheduling with release datesSwarm and Evolutionary Computation, Vol. 69Optimal Strategy for Pick-and-Place System with two RobotsJournal of Physics: Conference Series, Vol. 2216, No. 1Integrated Production and Outbound Distribution Scheduling: Online Problems20 October 2021Combining Simulation and Machine Learning for Response Time Prediction for the Shortest Remaining Processing Time DisciplineDecentralized elastic electricity demand schedulingSRPT Scheduling Discipline in Many-Server Queues with Impatient CustomersJing Dong, Rouba Ibrahim21 October 2021 | Management Science, Vol. 67, No. 12Unary NP-hardness of preemptive scheduling to minimize total completion time with release times and deadlinesDiscrete Applied Mathematics, Vol. 304GDSim: Benchmarking Geo-Distributed Data Center SchedulersDecentralized scheduling with precedence constraints28 May 2021 | Optimization Letters, Vol. 15, No. 8Scheduling and Control of Queueing Networks1 October 2021 | , Vol. 2Loss Queueing Systems with Limited Processor Sharing and Applications to Communication NetworksThe Gittins Policy in the M/G/1 QueueEfficient Online Scheduling of Electric Vehicle Charging Using a Service-Price MenuSingle-machine hierarchical scheduling with release dates and preemption to minimize the total completion time and a regular criterionEuropean Journal of Operational Research, Vol. 293, No. 1A Deep Reinforcement Learning-based Application Framework for Conveyor Belt-based Pick-and-Place Systems using 6-axis Manipulators under Uncertainty and Real-time ConstraintsNudge: Stochastically Improving upon FCFSProceedings of the ACM on Measurement and Analysis of Computing Systems, Vol. 5, No. 2Ergodicity bounds for the Markovian queue with time-varying transition intensities, batch arrivals and one queue skipping policyApplied Mathematics and Computation, Vol. 395Frequency scaling in multilevel queuesACM SIGMETRICS Performance Evaluation Review, Vol. 48, No. 3Joint coflow routing and scheduling in leaf-spine data centersJournal of Parallel and Distributed Computing, Vol. 148Open problems in queueing theory inspired by datacenter computing27 January 2021 | Queueing Systems, Vol. 63SmartDis: Near-Optimal Task Scheduling in Multi-edge Networks9 April 2021SEH: Size Estimate Hedging for Single-Server Queues19 August 2021Instability of LAS multiclass queueing networksOperations Research Letters, Vol. 49, No. 1Optimal multiserver scheduling with unknown job sizes in heavy trafficPerformance Evaluation, Vol. 145Frequency scaling in multilevel queuesPerformance Evaluation, Vol. 143SCHEDULING IN A SINGLE-SERVER QUEUE WITH STATE-DEPENDENT SERVICE RATES21 May 2019 | Probability in the Engineering and Informational Sciences, Vol. 34, No. 4Size-based scheduling for TCP flows: Implementation and performance evaluationComputer NetworksAnti-Aging Scheduling in Single-Server Queues: A Systematic and Comparative StudySimple Near-Optimal Scheduling for the M/G/1Proceedings of the ACM on Measurement and Analysis of Computing Systems, Vol. 4, No. 1Comment on "Datacenter Congestion Control: Identifying what is essential and making it practical" by Aisha Mushtaq, et al, CCR, July 2019ACM SIGCOMM Computer Communication Review, Vol. 50, No. 2Toward Fast and Optimal Robotic Pick-and-Place on a Moving ConveyorIEEE Robotics and Automation Letters, Vol. 5, No. 2Heavy-Traffic Analysis of Sojourn Time Under the Foreground–Background Scheduling PolicyBart Kamphorst, Bert Zwart17 February 2020 | Stochastic Systems, Vol. 10, No. 1To schedule or not to schedule: when no-scheduling can beat the best-known flow scheduling algorithm in datacenter networksComputer NetworksA Queueing Model that Works Only on the Biggest Jobs3 April 2020Simple Near-Optimal Scheduling for the M/G/1ACM SIGMETRICS Performance Evaluation Review, Vol. 47, No. 2Low-Complexity Flow Scheduling for Commodity Switches in Data Center NetworksOnDisc: Online Latency-Sensitive Job Dispatching and Scheduling in Heterogeneous Edge-CloudsIEEE/ACM Transactions on Networking, Vol. 27, No. 6A note on single-machine scheduling to tradeoff between the number of tardy jobs and the start time of machineOperations Research Letters, Vol. 47, No. 6Theoretical and Experimental Evaluation of the Two-Level Processor Sharing Discipline for TCP FlowsOpen Problem—M/G/k/SRPT Under Medium LoadIsaac Grosof18 September 2019 | Stochastic Systems, Vol. 9, No. 3Open Problem—M/G/1 Scheduling with Preemption DelaysZiv Scully17 September 2019 | Stochastic Systems, Vol. 9, No. 3Hybrid Deep Neural Network Scheduler for Job-Shop Problem Based on Convolution Two-Dimensional TransformationComputational Intelligence and Neuroscience, Vol. 2019On the Control of Fork-Join NetworksErhun Özkan, Amy R. Ward31 January 2019 | Mathematics of Operations Research, Vol. 44, No. 2Last in lineOperations Research Letters, Vol. 47, No. 2SRPT for Multiserver SystemsACM SIGMETRICS Performance Evaluation Review, Vol. 46, No. 3SRPT for Multiserver SystemsACM SIGMETRICS Performance Evaluation Review, Vol. 46, No. 2SRPT for multiserver systemsPerformance Evaluation, Vol. 127-128Achievable Performance of Blind Policies in Heavy TrafficNikhil Bansal, Bart Kamphorst, Bert Zwart8 March 2018 | Mathematics of Operations Research, Vol. 43, No. 3An Improved Bound for Minimizing the Total Weighted Completion Time of Coflows in DatacentersIEEE/ACM Transactions on Networking, Vol. 26, No. 4Age-optimal updates of multiple information flowsPerformance-Aware Fair Scheduling: Exploiting Demand Elasticity of Data Analytics JobsTask Replication for Deadline-Constrained Vehicular Cloud Computing: Optimal Policy, Performance Analysis, and Implications on Road TrafficIEEE Internet of Things Journal, Vol. 5, No. 1Delay-Efficient Multiclass Packet Scheduler24 April 2018Control and Optimization of the SRPT Service Policy by Frequency Scaling15 August 2018On Saturation Effects in Coupled Speed Scaling15 August 2018GEODIS: towards the optimization of data locality-aware job scheduling in geo-distributed data centers20 July 2017 | Computing, Vol. 100, No. 1Datacenter Traffic Control: Understanding Techniques and TradeoffsIEEE Communications Surveys & Tutorials, Vol. 20, No. 2KairosWorkload adaptive flow schedulingEfficient Data Center Flow Scheduling Without Starvation Using Expansion RatioIEEE Transactions on Parallel and Distributed Systems, Vol. 28, No. 11Edge minimality of EDF resource sharing networks24 June 2017 | Mathematical Methods of Operations Research, Vol. 86, No. 2Energy-aware SRPT server with batch arrivals: Analysis and optimizationPerformance Evaluation, Vol. 115Congestion Control for Background Data Transfers With Minimal Delay ImpactIEEE/ACM Transactions on Networking, Vol. 25, No. 5The impact of processing order on performance: A taxonomy of semi-FIFO policiesJournal of Computer and System Sciences, Vol. 88Scheduling Jobs with Estimation Errors for Multi-server SystemsCompetitive analysis for online scheduling in software-defined optical WANOnline job dispatching and scheduling in edge-cloudsJoint offloading and resource allocation for computation and communication in mobile cloud with computing access pointA feedback control approach to dynamic speed scaling in computing systemsOptimal control of a single server in a finite-population queueing network16 November 2016 | Queueing Systems, Vol. 85, No. 1-2Models and Concepts of Classical Scheduling19 October 2016A New Approach to Online SchedulingACM Transactions on Algorithms, Vol. 13, No. 1Smart Grid-aware scheduling in data centresComputer Communications, Vol. 96DRASH: A Data Replication-Aware Scheduler in Geo-Distributed Data CentersOptimizing resource management during business process execution: A case studyA delay efficient multiclass packet scheduler for heterogeneous M2M uplinkMinimality of EDF networks with resource sharing22 April 2016 | Mathematical Methods of Operations Research, Vol. 84, No. 2Large profits or fast gains: A dilemma in maximizing throughput with applications to network processorsJournal of Network and Computer Applications, Vol. 74Meeting Soft Deadlines in Single- and Multi-server SystemsAutoscaling Effects in Speed Scaling SystemsExperimental Calibration and Validation of a Speed Scaling SimulatorFluid Limits for Multiple-Input Shortest Remaining Processing Time QueuesŁukasz Kruk, Ewa Sokołowska21 April 2016 | Mathematics of Operations Research, Vol. 41, No. 3Whittle index approach to size-aware scheduling for time-varying channels with multiple states14 June 2016 | Queueing Systems, Vol. 83, No. 3-4Joint Optimization of Flow Latency in Routing and Scheduling for Software Defined NetworksPERFORMANCE OF NON-COOPERATIVE ROUTING OVER PARALLEL NON-OBSERVABLE QUEUES19 May 2016 | Probability in the Engineering and Informational Sciences, Vol. 30, No. 3A Set of Successive Job Allocation Models in Distributed Computing Infrastructures17 October 2015 | Journal of Grid Computing, Vol. 14, No. 2Online Scheduling FIFO Policies with Admission and Push-Out12 April 2015 | Theory of Computing Systems, Vol. 58, No. 2A Picking Strategy for Circular Conveyor Tracking12 June 2015 | Journal of Intelligent & Robotic Systems, Vol. 81, No. 2Flow Time Minimization22 April 2016From Preemptive to Non-preemptive Scheduling Using Rejections20 July 2016Energy-Aware Server with SRPT Scheduling: Analysis and Optimization3 August 2016Diffusion limits for shortest remaining processing time queues under nonstandard spatial scalingThe Annals of Applied Probability, Vol. 25, No. 6An Inequality for the Variance of Waiting Time under a General Queueing Discipline24 November 2015HopperACM SIGCOMM Computer Communication Review, Vol. 45, No. 4Asymptotic analysis of online algorithms and improved scheme for the flow shop scheduling problem with release dates7 October 2013 | International Journal of Systems Science, Vol. 46, No. 11User satisfaction fairness based optimal charging algorithm for multiple devicesApproximately optimal scheduling of an M/G/1 queue with heavy tails3 February 2015 | Queueing Systems, Vol. 80, No. 3Whittle Index Approach to Size-aware Scheduling with Time-varying ChannelsACM SIGMETRICS Performance Evaluation Review, Vol. 43, No. 1Non-intrusive scheduling of TCP flowsDRX-Aware Power and Delay Optimized Scheduler for Bursty Traffic TransmissionProvably delay efficient data retrieving in storage cloudsRevisiting symbiotic job schedulingSchemes for Fast Transmission of Flows in Data Center NetworksIEEE Communications Surveys & Tutorials, Vol. 17, No. 3Whittle Index Approach to Size-aware Scheduling with Time-varying ChannelsHopperScheduling jobs across geo-distributed datacentersMapReduce Job Scheduling Based on Remaining Job SizesIEICE Transactions on Communications, Vol. E98.B, No. 1Asymptotic optimality of shortest processing time-based algorithms for flow shop and open shop problems with nonlinear objective functions3 January 2014 | Engineering Optimization, Vol. 46, No. 12Don't be fat: Towards efficient online flow scheduling in data center networksA Tight 2-Approximation for Preemptive Stochastic SchedulingNicole Megow, Tjark Vredeveld30 May 2014 | Mathematics of Operations Research, Vol. 39, No. 4Turbocharged Speed Scaling: Analysis and EvaluationImproving the quality of experience with size-based and opportunistic schedulingQueueing-theoretic approaches for dynamic scheduling: A surveySurveys in Operations Research and Management Science, Vol. 19, No. 2Decoupled speed scaling: Analysis and evaluationPerformance Evaluation, Vol. 73How to transfer flows efficiently via the Internet?Balancing work and size with bounded buffersImplementation of shortest remaining processing time based schedulers on a 32 bit serial based processing platformShortest remaining processing time based schedulers for reduction of traffic congestionJoint optimization of overlapping phases in MapReducePerformance Evaluation, Vol. 70, No. 10Dynamic HTTP download scheduling with respect to energy consumptionA combinatorial auctions perspective on min-sum scheduling problemsThe expected asymptotical ratio for preemptive stochastic online problemTheoretical Computer Science, Vol. 495Online Speed Scaling Based on Active Job Count to Minimize Flow Plus Energy27 January 2012 | Algorithmica, Vol. 65, No. 3Single machine batch scheduling with release times and delivery costs18 October 2011 | Journal of Scheduling, Vol. 16, No. 1Online and Semi-online Scheduling26 July 2013The Two-Machine Flow Shop22 August 2012Priorities and Scheduling in M/G/128 March 2013Scheduling for weighted flow time and energy with rejection penaltyTheoretical Computer Science, Vol. 470Non-myopic vehicle and route selection in dynamic DARP with travel time and workload objectivesComputers & Operations Research, Vol. 39, No. 12A taxonomy of Semi-FIFO policiesIs Tail-Optimal Scheduling Possible?Adam Wierman, Bert Zwart, 9 October 2012 | Operations Research, Vol. 60, No. 5Optimal size-based opportunistic scheduler for wireless systems14 March 2012 | Queueing Systems, Vol. 72, No. 1-2A spike-detecting AQM to deal with elephantsComputer Networks, Vol. 56, No. 13Decoupled Speed Scaling: Analysis and EvaluationProbabilistic alternatives for competitive analysis13 April 2011 | Computer Science - Research and Development, Vol. 27, No. 3Minimizing slowdown in heterogeneous size-aware dispatching systemsACM SIGMETRICS Performance Evaluation Review, Vol. 40, No. 1Flow-level modeling and analysis of dynamic TDD in LTEASIdE: Using Autocorrelation-Based Size Estimation for Scheduling Bursty WorkloadsIEEE Transactions on Network and Service Management, Vol. 9, No. 2Distributed and Online Fair Resource Management in Video Surveillance Sensor NetworksIEEE Transactions on Mobile Computing, Vol. 11, No. 5Single-machine scheduling with no idle time and release dates to minimize a regular criterion15 July 2010 | Journal of Scheduling, Vol. 15, No. 2Branch-and-bound method for minimizing the weighted completion time scheduling problem on a single machine with release datesComputers & Operations Research, Vol. 39, No. 3Size- and state-aware dispatching problem with queue-specific job sizesEuropean Journal of Operational Research, Vol. 217, No. 2Invariance of fluid limits for the shortest remaining processing time and shortest job first policies9 November 2011 | Queueing Systems, Vol. 70, No. 2Many Flows Asymptotics for SMART Scheduling PoliciesIEEE Transactions on Automatic Control, Vol. 57, No. 2FIFO Queueing Policies for Packets with Heterogeneous ProcessingM/M/1-PS queue and size-aware task assignmentPerformance Evaluation, Vol. 68, No. 11Using spikes to deal with elephantsHeavy-traffic analysis of mean response time under Shortest Remaining Processing TimePerformance Evaluation, Vol. 68, No. 10Resource-sharing in a single server with time-varying capacityMinimizing flow time in the wireless gathering problemACM Transactions on Algorithms, Vol. 7, No. 3Diffusion Limits for Shortest Remaining Processing Time QueuesH. Christian Gromoll, Łukasz Kruk, Amber L. Puha6 February 2011 | Stochastic Systems, Vol. 1, No. 1Providing performance guarantees in multipass network processorsLower bounds for single machine subproblems occurring in weighted tardiness oriented shifting bottleneck proceduresQueueing Disciplines15 February 2011Single Machine Scheduling15 February 2011The M / G /1 Queue15 February 2011Size-Based Flow-Scheduling Using Spike-DetectionFairness and scheduling in single server queuesSurveys in Operations Research and Management Science, Vol. 16, No. 1On the Analysis of Supplier-Manufacturer Information Sharing Strategies for Production SchedulingDiscrete-time MAP/G/1/∞ system with inversive probabilistic servicing discipline12 January 2011 | Automation and Remote Control, Vol. 71, No. 12Tail-robust scheduling via limited processor sharingPerformance Evaluation, Vol. 67, No. 11The average response time in a heavy-traffic srpt queueACM SIGMETRICS Performance Evaluation Review, Vol. 38, No. 2Simulation of the Foreground-Background Queue in Parallel SystemsScheduling for the tail: Robustness versus optimalityBalancing SRPT prioritization vs opportunistic gain in wireless systems with flow dynamicsEfficient Web Requests Scheduling Considering Resources SharingA new scheduling algorithm for server farms load balancingQTL: An efficient scheduling policy for 10Gbps network intrusion detection systemA Flow Scheduler ArchitectureEfficient Algorithms for Average Completion Time SchedulingOnline Cooperative Cost SharingATLAS: A scalable and high-performance scheduling algorithm for multiple memory controllersOn the Gittins index in the M/G/1 queue24 September 2009 | Queueing Systems, Vol. 63, No. 1-4An RL-based scheduling algorithm for video traffic in high-rate wireless personal area networksComputer Networks, Vol. 53, No. 18Fluid Limits for Shortest Remaining Processing Time QueuesDouglas G. Down, H. Christian Gromoll, Amber L. Puha, 20 October 2009 | Mathematics of Operations Research, Vol. 34, No. 4State-dependent response times via fluid limits in shortest remaining processing time queuesACM SIGMETRICS Performance Evaluation Review, Vol. 37, No. 2Multi-objective scheduling for real-time data warehouses2 April 2009 | Computer Science - Research and Development, Vol. 24, No. 3SRPT applied to bandwidth-sharing networks13 September 2008 | Annals of Operations Research, Vol. 170, No. 1Optimal choice of threshold in Two Level Processor Sharing13 September 2008 | Annals of Operations Research, Vol. 170, No. 1Heavy-tailed limits for medium size jobs and comparison scheduling13 September 2008 | Annals of Operations Research, Vol. 170, No. 1Round robin scheduling of heterogeneous parallel servers in heavy trafficEuropean Journal of Operational Research, Vol. 195, No. 2Performance Evaluation of Interactive Data Services Under Sharing and Preemptive Scheduling DisciplinesFifty years of scheduling: a survey of milestones21 December 2017 | Journal of the Operational Research Society, Vol. 60, No. sup1BMAP/G/1/∞ system with last come first served probabilistic priority16 May 2009 | Automation and Remote Control, Vol. 70, No. 5Power-Aware Speed Scaling in Processor Sharing SystemsOn the Impact of Heterogeneity and Back-End Scheduling in Load Balancing DesignsEfficient fair algorithms for message communicationSimulation Modelling Practice and Theory, Vol. 17, No. 3Shortest Remaining Response Time Scheduling for Improved Web Server PerformanceAssessing the efficiency of resource allocations in bandwidth-sharing networksPerformance Evaluation, Vol. 66, No. 1Sojourn times in (discrete) time shared systems and their continuous time limits25 October 2008 | Queueing Systems, Vol. 60, No. 3-4Improving peer-to-peer performance through server-side schedulingACM Transactions on Computer Systems, Vol. 26, No. 4On the twin measure and queueing systems predictabilityPerformance Evaluation, Vol. 65, No. 11-12SRPT optimally utilizes faster machines to minimize flow timeACM Transactions on Algorithms, Vol. 5, No. 1The effect of local scheduling in load balancing designsACM SIGMETRICS Performance Evaluation Review, Vol. 36, No. 2Recent sojourn time results for multilevel processor-sharing scheduling disciplines22 July 2008 | Statistica Neerlandica, Vol. 62, No. 3Scheduling despite inexact job-size informationACM SIGMETRICS Performance Evaluation Review, Vol. 36, No. 1Scheduling problems in master-slave model1 December 2007 | Annals of Operations Research, Vol. 159, No. 1ASYMPTOTIC PROPERTIES OF SOJOURN TIMES IN MULTICLASS TIME-SHARED SYSTEMS19 March 2008 | Probability in the Engineering and Informational Sciences, Vol. 22, No. 2Fine-Tuning MAC-Level Protocols for Optimized Real-Time QoSIEEE Transactions on Industrial Informatics, Vol. 4, No. 1Flow Time MinimizationSingleton Acyclic Mechanisms and Their Applications to Scheduling ProblemsMinimizing Average Flow Time in Sensor Data GatheringScheduling for performance and availability in systems with temporal dependent workloadsOn the relative value of local scheduling versus routing in parallel server systemsEfficient resource allocation in bandwidth-sharing networksACM SIGMETRICS Performance Evaluation Review, Vol. 35, No. 3Minimizing weighted flow timeACM Transactions on Algorithms, Vol. 3, No. 4Scheduling in polling systemsPerformance Evaluation, Vol. 64, No. 9-12Fair Efficiency, or Low Average Delay without StarvationPBSACM SIGMETRICS Performance Evaluation Review, Vol. 35, No. 1Adaptive and scalable comparison schedulingACM SIGMETRICS Performance Evaluation Review, Vol. 35, No. 1A Network Architecture for Large-Scale ScienceApproximability of single machine scheduling with fixed jobs to minimize total completion timeEuropean Journal of Operational Research, Vol. 178, No. 1Fairness and classificationsACM SIGMETRICS Performance Evaluation Review, Vol. 34, No. 4Impact of Size-Based Scheduling on Flow Level Performance in Wireless Downlink Data ChannelsStability of Networks with Age-Based SchedulingOn the effect of inexact size information in size based policiesACM SIGMETRICS Performance Evaluation Review, Vol. 34, No. 3M/G/1/MLPS compared with M/G/1/PS within service time distribution class IMRL15 August 2006 | Mathematical Methods of Operations Research, Vol. 64, No. 2A large-deviations analysis of the GI/GI/1 SRPT queueQueueing Systems, Vol. 54, No. 2A Branch and bound for 1|ri| wiCi, Scheduling ProblemOptimal Scheduling of Heavy Tailed Traffic via Shape Parameter EstimationHandling load with less stressQueueing Systems, Vol. 54, No. 1Revisiting unfairness in Web server schedulingComputer Networks, Vol. 50, No. 13Multi-layered round robin routing for parallel serversQueueing Systems, Vol. 53, No. 4Minimizing sum of completion times and makespan in master-slave systemsIEEE Transactions on Computers, Vol. 55, No. 8Tail asymptotics for policies favoring short jobs in a many-flows regimeACM SIGMETRICS Performance Evaluation Review, Vol. 34, No. 1The asymptotic performance ratio of an on-line algorithm for uniform parallel machine scheduling with release dates7 June 2005 | Mathematical Programming, Vol. 106, No. 1Average-Case and Smoothed Competitive Analysis of the Multilevel Feedback AlgorithmLuca Becchetti, Stefano Leonardi, Alberto Marchetti-Spaccamela, Guido Schäfer, Tjark Vredeveld, 1 February 2006 | Mathematics of Operations Research, Vol. 31, No. 1TCP as an Implementation of Age-Based Scheduling: Fairness and PerformanceComparing Different Approaches to the use of DiffServ in the InternetDesign choices for content distribution in P2P networksACM SIGCOMM Computer Communication Review, Vol. 35, No. 3Systems with multiple servers under heavy-tailed workloadsPerformance Evaluation, Vol. 62, No. 1-4A review of exact solution methods for the non-preemptive multiprocessor flowshop problemEuropean Journal of Operational Research, Vol. 164, No. 3Nearly insensitive bounds on SMART schedulingACM SIGMETRICS Performance Evaluation Review, Vol. 33, No. 1Classifying scheduling policies with respect to higher moments of conditional response timeACM SIGMETRICS Performance Evaluation Review, Vol. 33, No. 1Minimizing flow time on a constant number of machines with preemptionOperations Research Letters, Vol. 33, No. 3On the average sojourn time under M/M/1/SRPTOperations Research Letters, Vol. 33, No. 2Priority Auctions and Queue Disciplines That Depend on Processing TimeThomas Kittsteiner, Benny Moldovanu, 1 February 2005 | Management Science, Vol. 51, No. 2Cooperative Content Distribution: Scalability Through Self-OrganizationAnalysis and control of correlated web server queuesComputer Communications, Vol. 27, No. 18On-line scheduling to minimize average completion time revisitedOperations Research Letters, Vol. 32, No. 5Formalizing SMART schedulingACM SIGMETRICS Performance Evaluation Review, Vol. 32, No. 2Optimizing Pilot Planning and Training for Continental AirlinesGang Yu, Julian Pachon, Benjamin Thengvall, Darryal Chandler, Al Wilson, 1 August 2004 | Interfaces, Vol. 34, No. 4Adaptive memory allocations in clusters to handle unexpectedly large data-intensive jobsIEEE Transactions on Parallel and Distributed Systems, Vol. 15, No. 7SPT is optimally competitive for uniprocessor flowInformation Processing Letters, Vol. 90, No. 5Two-level processor-sharing scheduling disciplinesACM SIGMETRICS Performance Evaluation Review, Vol. 32, No. 1Asymptotic Performance Ratio of an Online Algorithm for the Single Machine Scheduling With Release DatesIEEE Transactions on Automatic Control, Vol. 49, No. 5Enhancing Both Network and User Performance for Networks Supporting Best Effort TrafficIEEE/ACM Transactions on Networking, Vol. 12, No. 2Class Scheduling for Pilot TrainingXiangtong Qi, Jonathan F. Bard, Gang Yu, 1 February 2004 | Operations Research, Vol. 52, No. 1Scheduling to Minimize Average Completion Time Revisited: Deterministic On-Line AlgorithmsLogistics scheduling: Analysis of two-stage problemsJournal of Systems Science and Systems Engineering, Vol. 12, No. 4On the average sojourn time under M/M/1/SRPTACM SIGMETRICS Performance Evaluation Review, Vol. 31, No. 2Revisiting correlations and scheduling in Web serversACM SIGMETRICS Performance Evaluation Review, Vol. 31, No. 2Evolutionary programming for minimizing the average flow time in the presence of non-zero ready timesComputers & Industrial Engineering, Vol. 45, No. 2Analysis of LAS scheduling for job size distributions with high varianceACM SIGMETRICS Performance Evaluation Review, Vol. 31, No. 1Fairness and efficiency in web server protocolsACM SIGMETRICS Performance Evaluation Review, Vol. 31, No. 1Classifying scheduling policies with respect to unfairness in an M/GI/1ACM SIGMETRICS Performance Evaluation Review, Vol. 31, No. 1A class of on-line scheduling algorithms to minimize total completion timeOperations Research Letters, Vol. 31, No. 3Finite State and Action MDPSOptimization-Based Integrated Manpower Management for AirlinesWeb servers under overload: How scheduling can helpScheduling to Minimize Average Completion Time Revisited: Deterministic On-line AlgorithmsSSRN Electronic JournalAsymptotic convergence of scheduling policies with respect to slowdownPerformance Evaluation, Vol. 49, No. 1-4Minimizing makespan in a two-machine flowshop with dynamic arrivals allowedComputers & Operations Research, Vol. 29, No. 3Analysis of M/G/1/SRPT under transient overloadACM SIGMETRICS Performance Evaluation Review, Vol. 29, No. 3Asymptotic analysis of an on-line algorithm for the single machine completion time problem with release datesOperations Research Letters, Vol. 29, No. 3A flexible flowshop problem with total flow time minimizationEuropean Journal of Operational Research, Vol. 132, No. 3Analysis of SRPT schedulingACM SIGMETRICS Performance Evaluation Review, Vol. 29, No. 1SRPT Scheduling for Web Servers19 October 2001The Map/G/ /1/$\infty$ Queue with SRPT Service DisciplineTheory of Probability & Its Applications, Vol. 45, No. 3Parallel Machine Scheduling to Minimize Total Completion Time with Release Dates ConstraintsIFAC Proceedings Volumes, Vol. 33, No. 17Sorting of items on a moving conveyor belt. Part 2: performance evaluation and optimization of pick-and-place operationsRobotics and Computer-Integrated Manufacturing, Vol. 16, No. 2-3Scheduling on a Constant Number of MachinesA Review of Machine Scheduling: Complexity, Algorithms and ApproximabilityScheduling Models and Algorithms for TMA Traffic ManagementRanking Dispatching Rules by Data Envelopment Analysis in a Job Shop Environment13 September 2016 | IIE Transactions, Vol. 28, No. 8On-Line Algorithms for a Single Machine Scheduling ProblemOn-line scheduling to maximize task completionsNetwork of queues modeling in flexible manufacturing systems : a survey29 March 2011 | RAIRO - Operations Research, Vol. 27, No. 2A branch-and-bound algorithm to minimize total flow time with unequal release datesNaval Research Logistics, Vol. 39, No. 6Further applications of the optimal strategy srpt to media access protocols in local area networksEuropean Transactions on Telecommunications, Vol. 3, No. 3A branch-and-bound algorithm to minimize total tardiness with different release datesNaval Research Logistics, Vol. 39, No. 2Central processor scheduling using I/O behaviour modelsInternational Journal of Systems Science, Vol. 21, No. 10The steady-state appearance of the M/G/1 queue under the discipline of shortest remaining processing time1 July 2016 | Advances in Applied Probability, Vol. 22, No. 02The steady-state appearance of the M / G /1 queue under the discipline of shortest remaining processing time1 July 2016 | Advances in Applied Probability, Vol. 22, No. 2Further results on a new combined strategy based on the SRPT-principleIEEE Transactions on Communications, Vol. 38, No. 5The performance of multiprogrammed multiprocessor scheduling algorithmsACM SIGMETRICS Performance Evaluation Review, Vol. 18, No. 1Chapter 11 Queueing networksApplying the SRPT Principle to Improve the Performance of the CSMA/CD Media Access Control ProtocolLimits on stationary queue length under various service disciplinesJournal of Soviet Mathematics, Vol. 40, No. 4Stationary deterministic flows: II. The single-server queueTheoretical Computer Science, Vol. 52, No. 3Stochastically minimizing the number of customers in exponential queuing systemsEuropean Journal of Operational Research, Vol. 27, No. 1Evaluation of the Optimal SRPT Strategy with OverheadIEEE Transactions on Communications, Vol. 34, No. 4Process Scheduling in a Computer SystemIEEE Transactions on Computers, Vol. C-34, No. 7Optimal Resource Allocation for Two Processes*29 July 2013 | AT&T Technical Journal, Vol. 64, No. 1Serving process with least thinking time maximizes resource utilizationIEEE Transactions on Automatic Control, Vol. 29, No. 11The serving process with least thinking time maximizes resource utilizationOn reducing time spent in M/G/1 systemsEuropean Journal of Operational Research, Vol. 9, No. 3Scheduling jobs by stochastic processing requirements on parallel machines to minimize makespan or flowtime14 July 2016 | Journal of Applied Probability, Vol. 19, No. 01Scheduling jobs by stochastic processing requirements on parallel machines to minimize makespan or flowtime14 July 2016 | Journal of Applied Probability, Vol. 19, No. 1Scheduling Stochastic Jobs on Parallel Machines to Minimize Makespan or FlowtimeAdaptive Processor Scheduling Based On Approximating Demand Distribution25 May 2016 | INFOR: Information Systems and Operational Research, Vol. 15, No. 2Multiple feedback at a single-server stationStochastic Processes and their Applications, Vol. 5, No. 2A hamiltonian approach to optimal stochastic resource allocation1 July 2016 | Advances in Applied Probability, Vol. 9, No. 01A hamiltonian approach to optimal stochastic resource allocation1 July 2016 | Advances in Applied Probability, Vol. 9, No. 1Scheduling, Queues and Dynamic Allocation IndicesScheduling Techniques for Operating SystemsComputer, Vol. 9, No. 10Multi-queue scheduling of two tasksActa Informatica, Vol. 7, No. 2A simulation tool for performance evaluation of the IBM 360/75International Journal of Computer & Information Sciences, Vol. 3, No. 1Scheduling for Minimum Total Loss Using Service Time DistributionsJournal of the ACM, Vol. 21, No. 1Flow Shop SchedulingSpeed Scaling Functions for Flow Time Scheduling Based on Active Job CountNew On-Line Preemptive Scheduling Policies for Improving Real-Time BehaviorPerformance evaluation of a new CSMA/CD protocol based on the SRPT principleScheduling packet transmissions in a multi-hop packet switched network based on message lengthSize-based adaptive bandwidth allocation: optimizing the average QoS for elastic flowsQuantifying the properties of SRPT schedulingSize-based scheduling policies with inaccurate scheduling informationSimulation evaluation of hybrid srpt scheduling policiesA QoS framework for heavy-tailed traffic over the wireless InternetSWIFT: scheduling in web servers for fast response timeAn optimal algorithm for scheduling soft-aperiodic tasks in fixed-priority preemptive systemsOnline scheduling algorithms for improving performance of pick-and-place operations on a moving conveyor beltScheduling heavy-tailed data traffic over the wireless Internet Volume 16, Issue 3May-June 1968Pages 457-707 Article Information Metrics Information Published Online:June 01, 1968 © 1968 INFORMSCite asLinus Schrage, (1968) Letter to the Editor—A Proof of the Optimality of the Shortest Remaining Processing Time Discipline. Operations Research 16(3):687-690. https://doi.org/10.1287/opre.16.3.687 PDF download
Referência(s)