中文摘要：

现代排序的发展趋势是机器的环境趋于复杂化，其中机器有禁用区间和机器带加工权限是两类典型情形，本项目主要研究这两类复杂机器环境的现代排序，核心内容是近似算法、在线算法的设计与分析．对有禁用区间的排序问题，重点研究机器环境为平行机或者目标函数为极小化（赋权）总完工时间的情形，研究禁用区间周期性出现、禁用区间可移动和随机禁用区间等模型，并分析工件可恢复、工件可跨越对算法设计和算法性能的影响．对带加工权限的排序问题，研究问题的计算复杂性和可近似性，研究在线算法的设计和竞争比的分析，特别是预知部分信息的（半）在线模型和工件实时到达的在线模型，考虑设计问题的最优算法．我们还将开展带加工权限排序的应用研究．对这些问题的研究一方面有益于排序理论的发展，另一方面也为排序到实际应用中的转化和推广提供技术支撑．因此本项目的研究既有理论价值，又有实际意义，是一项有创造性和前瞻性的研究工作．