两类复杂机器环境的现代排序研究

项目名称： 两类复杂机器环境的现代排序研究

项目编号： No.11201105

项目类型： 青年科学基金项目

立项/批准年度： 2013

项目学科： 数理科学和化学

项目作者： 张安

作者单位： 杭州电子科技大学

项目金额： 22万元

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

中文关键词： 排序；近似算法；计算复杂性；竞争比分析；

英文摘要： In modern scheduling, the machine environments are becoming more and more complicated, among which, the environment with machine non-availability periods and that with machine eligibility restrictions might be of most significance. This project mainly con

英文关键词： scheduling；approximation algorithm；computational complexity；competitive analysis；