Research On Open-Shop Scheduling Problem Based On Network Flow

Open-shop scheduling problem can be considered as a special type of shop scheduling problem. Because of the wide application field, it has been paid more and more attention. In this paper open-shop scheduling problem with parallel machine is discussed, in which feasible scheduling scheme to minimize the makespan is obtained under two conditions:the work piece has a time window constraints; it is allowed to be interrupted but not postponement during the machining process.In this paper, the process of solving open-shop scheduling problem can be divided into two stages:resource allocation and scheduling. In the stage of resource allocation, first of all, linear programming model is established to obtain the feasible allocation scheme; then, network flow model of open-shop scheduling problem is built in which the machines and the work pieces are denoted by nodes and the constrained conditions of the shop can be substituted for arc capacity; at last, on the basis of having obtained the feasible solution by applying the maximum network flow theory, the allocation result is optimized to achieve the target of minimizing the makespan by utilizing paramatric max-flow network. In the stage of scheduling, firstly a rule is made so that the processing time can be distributed to every parallel machine; secondly, the processing time matrixes are separately established in every interval and in the way of choosing the decrement set the final scheduling results can be gained.In the end, the algorithm is proved to be right by analyzing the calculation examples, and the prototype of open-shop scheduling system is developed in VC++6.0 software environment in which the database of SQL Server2000 is used as its Server.The system possesses an interactive interface, and it can represent the scheduling solution visually in the form of gantt chart.