Heuristics Solutions For Flow Shop Scheduling Problem

Flow shop scheduling problem with total flowtime minimization is animportant manufacturing system widely existing in industrial environments. Flowshop scheduling is the simplified model of many actual productions. And flowshop scheduling is a typically NP-complete problem, which means that it isimpossible to find the global optimum in polynomial complexity. It is one of thekey problem in the production management. Good algorithms for this problemcan promote productivity of enterprises. So the study of flow shop schedulingplays an important role on theory and practice. In recent years, meta-heuristicsand heuristics are two kinds of algorithm for flow shop problem. However, theyare different in CPU-time and performance. Meta-heuristics can always obtainbetter solutions than heuristics but they need much more CPU-times. As well,robustness of heuristics is good but optimum can seldom be obtained. To bettersolve problem, two heuristics are proposed. The proposed heuristics arecompared with the existing ones in both efficiency and effectiveness. Theexperimental results show that the proposed heuristics can solve the consideredproblem effectively and efficiently.Two new composite heuristic RP and RT are designed for flow shopscheduling problem to minimize total flowtime. RP and RT are compared withthree best existing heuristics, RZ, WY and FL, on 1700 randomly generatedinstances. Experiment results show that RP and RT are very effective andefficient for flow shops with total flowtime minimization..