Optimal Dynamic Scheduling in Jackson Networks

Keith W. Ross

    Research output: Contribution to journalArticlepeer-review


    Considered is a Jackson-like network that supports J types of interactive traffic (e.g., interactive messages) as well as I types of noninteractive traffic (e.g., file transfers, facsimile). The service-time distributions and the internal routing are homogeneous for all traffic types, but can be node (queue) dependent. The problem is to find a scheduling control that minimizes a weighted sum of the average end-to-end delay for the noninteractive types and at the same time ensures that the average end-to-end delays for the interactive types be below given design constraints. Conservation laws are first established, which are shown to yield the base of a polymatroid. The optimal control problem is then transformed into a linear program with the feasible region being the polymatroid base truncated by delay constraints. Exploiting the problem structure, we identify an optimal control that partitions the traffic types into I + r(0 ≤ r ≤ J) ordered groups and applies a strict priority rule among the groups. Each of the first I groups has exactly one noninteractive type and a (possibly null) set of interactive types. All of the remaining r groups consist of interactive types only. An algorithm is developed, which does the grouping and solves the optimization problem. A decentralized implementation of the optimal control is also discussed.

    Original languageEnglish (US)
    Pages (from-to)47-53
    Number of pages7
    JournalIEEE Transactions on Automatic Control
    Issue number1
    StatePublished - Jan 1989

    ASJC Scopus subject areas

    • Control and Systems Engineering
    • Computer Science Applications
    • Electrical and Electronic Engineering


    Dive into the research topics of 'Optimal Dynamic Scheduling in Jackson Networks'. Together they form a unique fingerprint.

    Cite this