导　　师： 马军

学科专业： H1202

授予学位： 硕士

作　　者： ;

机构地区： 山东大学

摘　　要： 近年来,计算机在交通控制、通讯网络等各个领域得到了广泛的应用。支持上述应用的基础理论问题为求解该领域内的NP完全问题的实用与快速算法,对上述领域内NP完全问题的快速算法的研究已经成为近年来计算机科学领域内的一个热点。本论文主要研究具有共享资源竞争的任务调度问题的快速算法。 在很多系统中,系统中的任务需要一定的资源完成,在任务执行完毕后就释放所占用的资源,任何两个需要相同资源而又互相冲突的任务不能同时进行。这属于具有共享资源竞争的任务调度问题的研究范畴,该类调度问题在现实世界具有广泛的应用,如计算机的实时控制、并行与分布式计算中的多处理机对共享资源的竞争解决问题、通讯过程中多个信源对线路的竞争求解、通信控制软件设计、移动通信控制等。采用何种调度方式和调度算法,将直接影响到系统的运行性能,因此对该类调度问题的研究具有广泛的意义。 本文首先以十字路口交通调度问题和哲学家就餐问题提出短时资源混杂占用型任务调度问题（简称DHDD）,该问题一般可描述为:在一定的时间区间内,让尽可能多的任务使用资源,并能避免死锁、饿死等现象的发生。在DHDD问题中,一个任务允许与任务集中若干任务共享资源,而同时又不允许与任务集中的某些任务共享资源。通常一个任务本身是由若干子任务组成,即表示一个任务类。以十字路口交通调度为例,一个方向的车辆集合为一个待调度的任务,而其中每辆汽车为子任务。为不产生混乱,我们称任务类中的任务为子任务,并称任务类中的子任务数为该任务的权。每一个任务内的子任务个数是随时间变化的,所以整个调度过程是一个联机调度过程。文章以互斥图G（V,E）表示问题的数学模型,给出了调度算法,首先把图G的顶点划分成k个独立集V₁,V₂,…V_k,设WT为系统要求任一任务可能等待的最长

关 键 词： 调度算法 图的顶点独立集 图的顶点着色 难解问题 近似计算

分 类 号： [TP393.01]

领　　域： [自动化与计算机技术] [自动化与计算机技术]