启发式规则调度.doc

在一定的约束条件下，针对某项可以分解的工作：如何安排其组成部分所占用的资源、加工时间及先后顺序，以获得产品加工时间或成本最优。影响调度问题的因素：产品的投产期、交货期、生产能力、加工顺序、加工设备和原材料的可用性、批量大小、加工路径、成本限制等。这些都是约束条件。有些约束条件是必须满足的，如交货期，生产能力而有些是达到一定的满意程度即可，如生产成本。启发式规则算法最大的优点为就算复杂度低，能较好的应用于动态实时调度和复杂大规模调度问题。不同的调度规则具有不同的全局敏感性，所以不同的调度规则产生不同的调度方案。启发式规则的分类：启发式规则用于选择下一道在当前空闲机器上将进行加工的工序。以n个工件m台机器的车间作业计划问题为例，提出车间作业计划问题的求解算法，提出启发式调度规则。一般的规定：（1） 工件集J: J= J，J，J,其中J代表第i个工件；（2） 机器集M：M=M，MM,M,其中M代表第K台机器；（3） 工序集O：O=O，O，OO，其中O表示工件J的所有工序的集合，表示如下：O=O,OOO,其中O表示工件J的第j到工序，n为工件J的工序总数；（4） P：工序O的加工时间，i=1,2，n，j=1,2，,n；（5） R：工件J的到达时间；（6） R：工件J到达机器M的时间；（7） t：当前时间，即进行调度决策的时刻；（8） d：工件J的交货期；（9） M：工件J的加工机器；（10） Z :加工的优先级；由于调度规则的性能受到各种参数（如：车间机器的利用率、交货期等）的影响，目前尚无任何一个调度规则能够在任意的车间调度问题中表现出良好的性能。不同的调度规则针对不同的车间性能表现出较好的调度效果。常用的启发式调度规则有一下几种：1、 先到先加工的规则：它是根据任务到达的先后顺序进行安排加工的。那么在编程的时候它的优先级Z=R（其中R为工件J到达的时间）；2、 FIFO规则（first in，first out）：工件到达时间越早越优先，这个规则是针对不同的或同一批零件，在加工同一道工序用同一台机器加工的时候，哪个工件先到达机器，哪个先加工。在编程时它的优先级Z=R；3、 加工时间长短的规则：工件在系统中呆的时间越长或越短越优先的规则，在此规则中它的优先级为Z=t- R（如果在t时刻进行调度的话）；4、 加工工时越短越优先的规则：也就是工件J在第j到工序的时候如果有多台机器都能进行加工选择加工时间最短的那台机器进行加工的规则，它的优先级Z =p5、 工件剩余工序的加工工时越长越优先的规则：在不同的零件进行加工时，如果没有交货期的限制，优先加工用时较长的。它的优先级为Z =;6、 松弛时间越小越优先的规则：所谓松弛时间就是指当前时间t距离交货期的剩余时间与该项任务的加工时间的差。这是一个基于交货时期的规则，在编程时它的优先级为Z= d-t-；7、 LPT/SPT规则（longest/shortest processing time）：加工工时越长或越短越优先的规则。在几种工件同时加工的过程中将每道工序的用时都列举出来，在选择加工哪个工件时依据这道工序的加工时间的长短安排先后顺序。它的优先数位Z=P8、 EDD规则（earliest due-date）：此规则可表示为“工件的交货期越早越优先”，显然又是基于交货期的规则，则它的调度优先数为Z= d9、ODD规则（operation due-date）：工件的完工时间与交货期之间差值越小越优先的规则，其实就是规则6中当t=0时的情况，即在工件的加工伊始就开始调度的情况。它的优先数为Z=d- ；10、等待时间越短越优先的规则：即为下一工序等待的时间越短就越优先加工，这是基于车间状况的规则。设工件O当前等待加工的工序为O，在调度时刻t工件J的优先数为Z=s-t；s为工件O在第j到工序的开始时间，t为上道工序的结束时间。11、加工过程中等待时间最短的规则：在整个工件的加工过程中，等待时间越短越先加工的原则。在此规则中的优先数位Z=；这些单独的规则只能