一类拟线程通信模型中的排序问题

摘要

本文讨论了一类带传递时间，且任务的先后加工顺序约束于一棵k层出树的排序问题。我们约定如果对应于一条有向边的两个任务(前驱与后继)安排到同一台机器上加工，则传递时间记为0，否则按实际传递时间对后继任务进行传递加工。同时我们假设是逐层加工任务树的；假设机器加工每个任务时不允许中断，在每一时刻每台机器至多加工一个任务；假设任务在传递加工过程中不存在系统的传输延时。这样处理突破了原有模型的三个限制：1、机器数为无限2、1-level-outtree约束3、任务在传递过程中存在传递时间cij和系统延时误差，进而抽象为一般的Pm|pseudo-deliverytimes，k-level-outtree|Cmax问题。文中对这一问题的复杂性进行了分析，之后给出一个启发式算法，文末对算法的最优性、时间复杂性、概率性态进行了分析。结果表明，我们所给的算法性能良好。

目录

文摘

英文文摘

原创性声明及授权声明

第一节引言

第二节基本概念 模型及结论

第三节问题复杂性分析

第四节算法及其性能分析

参考文献

致谢