×

Sample-path conservation laws, with applications to scheduling queues and fluid systems. (English) Zbl 0966.90022

Summary: 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 Skorokhod problem and its minimal solution.

MSC:

90B22 Queues and service in operations research
90B36 Stochastic scheduling theory in operations research
60K25 Queueing theory (aspects of probability theory)
PDFBibTeX XMLCite
Full Text: DOI