[科普中国]-调度理论

发展史

在过去的几十年中,人们对调度问题进行了大量的研究工作。从上个世纪50年代起,调度问题的研究就受到应用数学、运筹学、工程技术等领域科学家的重视,科学家们利用运筹学中的线性规划、整数规划、目标规划、动态规划及决策分析方法,研究并解决了一系列有代表意义的调度和优化问题。但是，人们普遍把Conway、Maxwell和Miller三人有关调度的研究工作作为调度理论研究的正式开始,他们3人也被人们称为调度理论的奠基人。

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

调度理论根据加工系统的复杂度,生产调度可以分为单机调度、Job-shop调度、Flow-shop调度、Open-shop调度、多机器并行加工(K-machineinparallel)调度等几个基本类型。

单机调度是指所有的操作任务都在一台机器上完成，需要对任务进行优化排队；Job-shop调度是最一般的调度类型，它是指由m个不同的机器加工n个有特定加工路线(顺序)的工件，不同工件的工序间没有顺序约束,工序加工不能中断；Flow-shop调度假设所有工件都在同样的设备上加工，并有一致的加工操作和加工顺序；多机器并行加工调度是指多台机器并行加工工件,而且并行加工的机器和工件都是类似的-实际的调度问题通常是上述几种调度类型的组合。

根据优化准则,可以分为基于代价和性能的调度两大类。代价包括为了实现调度方案所消耗的各种费用和所造成的损失,如运行费用、运输费用、存储费用和延期交货损失等。性能主要包括设备利用率、最大完成时间、拖延加工任务的百分比等。虽然在理论分析上,大部分只注意调度的性能,但在实际生产中,通常要综合考虑代价和性能两方面因素。

根据生产环境的特点,可将调度分为确定性调度和随机性调度。前者是指加工时间和其他参数是已知的、确定的量;而后者的加工时间和有关参数是随机的变量。

根据加工任务或被加工工件的特征,可将调度分为静态调度和动态调度。静态调度是指所有待安排加工的工件均处于待加工状态,因而进行一次调度后,各作业的加工被确定,在以后的加工过程中就不再改变;动态调度是指作业依次进入待加工状态,各种作业不断进入系统接受加工,同时完成加工的作业又不断离开,还要考虑作业环境中不断出现的不可预测的动态扰动。1