Research On Distributed Flow-shop Scheduling Problem And Its Algorithms

With the development of economic globalization,the transnational and trans-regional flow of production factors such as goods,technology,information and services is becoming more and more frequent,and the competition between enterprises is becoming more and more fierce.Economic globalization has promoted the international division of labor and the development of the world market,and realized the optimal allocation of global resources and the deep integration of global interests.Efficient production mode is an effective means for enterprises to improve production efficiency and maintain competitiveness,and multi-store cooperative production mode is becoming more and more popular.Since distributed manufacturing system is beneficial to improve product quality,production efficiency,reduce production cost and manage risk in real life manufacturing industry,distributed scheduling problem has been paid more and more attention.Nowadays,environmental problems are becoming more and more serious,and manufacturing enterprises have to seek an effective way to save energy and reduce energy consumption without increasing equipment investment costs.An increasing number of researchers have realized that scheduling can balance these two seemingly conflicting issues and provide efficient schemes for energyefficient manufacturing processes.However,energy consumption indicators and economic indicators often have to be considered together,and the process is an NP-hard problem,which is very difficult to solve.Green and energy-saving distributed production scheduling problem is the inevitable trend of international production under the background of globalization.The theoretical research and algorithm design of green and energy-saving distributed production scheduling problem have very important academic research value and engineering application significance.The iterative greed algorithm(IGA)is a simple and effective intelligent optimization algorithm for solving scheduling problems.The IGA has the characteristics of the simple structure,few parameters,and strong searchability.Its unique destruction and reorganization mechanism makes the IGA jump out of the local optimum and more likely to get the optimal solution.The whale optimization algorithm(WOA)is a swarm intelligence optimization algorithm that simulates the predatory behavior of humpback whales in the ocean.Due to its unique learning mechanism and efficient global search ability,the WOA has attracted much attention.Combined with the constraints and objectives faced in the actual production,the flow shop scheduling problem and its extension are deeply studied.The main research contents and work of this paper are as follows:(1)For the distributed assembly no-wait flow-shop scheduling problem(DANWFSP),a population-based iterative greed algorithm(PBIGA)is proposed to address the problem.According to the problem characteristics and problem knowledge of DANWFSP,a population initialization method based on the famous NEH algorithm and FRB2 algorithm is proposed to ensure the diversity of the population on the premise of obtaining a highquality population.In order to reduce the computing time and improve the efficiency of the algorithm,an accelerated algorithm NR3 a is proposed.Five neighborhood search operations are proposed and four different frameworks are designed to combine the five neighborhood search methods.Simulation results show that the proposed VND exploration method has the best performance.According to the characteristics of the distributed assembly plant,a destruction and construction method based on the product and jobs is designed to make the algorithm escape from the local optimum.A selection mechanism is proposed to select specific individuals for destructive recombination and local search.An acceptance criterion is proposed to decide which offspring individuals will be accepted by the population.The simulation results based on 810 large-scale benchmark instances show that the performance of the proposed algorithm is better than that of the current seven state-of-the-art algorithms,which proves that the proposed PBIGA is an effective and stable algorithm for solving DANWFSP.(2)For the energy-efficient distributed assembly no-wait flow-shop scheduling problem(EEDANWFSP),an improved iterative greedy(IIG)algorithm is proposed to solve the problem.According to the characteristics of EEDANWFSP and the problem of product allocation,the allocation method of resource balanced allocation is used to allocate products to factories in a balanced way.The individual initialization method is proposed based on the well-known NEH algorithm.A destruction-construction method is proposed to destroy the sequence of products in the factory.Seven neighborhood search operations are proposed and a random selection method is used to select the local search in the iterative process.For the processing of the jobs under energy constraints,the energy-saving operation is proposed to reduce the energy consumption index.A multi-objective-based acceptance criterion is proposed to receive the optimal Pareto solution set.The simulation results based on 810large-scale benchmark datasets show that the proposed IIG can effectively solve the EEDANWFSP problem,and it is superior to the current five advanced and effective algorithms.(3)Based on Q-learning,a learning iterative greedy(LIG)algorithm is proposed to address EEDANWFSP more efficiently.In terms of algorithm design,a new solution expression is proposed.In the initialization method,a well-known heuristic method FRB2 and a Largest Processing Time(LPT)ordering rule are used to construct the job sequence in the product and the product sequence in the factory according to the problem characteristics of EEDANWFSP.The external archiving mechanism is used to store the non-optimal but potential historical solutions,which provides more information about the search direction and can also improve the diversity of solutions.According to the characteristics of EEDANWFSP,the destruction-construction method is proposed and a Q-learning-based destruction size selection mechanism is proposed.Six kinds of operators are proposed and a Q-learning-based operator selection mechanism is proposed.Accelerated operations targeting critical paths in critical plants are proposed.Energy-saving operations are proposed for the characteristics of the no-wait flow shop scheduling problem.The parameters of the algorithm are calibrated in the experimental phase.The effectiveness of the proposed strategy is proved by the strategy effectiveness analysis.Comparative and statistical experiments show that the proposed algorithm ILG is very effective in solving EEDANWFSP.(4)For the distributed blocking flow-shop sequence-dependent scheduling problem(DBFSDSP),a cooperative whale optimization algorithm(CWOA)is presented to address the problem.The optimization objective is to minimize the makespan,total tardiness,and total energy consumption.The algorithm first designs a heuristic method for population initialization.In the stage of searching for prey,the operators of inserting neighborhood and exchanging are proposed to search the solution space to obtain better solutions.In the Encircling prey phase,a critical path-based acceleration operation is used to improve the quality of the solution to reduce the maximum completion time and total tardiness.In the phase of bubble-net attacking prey,a critical path-based deceleration operation is used to reduce the total energy consumption.Finally,three acceptance criteria for multi-objective optimization are proposed to improve the diversity of the population.Simulation results show that the proposed CWOA significantly outperforms three state-of-the-art algorithms.