多处理机系统上不相容作业集的分配问题

多处理机系统上不相容作业集的分配问题 The Scheduling Problem for MPS with Incompatible Jobs 黄干平 HUANG Gan\|ping 1 first-author 郑晖 ZHENG Hui 1 李世平 LI Shi\|ping 1 武汉大学数学与计算机科学学院,武汉,430072 武汉大学数学与计算机科学学院,武汉,430072 The College of Mathematics and Computer Science ,Wuhan University The College of Mathematics and Computer Science ,Wuhan University 讨论了多处理机系统 MPS（Multi Processor System ）上不相容作业集的分配算法 ,以及对该算法正确性和效率的分析和证明 ,给出了该算法的若干推论 We present a heuristic scheduling algorithm for MPS （Multi Processor System） with incompatible jobs, and give the performance analysis about this algorthm.Some scheduling problem can be solved based on the heuristic method in polymonial time complexity when the job graphs have some special structures such as bipartite graph,tree and so on. 不相容作业集 调度算法 时间复杂性 incompatible jobs scheduling algorithm time complexity 10.14188/j.1671-8836.2000.03.005 TP301 湖北省自然科学基金!（99J0 26）资助项目 2000-03-01 2021-04-01 3