Abstract: The Permutation Assembly-line Scheduling Problem(PASP) is a kind of typical production scheduling problem,which has the property of NP-Hard and is the key of Computer Integrated Manufacturing System(CIMS). This problem can be described as follows:N jobs are proceeded in M machines; each job requires M working procedures, of which each procedure requires different machine; they go through the machines in the same order while the processing sequence are also the same in each machines. The main goal for the problem is to find out the optimal processing sequence of N jobs in each machine to minimize the makespan. Genetic algorithm is one kind of heuristic algorithms used to solve permutation Assembly-line scheduling problem (PASP). However, the offspring is difficult to have various genes in good solutions because of the evolution of its selection and crossover mechanism and then leads to local optimum. This paper aims to propose an improved genetic algorithm based on block mining with recombination for solving PASP, in which association rule is used to extract various good genes and increase the gene diversity. These genes are also used to generate various block for artificial chromosome combination. The generated blocks can not only improves the opportunities of finding optimal solutions but also enhance the efficiency of convergence. The proposed algorithm is validated and compared with other five algorithms by numerical experiments, namely Taillard in OR-Library. To compare with other algorithms, the solutions of proposed algorithm are closest to the optimal solution. The results show that proposed algorithm can have not only high the convergence speed but also better solution quality by increasing the solutions diversity.

Key words: combination optimization, assembly-line scheduling, association rules, improved genetic algorithm, artificial solution