关键词: 双向阻塞车间调度,单线列车调度,离散粒子群优化算法

Abstract: According to the characteristics of the single-track lines train scheduling problem,a bi-directional blocking job shop scheduling (BDBJSS) model was built to describe its solution space and the discrete particle swarm optimization (DPSO) algorithm was proposed to solve it with the objects of makespan minimization．Based on the BDBJSS mo-del,permutation based encoding schemes were designed in DPSO algorithm for arranging the train sequences,and the random strategy and processing time shortest first strategy were put forward for selecting the running tracks.Also,the train conflict detection and resolution methods were proposed in the algorithm,which can schedule trains according to the steps of "scheduling-detecting conflicts-resolving conflicts".At last,DPSO algorithm was used for global optimization to get the best solution．Experiments results show that the model and algorithm can solve single-track lines train scheduling problem effectively.

Key words: Bi-directional blocking job shop scheduling,Single-track lines scheduling,Discrete particle swarm optimization algorithm