求解混合多处理机任务作业车间调度的改进粒子群算法

Improved Particle Swarm Optimization Algorithm for Solving Hybrid Job-shop Scheduling with Multiprocessor Task

针对车间生产制造中,工件的一道加工工序需要不止一台处理机(工人、设备等)同时加工处理的情景,建立了混合多处理机任务作业车间调度模型,并针对粒子群算法容易陷入局部最优提出一套改进粒子群算法用于求解该问题.其中,对粒子群算法的改进工作包括:提出编码机制和解码机制、设计迭代机制和为了尽量避免早熟而引进的变异机制.利用提出的改进粒子群算法对JSP问题经典算例进行求解,以验证该算法的有效性与稳定性,之后对混合多处理机任务作业车间调度问题的算例进行仿真分析,实验结果表明该算法有效提高了处理机的利用率,缩短了最大完工时间.

A hybrid job-shop scheduling with multiprocessor task（HJSMT）model was constructed for scheduling the job process in which each job is processed on a number of processors simultaneously at each stage.And an improved particle swarm optimization algorithm（IPSO）was proposed to solve the new problem.Coding and decoding strategies were introduced for establishing the mapping between particles and solutions.A kind of iterating strategy was designed for particles updating in the feasible solution domain and in order to improve the ability for particles to get out of local optimal solution domain,a mutation strategy was designed.The JSP benchmark problems were used to verify the effectiveness and stability of the proposed IPSO,and then IPSO was also used to solve the HJSMT instance.Simulation results show that the algorithm effectively improves the utilization of processors and shortens the makespan.