Heuristics For Large-Scale Flow Shop Scheduling Problems

Large-scale flow shop scheduling is an important manufacturing system widely existing in industrial environments. Large-scale flow shop scheduling is the simplified model of many actual productions. And flow shop scheduling is a typically NP-complete problem, which means that it is impossible to find the global optimum in polynomial complexity. It is one of the key problems in the production management. Good algorithms for this problem can promote productivity of enterprises. So the study of large-scale flow shop scheduling plays an important role on theory and practice. In recent years, meta-heuristics and heuristics are two kinds of algorithm for flow shop problem. However, they are different in CPU-time and performance. Meta-heuristics can always obtain better solutions than heuristics but they need much more CPU-times. As well, robustness of heuristics is good but optimum can seldom be obtained. To better solve large-scale problem, two heuristics are proposed. The proposed heuristics are compared with the existing ones in both efficiency and effectiveness. The experimental results show that the proposed heuristics can solve the considered problems effectively and efficiently.First, a new heuristic DIH (Double Inserting Heuristic) is designed for large-scale flow shop scheduling problems to minimize total flowtime, which integrates local-insertion of NEH and global-insertion of RZ respectively。DIH is compared with three best existing heuristics, RZ, WY and FL, on 1500 randomly generated instances. Experiment results show that DIH is very effective and efficient for flow shops with total flowtime minimization.Second, the composite heuristic CDIH is proposed for large-scale flow shop scheduling problems with total flowtime minimization. In CDIH, the solution of DIH is improved by RZ-insertion and pair-wise exchange. CDIH is compared against other three best existing composite heuristic algorithms IH7, FL-IH7 on...