基于网络流的多并行机可中断开放车间调度算法

Algorithm of preemptive open-shop scheduling with parallel machines based on network flow

为提高开放车间的生产效率,研究了多并行机可中断开放车间调度问题,提出了基于网络流的调度算法。针对车间的特点,建立了以制造期最短为目标的整数规划模型,提出了工件有就绪时间约束时制造期下界的计算方法。采用网络流理论表示机器与工件间的分配关系和时间约束,建立了开放车间的网络流模型,将调度问题转换为最大流问题。引入最小负载优先和最大工作量优先两条启发式规则,设计了基于预流推进的最大流算法,并针对最大流算法中存在的局部优化问题,提出了最大流优化方法,得到机器资源的分配结果。在此基础上,建立了加工时间矩阵及减量集合,求得各机器上工件的加工顺序。使用两组随机数据对算法进行了实验,通过与制造期下界的对比,验证了算法的正确性。

To improve the production efficiency of open-shop, the preemptive open-shop scheduling with parallel machines was studied, and a network-flow-based algorithm was presented. A mixed integer programming model was established with the objective to minimize the make-span based on the characteristics of the open-shop, and the method was proposed to calculate the lower bound of make-span. Distribution relationships and time constraints between machine and workpiece was represented by network flow theory. Network flow model of open workshop was established which transformed scheduling problem into maximum flow problem. Two heuristic rules of minimum load priority and maximum workload priority were introduced, and maximum flow algorithm based on pre-flow pushing was designed. To deal with local optimization problems in maximum flow algorithm, optimization method for maximum flow was proposed and distribution of machine resources was also obtained. Based on these, processing time matrix and decrementing set were established to obtain sequences of tasks processed by each machine. Validity of the developed scheduling algorithm was illustrated by two random examples.