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

关键词：签派员 单机排序 峰值负荷 质量 席位任务分配 

单位：中国科技大学管理学院 安徽合肥230026 中国科学院科技政策与管理科学研究所 北京100190