求解调度问题的粒子群算法编码方法研究

利用粒子群算法求解调度问题的关键是建立有效的粒子编码结构。介绍了作业车间、流水车间和并行机调度等3类典型调度问题的特点，阐述了求解调度问题的粒子群算法结构，指出设计粒子群算法编码方法需要考虑的3个关键问题。提出3种求解不同调度问题的粒子群算法编码方法，并从生成调度解的可行性和有效性、粒子群计算模型的适用性和解码过程的复杂性等几个方面对粒子编码方法进行分析。以作业车间调度问题为例，验证了所提粒子编码方法的有效性。

Encoding of particle swarm optimization algorithm for scheduling problem

The key in using particle swarm algorithm to optimize the scheduling problem is to find an effective and feasible encoding structure. After the particle swarm optimization algorithm structure for the scheduling problem is described, three important points of the particle swarm optimization encoding are presented. Having analyzed the characteristics of three scheduling problems comprising of job shop scheduling, flow shop scheduling and parallel machine scheduling, this paper introduces the encoding and decoding methods for the three scheduling problems, which are further studied as viewed from several factors including the feasibility and validity of the schedule solution, the applicability of the particle swarm optimization model, and the complexity of decoding. The proposed encoding and decoding methods are proved to be feasible and effective when the job shop scheduling problem is taken as an example.