Research On Algorithms For The Distributed Permutation Flowshop Scheduling Problem

As an important combinational optimization problem, flowshop scheduling prob-lem and its algorithms have attracted much attention in computer science and OR com-munities, and those algorithms play an important role in industrial areas. However, many modern companies have changed their manufacturing environments, where tradi-tional single-factory environment is replaced by multi-factory environment and more factories are built to set up the environment. Traditional flowshop scheduling problem concerns single factory, and it cannot deal with distributed multi-factory environment, so the Distributed Permutation Flowshop Scheduling Problem (DPFSP) was presented and studying this problem becomes a new hotspot.Though kinds of optimization algorithms have been studied to solve traditional flowshop scheduling problems with single factory, it is in the early stage of studies on algorithms for solving DPFSPs. This paper concentrates on the flowshop scheduling problems with multi-factories, studies the model of this problem and its scheduling al-gorithms.In the aspect of theory,this paper studies Distributed Permutation Flowshop Scheduling Problem with Identical factories (DPFSP-I). Then with the consideration that processing times of jobs in two factories differs from each other, this paper defines a new problem called Distributed Permutation Flowshop Scheduling Problem with Dis-tinct factories (DPFSP-D) and its mathematic model. Furthermore, it discusses lower and upper bounds of solutions by analyzing relationship between makespan of DPFSP-I and traditional flowshop scheduling problems. Additionally, solution representation and solution space are studied in this paper, as well as acceleration methods to compute makespan.In the aspect of algorithm, this paper proposes several algorithms for DPFSPs to minimize makespan, including:(1) Constructive heuristics and variable neighbourhood descent algorithms for DPFSP-I. Different from the existing methods that insert one job each time, it considers several jobs at each time and proposes a job dispatching rule based on this strategy. The results of experiments show that constructive heuristics and variable neighbourhood descent algorithms can benefit from the proposed dispatching rule and thus improve their performance greatly.(2) Genetic algorithms for DPFSP-I. There is no effective intelligent optimization algorithm proposed for this problem, so this paper presents a genetic algorithm, as well as its operators according to the repre-sentation of scheduling solutions, then an efficient local search method is also proposed and is combined into the genetic algorithm. In addition, in order to obtain better solu-tions, this paper improves the genetic algorithm by introducing a new knowledge-based infection operator, through which the solution quality is improved. Intensive experi-ments have performed and the results update most best-known solutions of instances from DPFSP benchmark.(3) Tabu search algorithms for DPFSP-I and DPFSP-D. This paper proposes a tabu search algorithm for DPFSP-I to improve efficiency, where a job exchange rule that operates on job sequences and a tabu strategy are introduced. This strategy uses the exchange rule to escape local optima. Besides, this paper designs a new acceleration method to compute makespan of DPFSP-D and then proposed a tabu search algorithm for DPFSP-D. The computational results indicate the effectiveness of those algorithms.(4) A cooperative algorithm based on multi-agent systems. This paper proposes a cooperation algorithm for DPFSP-D and studies a ring-based mes-sage-passing strategy to ensure security of local information.