基于峰值负荷的签派员席位任务分配问题

Dispatcher Scheduling Problems Based on the Minimum Peak Workload

本文研究的问题来源于航空公司运行控制中心的签派部门,签派员在放行航班时,既要保证航班的正点起飞,又要调节放行航班的工作劳动强度保证放行的质量,使航班在安全状态下运行。这里放行航班的工作劳动强度为单位时间内的工作时间,峰值负荷即劳动强度最大值。峰值负荷过高则工作紧张,进而推断该放行席位的任务分配不合理。文中将问题描述为任务有优先序的单机排序问题,每个任务都有一个到达时间(release time)、截止期限(deadline)和处理时间(procession time),处理时间因任务的不同而不同,目标是在绝对不准延误完成任务前提下,使单位时间的峰值负荷最小。在使单位时间峰值负荷最小的目标下,本文提出了一个有效算法,并证明该算法下的任务安排是最优安排。

The problem studied in this paper comes from the dispatchers＇ department of airline operation control centers. When dispatchers dispatch the flight, it is necessary to ensure punctuality for flights to take off, and regulate the rhythm of flight dispatched to ensure the quality of dispatch. The problem is described as a single machine scheduling problem with n task in this paper. Each task has release time, deadline and processing time, and the goal is to minimize the peak load of the machine, restrict to the conditions of each task ended before its deadline. Under the goal, an effective algorithm and the proof of the performance of algorithm are proposed.