关键词: 开放车间, 调度, 并行机, 网络流, 整数规划, 调度算法

Abstract: 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.

Key words: open-shop, scheduling, parallel machine, network flow, integer programming, scheduling algorithms