本文主要研究一类工件加工需要额外资源的调度问题,该问题在地球观测卫星数据下载等领域有着重要的应用。通常情况下工件的加工除了机器资源外还需要的其他额外资源才能更好的完工,所以我们把除了机器设备以外的其他资源统称为额外资源。本文主要研究了两类机器环境为平行机的该问题模型,研究的核心是近似方案和近似算法的设计,以及最坏情况界的证明,同时结合智能算法设计和数值实验进行分析。全文内容具体如下:论文第一章简单介绍了调度问题的基本概念、经典的调度问题和额外资源调度问题的研究现状,阐述了本文具体需要研究的调度问题模型。首先,研究了一类平行机环境下工件加工需要额外资源的调度问题。在该问题中,工件需要在m台平行机上进行加工,其中机器数m为固定的数值,有种额外资源且每种资源只有一个单位可用,同时工件的加工要占用一个单位的某种资源才能进行,目标为最小化Cmax,用三参数表示为Pm｜resλ11｜max。该问题已知是NP-难的,前人给出了该问题的一个最坏情况界为2-2/（m+1）的近似算法,本文改进了该算法,给出了该问题的一个多项式时间近似方案（PTAS）,从而给出了该问题的最好近似算法。其次,对于上述问题,本文研究了每种额外资源同一时刻具有两个单位可用的更为一般情况下的模型,用三参数法表示为Pm｜resλ21｜max。该问题尚未有已知的近似算法结果,本文给出了该问题的一个简单近似算法,并证明该算法的最坏情况界为3-2/m。之后,考虑到问题的复杂性,研究了该类问题的启发式算法实现,建立了该问题的整数规划模型,给出了该问题的遗传算法求解设计,并通过大量的数值实验分析,从算法解的质量、算法解的收敛速度和稳定性上说明了本文设计算法的有效性。最后,总结了论文的工作,分析了所研究问题的结论和未来可以进一步研究的方向。