Integration of Queueing and Scheduling
J. Christopher Beck
Douglas G. Down
Tony T. Tran
In a real scheduling problem, the set of jobs (customers/requests/tasks) to be scheduled changes dynamically over time, each job has specific processing requirements and the actual processing times of jobs are affected by various types of uncertainty. In order to solve such problems, an approach is needed that can handle their combinatorial structure as well as their stochastic and dynamic nature. Scheduling research has mostly focused on devising effective methods for solving deterministic problems with a complex combinatorial structure, although there has recently been an increasing interest in modelling and solving of scheduling problems in dynamic and uncertain environments. In queueing theory, on the other hand, scheduling problems with a simpler combinatorial structure but with stochastic and dynamic characteristics have been considered for a long time. The main objective of this project is to develop an effective methodology for solving scheduling problems arising in dynamic and stochastic environments based on the integration of approaches from the scheduling and queueing theory literature.
SGS Doctoral Completion Award
- Terekhov, D., Tran, T.T., & J. C. Beck. "Investigating Two-Machine Dynamic Flow Shops Based on Queueing and Scheduling", Proceedings of ICAPS'10 Workshop on Planning and Scheduling Under Uncertainty, Toronto, Canada, 2010.