考虑工序序列动态时间紧迫度的逆序贪婪综合调度算法

Reverse Order and Greedy Integrated Scheduling Algorithm Considering Dynamic Time Urgency Degree of the Process Sequences

针对树状结构复杂单产品加工和装配的一般综合调度问题,该文提出考虑工序序列动态时间紧迫度(TUD)的逆序贪婪综合调度算法。提出工序排序策略,定义工序序列的时间紧迫度,将工序树逆置,采用叶对齐的方式,按照由叶到根的顺序,逐层根据叶结点所属工序序列动态时间紧迫度值由大到小的顺序确定其调度顺序,将各层排序后的叶结点依次入队列保存,最后将队列中元素逆置。提出逆序贪婪调度策略,每次以一道工序为单位,安排它在所需设备上的准调度时间点进行试调度,得到该工序的准调度方案集,选择准调度方案结束时间最小的方案,若不唯一,选择使该工序尽早加工的方案。实例表明所提算法优化了一般综合调度的结果且效率较高。

For the general integrated scheduling problem of tree structured complex single product machining and assembling,a reverse order and greedy integrated scheduling algorithm is proposed by considering dynamic TUD(Time Urgency Degree)of the process sequences.The strategy of process sorting is put forward,and the TUD of process sequence is defined.The process tree is reversed using leaf alignment,according to the order from leaf to root,the scheduling order of leaf nodes in the same layer is determined layer by layer from large to small according to the dynamic TUD values of the process sequences to which the leaf nodes belong.The sorted leaf nodes are put into the queue in turn.Finally,the elements in the queue are reversed.A reverse order and greedy scheduling strategy is proposed.Each time,a single process is taken as a unit to conduct trial scheduling at the quasi-scheduling time point in the required equipment.Quasi-scheduling scheme set of the process is obtained,and the quasi-scheduling scheme with the minimum end time is selected,and if it is not unique,the scheme is selected to machine the process as early as possible.A case shows that the proposed algorithm optimizes the general integrated scheduling results and has high efficiency.