Robust scheduling for flexible processing networks

DOI10.1017/APR.2017.14zbMATH Open1425.60079arXiv1610.03803OpenAlexW2962794893MaRDI QIDQ5233182FDOQ5233182

Authors: Ramtin Pedarsani, Jean Walrand, Yuan Zhong 

Publication date: 16 September 2019

Published in: Advances in Applied Probability (Search for Journal in Brave)

Abstract: Modern processing networks often consist of heterogeneous servers with widely varying capabilities, and process job flows with complex structure and requirements. A major challenge in designing efficient scheduling policies in these networks is the lack of reliable estimates of system parameters, and an attractive approach for addressing this challenge is to design robust policies, i.e., policies that do not use system parameters such as arrival and/or service rates for making scheduling decisions. In this paper, we propose a general framework for the design of robust policies. The main technical novelty is the use of a stochastic gradient projection method that reacts to queue-length changes in order to find a balanced allocation of service resources to incoming tasks. We illustrate our approach on two broad classes of processing systems, namely the flexible fork-join networks and the flexible queueing networks, and prove the rate stability of our proposed policies for these networks under non-restrictive assumptions.

Full work available at URL: https://arxiv.org/abs/1610.03803

Recommendations

• Dynamic Scheduling for a Flexible Processing Network
• Scheduling and stability aspects of a general class of parallel processing systems
• Stability of multiclass queueing networks under longest-queue and longest-dominating-queue scheduling
• Robust Scheduling to Hedge Against Processing Time Uncertainty in Single-Stage Production
• scientific article; zbMATH DE number 786512

zbMATH Keywords

robust schedulingflexible queueing networkstochastic gradient projection

Mathematics Subject Classification ID

Queueing theory (aspects of probability theory) (60K25) Sample path properties (60G17) Stochastic network models in operations research (90B15)

Cites Work

• Title not available (Why is that?)
• Probability. Theory and examples.
• Stochastic approximation. A dynamical systems viewpoint.
• On positive Harris recurrence of multiclass queueing networks: A unified approach via fluid limit models
• Title not available (Why is that?)
• Brownian models of multiclass queueing networks: Current status and open problems
• Title not available (Why is that?)
• Tightness of invariant distributions of a large-scale flexible service system under a priority discipline
• Scheduling Flexible Servers with Convex Delay Costs: Heavy-Traffic Optimality of the Generalized cμ-Rule
• The fork-join queue and related systems with synchronization constraints: stochastic ordering and computable bounds
• Dynamic Server Allocation for Queueing Networks with Flexible Servers
• Sufficient conditions for stability of longest-queue-first scheduling: second-order properties using fluid limits
• Brownian models of open processing networks: Canonical representation of workload.
• Stability analysis of parallel server systems under longest queue first
• Stability of multiclass queueing networks under longest-queue and longest-dominating-queue scheduling
• Stationary and stability of fork-join networks
• On stability and performance of parallel processing systems
• Processing networks with parallel and sequential tasks: Heavy traffic analysis and Brownian limits
• The trouble with diversity: Fork-join networks with heterogeneous customer population

Cited In (4)

• Control of fork-join processing networks with multiple job types and parallel shared resources
• Information and memory in dynamic resource allocation
• Dynamic Scheduling for a Flexible Processing Network
• Robust scheduling of metaprograms

Uses Software

• MapReduce

This page was built for publication: Robust scheduling for flexible processing networks

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5233182)