带等级约束的半在线调度问题模型与算法研究

Online parallel machines scheduling is a classical problem in the fields of combinatorial optimization and theoretical computer science. Scheduling under hierarchy constraint is becoming a research hot topic now since it describes real world accurately. Though a number of results were given, there were abundant complicated problems to be solved, considering the complexity of real world and the variety of semi-online method. We thus consider two semi-online hierarchical scheduling problems in this research, where the first one is buffer version and the second is reassignment version. The lower bounds for both two versions are discussed and several semi-online algorithms are proposed. Furthermore, the relationship between the two versions is studied. We begin with the case of two uniform machines with two hierarchies, then m machines(m>2) with two hierarchies and finally the case of m machines with h hierarchies(2<h≤m). The research will enrich the achievements for the scheduling problem and lay more theoretical foundation for the application of this problem.

平行机在线调度问题（又称排序问题）是组合优化领域和理论计算机科学领域的热点问题之一。带等级约束的调度问题，由于能很好的反映现实中的约束关系，已引起国内外学者的广泛关注。 现有文献已给出大量关于该问题很好的结果，但考虑到实际生产环境的复杂性与半在线形式的多样性，仍有一系列复杂的问题亟待解决。本项目考虑两类带等级约束的半在线调度模型：缓冲区模型和允许任务重排模型。将分析模型的竞争比下界、设计竞争比接近以至匹配该下界的半在线算法，进而讨论两个模型相关结果之间的关联。研究过程由简入繁，先从两等级两台同类机的情况入手，进而研究两等级多台机器的情况，最终考虑多等级多台机器这种最复杂、却又最接近于实际生产环境的情况。 课题的成功实施，能够补充带等级约束调度问题的现有成果，拓展平行机调度问题的研究范畴，为调度模型的实际应用打下更为坚实的理论基础。

调度问题（又称排序问题）是运筹学、管理科学、计算机科学等领域的经典问题之一，其研究内容为如何将有限的资源、在满足一定约束条件的情况下、分配给一系列的任务，以追求某个或者多个最优化目标。三年来，项目组对项目《带等级约束的半在线调度问题模型与算法研究》进行了持续研究，共发表文章14篇，其中SCI检索5篇、EI检索6篇、核心期刊3篇。主要取得如下成果：.1、研究了在等级约束下、带缓冲区的半在线调度模型和允许任务重排的半在线调度模型，分别给出上下界一致的半在线算法；.2、研究了在等级约束下、允许有限个任务随时重新调整的半在线调度模型，并给出最优算法；.3、研究了在等级约束下、获知任务部分信息的半在线调度模型，分析模型下界并给出匹配下界的最优算法；.4、改进了带缓冲区的半在线调度问题的某些算法，获得了比前人性能更好的算法。..除了上述计划内的研究内容，在基金的支持下，项目组还获得了其他一系列好的成果。.1、调度问题虽然具有不同的最优化目标，但由于其问题本身的相似性，研究方法上具有一定的借鉴性。因此，项目组首次研究了最小化任务损失的在线模型，获得了最好可能算法；.2、除了理论分析之外，项目组还设计了平行机调度问题、DAG调度问题的（元）启发式算法，并通过实验对比验证了算法的优势。..总之，项目组很好的完成了立项中的问题，拓展了调度问题的研究范畴，并为调度问题的进一步研究打下了基础。