本文以航班优化及航线经济效益分析系统(FORMAX)为应用背景,对机组排班中的勤务编排问题进行研究,通过优化勤务编排的算法得到正确、合理、高效的勤务。本文将勤务编排分成可行勤务的产生和勤务优化两个子问题进行研究。在分析了勤务编排规则的基础上,给出了分层次的勤务编排模型及各项优化指标。并为了得到最佳优化效果,综合平衡了各项目标函数的权重;然后总结分析了启发式算法和最优解算法的适用性,明确了启发式算法在解决大规模数据量问题时的优势。同时通过对遗传算法和模拟退火算法的仿真比较实验,论证了模拟退火算法较遗传算法具有更高的局部搜索能力;在算法设计阶段,将深度优先算法应用于可行勤务产生的过程中。本文重点研究勤务优化问题,在候选勤务集合中进行初步筛选得到初始勤务,并在初始解的基础上,分析模拟退火算法在解的邻域内寻找最优可行勤务的过程。针对模拟退火算法随机筛选过程中的不足,引入了一种启发式操作,保证了最优解的可行性。最后通过对算法的初步筛选效能、敏感度、时间复杂度、优化效果等角度的比较分析,验证了模拟退火算法产生勤务的高效性。