本文考虑一类具有图约束的平行机调度问题,具体研究具有树状结构或路约束的同型平行机调度问题及具有图覆盖约束的不同类平行机调度问题。第一个问题描述为:给定无向图G(或有向图D)以及工件集,这里要求工件集与无向图G(或有向图D)中的边集(或弧集)建立一一对应关系,需要选取工件集的一个子集,使其满足无向图G(或有向图D)中树或路的属性,然后将其放置在同型平行机上处理,目标是使得机器的最大负载达到最小。第二个问题描述为:给定无向图G以及工件集,这里要求工件集与图G中边集和顶点集的并集建立一一对应关系,需要选取工件集的一个子集使其为图G中某种边覆盖,然后将其放置在不同类平行机上处理,目标是使得机器的最大负载达到最小。针对以上两个问题,我们得到以下结果:(1)当选取的工件集限制为无向图G的一棵K-树,或者限制为有向图D的一棵单源点最短路径树,我们分别设计了一个时间复杂度为f(1/ε)+O(k2)的有效多项式时间近似方案(EPTAS),这里f(1/ε)是关于1/ε的双指数函数;(2)当选取的工件集为给定两个固定顶点s和t间的路,在无向图G的情形下,我们设计了一个(2-1/m)-近似算法TVP,其时间复杂度为O(k(n2+k));特别地,在有向图D中具有两点间最短路约束的情形下,设计了一个1.618-近似算法SPP,其时间复杂度为O(n2+k(n2+klogk));(3)对于具有图覆盖约束的不同类平行机调度问题,我们设计了两个近似算法GCR和GCRm,这里算法GCR是当机器数不固定时的4-近似算法,算法GCRm是当机器数固定时的3-近似算法。这里n,m,k分别表示图的顶点数、机器数和工件数。