首页 理论教育调度理论的历史和发展

调度理论的历史和发展

【摘要】:人们普遍把Conway、Maxwell和Miller三人有关调度的研究工作作为调度理论研究的正式开始,他们三人也被人们称为调度理论的奠基人,此后30多年的调度理论和应用研究都受到他们的影响。有关调度理论没有在实践中大规模应用的原因有很多说法,一种比较有说服力的说法是这样的:现有的调度理论和方法对于解决实际调度问题仍然是不够的,需要重新考虑和进一步扩展。

在过去的几十年中,人们对调度问题进行了大量的研究工作。从20世纪50年代起,调度问题的研究就受到应用数学运筹学工程技术等领域科学家的重视,科学家们利用运筹学中的线性规划、整数规划、目标规划、动态规划及决策分析方法,研究并解决了一系列有代表意义的调度和优化问题。人们普遍把Conway、Maxwell和Miller三人有关调度的研究工作作为调度理论研究的正式开始,他们三人也被人们称为调度理论的奠基人,此后30多年的调度理论和应用研究都受到他们的影响。20世纪70年代,人们开始注意并重视调度复杂性问题的研究,提出了用于研究算法有效性和问题难度的计算复杂度理论,许多调度问题被证明为NP(non-deterministic polynomial)完全问题。

20世纪70年代后期,经典调度理论取得了重要进展,并且作为一门应用数学学科已经基本成熟,但是实际调度问题与经典调度问题还有相当的距离。人们经常会问到这样的问题:调度理论的研究成果有多少已经应用到实际调度问题中,比如敏捷制造、实时系统、空中管制、自适应容错和机器人等领域中的调度问题。这是一个很难回答的问题,因为调度研究的分类经常是模糊不清的,并且某些调度研究是在很具体的层次上,通用价值很小。有关调度理论没有在实践中大规模应用的原因有很多说法,一种比较有说服力的说法是这样的:现有的调度理论和方法对于解决实际调度问题仍然是不够的,需要重新考虑和进一步扩展。当然,严重阻碍经典调度理论研究取得重大进展和突破的关键还是调度问题的NP性质,实际调度问题往往都是非常复杂的,没有确定的物理和自然规律可循,因此是非常难解的,并且大多是没有精确解的。因此,仅仅依靠经典调度理论中基于解析优化的技术和方法,试图解决属于NP完全问题的实际调度问题,不可避免地会遇到难以逾越的障碍。

从20世纪80年代初开始,人们一直在尝试并致力于解决实际调度问题,调度研究由理论研究转向应用研究阶段。在这样的历史背景下,应用人工智能、计算智能和实时智能研究成果,解决实际调度问题的智能调度方法就走上了历史的舞台。