乘务员排班问题是航空公司面临的重要问题之一。人力成本在航空公司的日常营运过程中占了一部分重要的支出。航空公司排班问题(crew scheduling)可分为两个大问题,一个是航班串(crew pairing)的产生,另一个是航班串的分配(crew rostering),即本文所讨论的乘务员排班问题。目前的已经有很多商业排班系统,一个商业排班系统中最关键的技术是解决排班优化问题的算法。现有排班系统的优化算法多数是为西方航空公司量身定做,在应用到中国时,算法所产生出来的排班方案往往不能达到航空公司要求。在国内,机组乘务员排班不仅要考虑成本的控制,同时要兼顾乘务员工作量的公平性。在排班系统中,一种公平、合理的排班方法对于调动工作人员的工作积极性、提高工作效率都具有重要的意义。本文的主要贡献是,提出一个对国内航空公司更有效的排班问题优化算法。本文以中国某大型航班公司的具体要求为实例,探讨一个典型排班问题中需要考虑到的典型的约束条件以及中国航空公司所面临的特殊的约束条件。在此实例中,机组乘务员排班中乘务员工作量的公平性是排班主要的优化需求。工作量公平又分为多种工作时间和类型的平衡性,例如飞行时间的平衡,过夜天数的平衡等。本文由简到难逐步建立了数学模型来描述排班问题。由于排班问题包含了大量航班线和大量约束条件,是一个复杂的NP难问题,此数学模型不能直接利用已有的软件工具直接求解。因此利用启发式搜索来进行求可行解可以得到较好的效率。本研究用的贪心算法的策略,以实现飞行时间平衡的优化目标为例,分为两阶段:第一阶段在满足各种排班规则限制的前提下先分配时间跨度长,需要能力强的航班串;第二阶段分配时间跨度小,需要能力低的航班进行调整平衡性。以获取的实际运营数据验证算法结果,被证明是合理而有效的,应用此算法解决航空公司的排班,不仅仅快速而且产生的排班结果是比较平衡的。而且本文提出的贪心算法无论在公平或者覆盖率角度上对比原公司使用的商业排班系统更好。