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

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

项目编号： No.61300016

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

立项/批准年度： 2014

项目学科： 自动化技术、计算机技术

项目作者： 陈鑫

作者单位： 大连理工大学

项目金额： 23万元

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

中文关键词： 半在线调度；等级约束；竞争比；任务损失；（元）启发式算法

英文摘要： 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.

英文关键词： Semi-online scheduling；Hierarchy constraint；Competitive ratio；Late work；(meta) heuristic method