Business Analytics for Flexible Resource Allocation Under Random Emergencies
与一家大型多州燃气公司合作，研究在已知任务和随机紧急任务并存下的资源分配问题，提出两阶段分解方法，通过启发式算法和随机混合整数规划最小化加班时间，预计可减少55%加班。
In this paper, we describe both applied and analytical work in collaboration with a large multistate gas utility. The project addressed a major operational resource allocation challenge that is typical to the industry. We study the resource allocation problem in which some of the tasks are scheduled and known in advance, and some are unpredictable and have to be addressed as they appear. The utility has maintenance crews that perform both standard jobs (each must be done before a specified deadline) as well as respond to emergency gas leaks (that occur randomly throughout the day and could disrupt the schedule and lead to significant overtime). The goal is to perform all the standard jobs by their respective deadlines, to address all emergency jobs in a timely manner, and to minimize maintenance crew overtime. We employ a novel decomposition approach that solves the problem in two phases. The first is a job scheduling phase, where standard jobs are scheduled over a time horizon. The second is a crew assignment phase, which solves a stochastic mixed integer program to assign jobs to maintenance crews under a stochastic number of future emergencies. For the first phase, we propose a heuristic based on the rounding of a linear programming relaxation formulation and prove an analytical worst-case performance guarantee. For the second phase, we propose an algorithm for assigning crews that is motivated by the structure of an optimal solution. We used our models and heuristics to develop a decision support tool that is being piloted in one of the utility's sites. Using the utility's data, we project that the tool will result in a 55% reduction in overtime hours. This paper was accepted by Noah Gans, special issue on business analytics.