Research On Meta-heuristic Algorithms For Solving Multi-objective Flow Shop Scheduling Problem

For a long time,the production scheduling problem has been not only the emphasis of production managers,but also the hotspot in research of combinatorial optimization.The multi-objective flow shop scheduling problem is one of the most thoroughly studied machine scheduling problems with a number of applications,which schedules a set of jobs on a set of machines according to a specific order.At the same time,it usually needs to meet a number of different constraints.Reasonable processing procedure and scheduling strategy can effectively reduce the production cost of enterprises,capital loss,and administrative overhead.Therefore,efficiently solving the multi-objective flow shop scheduling problem is of great importance to gain theoretical guidance and practical value,which can improve the production efficiency,allocate manufacturing resources rationally,and reduce the cost of production and management for promoting the comprehensive competitive power of enterprises.As a classical NP-hard combinatorial optimization problem,no exact algorithm is expected to solve the multi-objective flow shop scheduling problems in a polynomial time.Therefore,many heuristic and meta-heuristic algorithms were proposed to deal with this problem,including simulated annealing,tabu search,explorative local search,genetic algorithms,memetic algorithms,ant colony optimization,etc.Based on good performance of hypervolume method on a class of combinatorial optimization problems,this thesis employs a hypervolume contribution indicator as the selection mechanism during an iterated local search procedure for solving the multi-objective flow shop scheduling problem.Taking into full account the characteristics of flow shop scheduling problems,in this thesis,through integrating the path relinking techniques and the perturbation strategy into the framework of hypervolume indicator based optimization algorithm to further improve the quality of Pareto approximation set,hypervolume-based multi-objective path relinking algorithm and the multi-objective perturbation local search algorithm are proposed to solve bi-objective flow shop scheduling problem which aims to minimize the total completion time and the total tardiness.On the other hand,based on the research status of multi-objective flow shop scheduling problems which have more than two objectives,this thesis presents a hypervolume-based multi-objective algorithm for the explorative research on three-and four-objective flow shop scheduling problem.Experimental results on standard test examples indicate that proposed algorithms in this thesis are very effective in comparison with the algorithms based on the binary indicators with good stability.