Priority Scheduling of Jobs with Hidden Types
Public Deposited- Last Modified
- March 19, 2019
- Creator
-
Sun, Zhankun
- Affiliation: College of Arts and Sciences, Department of Statistics and Operations Research
- Abstract
- In service systems, prioritization with respect to the relative "importance" of jobs helps allocate the limited resources efficiently. However, the information that is crucial to determine the importance level of a job may not be available immediately, but can be revealed through some preliminary investigation. While investigation provides useful information, it also delays the provision of services. Therefore, it is not clear if and when such an investigation should be carried out. To provide insights into this question, we consider a service system with a single server and the two possible types of jobs, where each type is characterized by its waiting cost and expected service time. Jobs' type identities are initially unknown, but the service provider has the option to spend time on investigation to determine the type of a job albeit with a possibility of making an incorrect determination. Our objective is to identify policies that balance the time spent on information extraction with the time spent on service. In this dissertation we consider two settings: one with finitely many jobs present at time zero and no external arrivals; the other with exogenous arrivals. Under the assumption of linear waiting cost, our study on the first model reveals that investigation is less likely to be beneficial when one of the types is significantly dominated by the other in terms of numbers, or the two types of jobs are not significantly different from each other with respect to their importance. More interestingly, we find that if the server decides to do investigation for all jobs, it is possible that more accurate information might result in higher costs. We prove that the optimal dynamic policy can be characterized by a switching curve. One insight that comes out of this characterization is that the server should start with performing investigation when there are sufficiently many jobs at the beginning and never perform investigation when there are few jobs. Numerical study shows that the optimal policy could improve significantly upon some simple baseline policies. Heuristic policies developed based on the optimal policy perform well even with nonlinear holding cost. When there are external arrivals to the system, we show that the optimal dynamic policy is of threshold type. The structure of the optimal policy implies that when there are few less-important jobs waiting for service, the server should perform investigation; otherwise, the server should stop investigation and serve jobs directly. Given that it is almost impossible to obtain an analytical expression of the threshold, we develop a heuristic policy based on the results for the clearing system. We carry out a simulation study and find that the heuristic policy performs significantly better than No-Triage Policy in most cases; for the rest, it performs at least as well as No-Triage Policy. Finally, we study three extensions. The first extends the clearing system by considering multiple parallel servers. The second studies a queueing system in which investigation is instantaneous but incurs a fixed cost, and the last one extends the queueing system by assuming that investigation has to be done before service.
- Date of publication
- August 2014
- Keyword
- Subject
- DOI
- Identifier
- Resource type
- Rights statement
- In Copyright
- Advisor
- Kulkarni, Vidyadhar
- Ziya, Serhan
- Budhiraja, Amarjit
- Argon, Nilay
- Sun, Peng
- Degree
- Doctor of Philosophy
- Degree granting institution
- University of North Carolina at Chapel Hill Graduate School
- Graduation year
- 2014
- Language
- Publisher
- Place of publication
- Chapel Hill, NC
- Access right
- There are no restrictions to this item.
- Date uploaded
- April 22, 2015
Relations
- Parents:
This work has no parents.
Items
| Thumbnail | Title | Date Uploaded | Visibility | Actions |
|---|---|---|---|---|
|
|
Sun_unc_0153D_14885.pdf | 2019-04-09 | Public | Download |