基于最短时间碎片的在线生产调度算法研究

针对订单型企业的在线生产调度问题,文章通过统计每个设备上允许插入工序的时间区间,提出了基于最短时间碎片的启发式在线生产调度算法.该算法的主要思路是将工序的先后约束关系和在同一设备上的先后执行关系统一建模为无圈有向图,从而依据最短时间碎片将新订单的调度过程转化为在有向图中添加顶点和有向边的过程.仿真实验结果表明该算法可以在保证订单交付期的前提下实现排产任务,并尽可能少地变更已排产工序在设备上的相对位置;在订单频繁到达时,调度的设备利用率较高,达到了约94%;此外,算法运行较快,适用于较大规模在线生产调度问题的求解.

Shortest time interval based algorithm for on-line job scheduling

In this paper, we are mainly concerned with the on-line job scheduling problem in the order-oriented enterprise. By analyzing time intervals on devices that a new task can be inserted in, an algorithm based on shortest time interval for on-line job scheduling is proposed. Its main idea is to model the scheduling problem as an acyclic digraph in graph theory, and then the scheduling can be realized by adding vertices and edges in a digraph. Simulation results show that the algorithm performs well with guaranteeing the deadline of each other, and changes little the relative execution sequences of tasks on each device. There are fewer time intervals on devices when orders come frequently, and the utilization rate of devices is very high, reaching nearly 94% in the simulation results. In addition, the algorithm runs fast. Thus, it is suitable for solving large-scale on-line job scheduling problem.