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.