Dynamic scheduling with uncertain job types

Zuo-Jun Max Shen, Jingui Xie, Zhichao Zheng and Han Zhou

European Journal of Operational Research, 2023, vol. 309, issue 3, 1047-1060

Abstract: Uncertain job types can arise as a result of predictive or diagnostic inaccuracy in healthcare or repair service systems and unknown preferences in matching service systems. In this paper, we study systems with multiple types of jobs, in which type information is imperfect and will be updated dynamically. Each job has a prior probability of belonging to a certain type which may be predicted by data, models, or experts. A job can only be processed by the right machine, and a job assigned to the wrong machine must be rescheduled. More information is learned from the mismatch, and job type probabilities are updated. The question is how to dynamically schedule all jobs so that they can be processed in a timely fashion. We use a novel coupling and inductive method to conduct optimality analysis. We obtain the near-optimal policy regarding completion time, named the less-uncertainty-first policy, when there are two types of jobs; the insights it yields are used to develop heuristic algorithms for more general cases. We also consider other objectives, including the number of mismatches and the total amount of time jobs spend in the system. In our numerical study, we examine the performance of the proposed heuristics when there are more than two types of jobs under two learning schemes: dedicated learning and exclusive learning. In the extension, we also analyze an online version of the problem in which jobs arrive sequentially to the system and must be assigned immediately and irrevocably without any knowledge of future jobs. We analyze the competitive ratios of different scheduling policies and find similar insights. It is essential that managers dynamically schedule services by leveraging predictive information and knowledge learned from mismatches. Our proposed less-uncertainty-first policy, which accounts for system dynamics to avoid mismatches and resource idling, can be used to improve system efficiency in various contexts.

Keywords: Scheduling; Uncertain job types; Predictive information; Learning; Mismatch and rescheduling (search for similar items in EconPapers)
Date: 2023
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221723001479
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:ejores:v:309:y:2023:i:3:p:1047-1060

DOI: 10.1016/j.ejor.2023.02.013

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().