中文摘要：

项目主要对批调度、基因组重排以及相关问题的算法和复杂性问题进行了研究。 批调度问题源于半导体制造中的预烧工序，在金属切割、服装制造、无线广播等领域有实际应用。在批调度中，不同工件可以作为一批同时被加工，而这批的加工时间等于这批工件的最大给定处理时间。基因组重排在研究物种进化、疾病诊断等方面有重要应用。 项目在批调度方面对可拒绝且工件大小可能不同的情况第一次给出了研究并给出了一个常数近似算法，其中用到的方法将对研究类似问题提供有益的参考。对可拒绝且目标函数是完成时间之和加惩罚值之和的情况给出了第一个结果。另外，项目对复杂的批流水车间调度给出了一个遗传算法并用程序实现。对复杂的车间调度问题给出了若干共生进化算法。对基因组重排中的反转操作和移位操作给出了多项式时间算法。项目还对相关的参数化复杂性问题和货郎担问题的多项式时间近似方案的设计进行了研究。 项目发表论文17篇，其中Theoretical Computer Science 2篇，《计算机学报》1篇，《计算机研究与发展》1篇。其它EI索引论文9篇，其它刊物论文4篇。目前正准备投稿论文2篇。培养博士3名，硕士3名。