Research On Exact Algorithm Of Two-Stage Hybrid Flow Shop Schedule Problem

Flow Shop Scheduling has been on the subject of widespread attention and study since been proposed. In this issue, only a few special are cases polynomial solvable, while most cases are NP-Hard. Therefore, the study of the problem in the most concentrated are the proof of complexity, application in a particular case, approximation algorithms, accurate algorithm and so on. Hybrid Flow shop scheduling of this study comes from the flow shop scheduling and parallel machine scheduling.To Hybrid Flow shop scheduling, the number of machines in each stage flow shop scheduling is not necessarily the same, and there are different forms between scheduling stage. This paper concern on a Two-Stage Hybrid Flow shop scheduling of which the first stage only one machine, the second stage of more than 1 station parallel machines(m1 = 1, m2 = m> 1). First, the paper introduces the flow shop problem. On the basis of this, the paper gives the problem and the model of the problem, and gives the proof of the complexity. Secondly, the hybrid flow shop scheduling problem is transformed into Packing Strip problem. Thirdly, By means of several different relaxation of the original problem and the problem of relaxation, an upper bound and several lower bound of the problem are obtained by using the Johnson algorithm, and using mixed integer programming to model the problem and relax the problem. On the basis of the upper bound and lower bounds, based on the idea of branch and bound and Benders decomposition, an exact algorithm is presented to solve this problem. Finally, the algorithm is compared with the two data sets, which proves the feasibility and effectiveness of the proposed algorithm.