优化差异工件单机批调度问题的混合微粒群算法

A Hybrid PSO Approach for Optimal Scheduling Single Batch-processing Machine with Different Workpieces

研究了单机环境下具有动态到达时间的差异工件批调度问题,设计了微粒群算法对此类问题进行求解,并结合动态规划进行优化。首先给出了问题的微粒表达形式,并根据问题的离散优化特性对微粒状态的更新方法进行了改进;然后将微粒群算法和动态规划算法进行有效结合,改善近似解的质量。在实验中,对各类不同规模的算例均进行了仿真,验证了该算法的有效性。

This paper explores minimizing makespan on a single batch processing machine where workpieces have dynamic release time and different sizes. The problem is proven to be NP-hard and hence a hybrid ant Particle Swarm Optimization （PSO） method is proposed by combining it with dynamic programming （DP）. The particle is redesigned for the problem and the updating of particles is modified to match the discrete optimization problem and DP determines the batching. Computational results show that the Hybrid PSO approach performs considerably well in all instances.