Stochastic Scheduling with Abandonment: Necessary and Sufficient Conditions for the Optimality of a Strict Priority Policy

• 成果类型: Article
• 署名作者: Chen, Gang; Gayon, Jean-Philippe; Lemaire, Pierre
• 署名单位: Guangzhou University; Universite Clermont Auvergne (UCA); Polytechnic Institute of Clermont Auvergne; Centre National de la Recherche Scientifique (CNRS); IMT - Institut Mines-Telecom; Mines Saint-Etienne; Communaute Universite Grenoble Alpes; Institut National Polytechnique de Grenoble; Universite Grenoble Alpes (UGA); Centre National de la Recherche Scientifique (CNRS)
• 刊物名称: OPERATIONS RESEARCH
• ISSN/ISSBN: 0030-364X
• DOI: 10.1287/opre.2022.2285
• 发表日期: 2023
• 页码: 1789-1793
• 关键词: stochastic scheduling; ABANDONMENT; strict priority policy; dynamic programming

摘要

We consider a stochastic scheduling problem in clearing systems with two types of jobs, each characterized by a general service time distribution, an exponentially distributed lifetime, and a reward. A job abandons the system if its waiting time in the queue is larger than its lifetime. Preemption is not allowed. The objective is to maximize the total expected reward. When service times are homogeneous, we provide a set of necessary and sufficient conditions for the optimality of a strict priority policy. When service times are heterogeneous and exponentially distributed, we conjecture a set of necessary conditions, which would also be sufficient when one parameter is identical (reward or lifetime rate) for the two types of jobs.