Canada Spends Logo

Explorez notre analyse du budget 2026

Grant: Discovery Grants Program - Individual

University of Toronto

$24,000.00

Integrating combinatorial optimization with queueing theory for dynamic scheduling

EF 2011-12

Résumé
A wide variety of industries and services are faced with making decisions about the assignment of a stream of incoming jobs to a complex set of resources. For example, to deliver chemotherapy, a hospital needs to take into account the fact that patients may arrive early or late for their appointments, that differing shelf-lives and specificities of drug regimens create a challenge for on-time drug preparation and/or storage, and that the time, equipment (e.g., beds, chairs), rooms, and staff required for the treatment of a patient may change based on the patient's condition. Similar problems arise in manufacturing, where production, maintenance, and delivery operations must be scheduled; in telecommunications where bandwidth must be allocated to fulfill user needs; and in transportation applications such as runway scheduling. Common among all these problems is the stochastic arrival of a varying requests which must be met by the allocation complex combinations of resources. The two primary areas of research on such dynamic scheduling problems, queueing theory and combinatorial optimization, have tended to address the two major challenges of such problems in isolation: queueing theory has focused on the stochastic nature of job arrivals and processing requirements while largely ignoring the complex resource requirements; conversely, combinatorial optimization has tended to ignore the dynamism and uncertainty, concentrating on the challenges of the underlying (deterministic) combinatorial structure arising from resource usage and timing constraints. The central thesis of this research is that a hybrid approach that is able to combine long-term reasoning about uncertainty with short-term optimization of the current, known portion of the problem can lead to better performance than either of these approaches separately. This project proposes a problem-driven approach to the investigation of this thesis and aims to make contributions to both queueing theory and scheduling, practice and theory.
Programme
Discovery Grants Program - Individual
Bénéficiaire
Emplacement
Ontario, Canada
Type de bénéficiaire
Academia
Type
Grant
Source
NSERC's Awards Data

Tel que publié

Application id
312517-2010
Name nom
Beck, Christopher
Department département
Mechanical and Industrial Engineering
Organization id
31
Institution établissement
University of Toronto
Province en
Ontario
Province fr
Ontario
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2011
Competition year année de concours
2010
Award amount
24000
Program id
RGPIN
Program nane en
Discovery Grants Program - Individual
Program name fr
Programme de subventions à la découverte - individuelles
Group en
Discovery grants programs
Group fr
Programmes de subventions à la découverte
Committee code
1509
Committee name en
Civil, Industrial and Systems Engineering
Committee name fr
Génie civil, industriel et des systèmes
Area of application code
500
Area of application group en
Manufacturing processes and products
Area of application group fr
Procédés et produits industriels
Area of application en
Manufacturing processes and products
Area of application fr
Procédés et produits industriels
Research subject code
1601
Research subject group en
Industrial engineering
Research subject group fr
Génie industriel
Research subject en
Operations research and management science
Research subject fr
Recherche opérationnelle et science de la gestion
Partie
2
Nb partie
5
Application title
Integrating combinatorial optimization with queueing theory for dynamic scheduling
Keyword
NSERC
Application summary
A wide variety of industries and services are faced with making decisions about the assignment of a stream of incoming jobs to a complex set of resources. For example, to deliver chemotherapy, a hospital needs to take into account the fact that patients may arrive early or late for their appointments, that differing shelf-lives and specificities of drug regimens create a challenge for on-time drug preparation and/or storage, and that the time, equipment (e.g., beds, chairs), rooms, and staff required for the treatment of a patient may change based on the patient's condition. Similar problems arise in manufacturing, where production, maintenance, and delivery operations must be scheduled; in telecommunications where bandwidth must be allocated to fulfill user needs; and in transportation applications such as runway scheduling. Common among all these problems is the stochastic arrival of a varying requests which must be met by the allocation complex combinations of resources. The two primary areas of research on such dynamic scheduling problems, queueing theory and combinatorial optimization, have tended to address the two major challenges of such problems in isolation: queueing theory has focused on the stochastic nature of job arrivals and processing requirements while largely ignoring the complex resource requirements; conversely, combinatorial optimization has tended to ignore the dynamism and uncertainty, concentrating on the challenges of the underlying (deterministic) combinatorial structure arising from resource usage and timing constraints. The central thesis of this research is that a hybrid approach that is able to combine long-term reasoning about uncertainty with short-term optimization of the current, known portion of the problem can lead to better performance than either of these approaches separately. This project proposes a problem-driven approach to the investigation of this thesis and aims to make contributions to both queueing theory and scheduling, practice and theory.