调度问题这些年已经成为计算机科学中的一个重要问题,其中计算复杂度分析,CPU调度算法的选择,云计算与网格计算中的资源调度和任务调度等问题已经成为研究热点。以上都和经典的调度问题有着紧密联系。随着调度理论的不断发展,不同学科的不断交叉,调度各个不同领域之间也有了越来越多的联系,越来越多的学者现在开始把经典调度理论与计算机应用背景结合起来考虑,试图利用经典调度模型来模拟计算机真实情况,然后利用经典的解析方法来设计算法并求解问题。本文从磁盘整理和系统运行速度之间的一系列关系描述入手,提出了一个具有现实意义的调度问题,并对该调度问题进行建模,发现该模型在相关实际生产等领域都具有一定的适用,通过对国内外研究进行综述提炼其理论价值和现实意义,并且设计了多项式时间最优算法求解该问题。对相应调度问题进行建模后,分别针对单处理器环境和多处理器环境各自的一些目标设计最优算法进行求解。对单处理器问题,本文研究的是最小化所有任务的最大完成时间和最小化所有任务的总完成时间；对多处理器器问题,本文只研究了最小化所有任务的总完成时间。本文的主要研究工作分为下面几个方面：(1)对国内外相关问题的调度模型进行研究,包括研究问题模型中所涉及的各个子模型和他们研究问题的相关求解算法。其中前者主要工作是总结归纳前人提出的各个子模型的不同表达式,明白它们之间的不同和各自表达的意义。(2)针对从磁盘整理中延伸出的扩展问题,对其建立相应的模型,其中多处理器环境的模型是单处理器模型的扩充,并给出模型中用到的数学符号。(3)经过预备工作,首先对简单的单处理器环境模型进行分析、推导、归纳,将问题的原始调度模型最终巧妙地转化为等价的指派问题,从而推断出单处理器下最小化所有任务总完成时间的目标和最小化所有任务最大完成时间的目标是多项式时间内能够解决的,并给出了各自问题的计算时间复杂度。然后扩展到相对复杂的多处理器模型,证明该环境下最小化所有任务总完成时间的目标是多项式时间能够得到最优解的,也给出了计算时间复杂度。(4)用本文提出的算法对一个实例进行求解,利用LINGO软件对匈牙利算法进行编程求解,并且验证本文的算法能够在多项式时间内得到问题的最优解。