Stable and Utility-Maximizing Scheduling for Stochastic Processing Networks

摘要

Stochastic Processing Networks (SPNs) model manufacturing, communication, and service systems. In such a network, service activities require parts and resources to produce other parts. Because service activities compete for resources, a scheduling problem arises. This paper proposes a deficit maximum weight (DMW) algorithm to achieve throughput optimality and maximize the net utility of the production. It overcomes the instability problem of Maximum-Weight Scheduling in SPNs.