Sample-path conservation laws,with applications to scheduling queues and fluid systems |
| |
Authors: | Green Tuell C. Stidham Shaler |
| |
Affiliation: | (1) American Airlines, 4333 Amon Carter Boulevard, MD 5358, Fort Worth, TX 76155, USA;(2) Department of Operations Research, University of North Carolina at Chapel Hill, Chapel Hill, NC 27599-3180, USA |
| |
Abstract: | The achievable-region approach, based on strong conservation laws, has most often been applied to stochastic scheduling and other control problems in the context of performance measures that are steady-state expected quantities. For some problems, however, strong conservation laws hold for performance measures at every time point on every sample path. We exploit this property to study optimal control for certain scheduling problems on a sample-path basis. Examples include preemptive scheduling to minimize a weighted sum of work in the system in each class, nonpreemptive scheduling to minimize a weighted sum of the number of customers in each class (when all classes have the same service-time distribution), and scheduling the processing of fluid in a multiclass fluid system operating in a random environment. The last problem is solved by considering the related Skorohod problem and its minimal solution. This revised version was published online in June 2006 with corrections to the Cover Date. |
| |
Keywords: | scheduling queues sample paths strong conservation laws achievable region Skorohod problem |
本文献已被 SpringerLink 等数据库收录! |
|