Heuristics For Flexible Flow Shop Scheduling Problem With Group Constraint

In discrete manufacturing industries, flexible flow shop scheduling problems (FFs) are common. It is theoretical and practical to study it. Therefore, more and more researchers are attracted to study it. According to the location of group constraint, this paper divides this problem into three sub-categories:flexible flow shop problem with head, mid and tail group constraint, respectively. Obviously, this problem is an extension of the classical flexible flow shop scheduling problem, and it is a hybrid problem combined FFs problem and group problem. Since the classical FFs problem is NP-hard, flexible flow shop problem is at least NP-hard.For NP-hard problem, whose optimal solution makes combinatorial explosion of searching space, it can not obtain the optimal solution in the polynomial time. Therefore, the classical exact methods, i.e. linear programming, branch and bound and so on, aren’t meaningful for large scale problems. However, heuristics are effective for this sort of problem. So this paper study FFs problem with group constraint and obtains the main research results as follows:1. For the two-stage flexible flow shop scheduling problem with head group constraint, we built its mathematical model and the objective is to minimize makespan; through analyzing the structure of this problem, a heuristic algorithm called H’is proposed; then, the time complexity and worst-case analyze of H’ are given, respectively; to test the efficiency of H’, sets of examples are designed and compare H’with three classical developed heuristics, the results indicate that the performance of algorithm H’is more superior than other three heuristics with respect to the two-stage flexible flow shop scheduling problem with head group constraint; finally, a heuristic algorithm based on H’ called MH’is proposed and apply MH’to the multi-stage flexible flow shop with head group constraint.2. For the two-stage flexible flow shop scheduling problem with tail group constraint, we build its mathematical model and the objective is to minimize the total tardiness of jobs; through analyzing the structure of this problem, an advantage scheduling rule is proposed; According to this advantage scheduling rule, a new heuristic method called EL algorithm is proposed; then, the time complexity and worst-case analyze of EL are given, respectively; To test the performance of EL algorithm, a computational experiment is designed and the simulation results indicate that EL algorithm outperforms the other twelve dispatching rules with respect to the two-stage flexible flow shop scheduling problem with tail group constraint; finally, a heuristic algorithm based on EL called MEL is proposed and apply MEL to the multi-stage flexible flow shop with tail group constraint.3. For the three-stage flexible flow shop scheduling problem with mid group constraint, we built its mathematical model and the objective is to minimize makespan; through analyzing the structure of this problem,10heuristics are proposed and their time complexity are proposed; by analyzing this problem,4lower bounds are proposed; with analyzing these10heuristics, the worst-case of nine of them are proved. In order to validate and evaluate the10heuristic algorithms, a simulation method is designed, and then the heuristic algorithms are adopted in the scheduling simulation. Simulation results indicate the effectiveness of the10heuristic algorithms with different configurations and SP.JH-MJ outperforms the others with respect to the three-stage flexible flow shop scheduling problem with mid group constraint; finally, a heuristic algorithm based on SP.JH-MJ called MJL is proposed and apply MJL to the multi-stage flexible flow shop with mid group constraint.4. System-simulation software of flexible flow shop scheduling problem with group constraint is developed. It is convenient to generate different instances with it. By using this software, obtain the simulation results under different configurations with different algorithms and analyze the performance of these algorithms.Finally, based on the theoretical research results above and combined with the characteristics of the cooperative enterprises, scheduling system is designed and developed, and it is successfully applied in the enterprises.