一类含同工件流水线调度问题的优化研究

Optimization Study on a Class of Flow Shop Scheduling with Non-unique Jobs

流水线调度问题是具有很强工程背景的典型NP完全问题,当其含有同工件时,批量和排序的相关性使得问题的求解更为复杂。文章有机结合模拟退火的概率突跳性和遗传算法的并行搜索结构,提出了处理一类含同工件流水线调度问题的混合优化策略。算法不仅能够动态缩小搜索空间以提高搜索效率,而且在保优策略的基础上利用重升温技术来增强克服陷入局部极小的能力,其有效性和快速性通过仿真得到了验证。

Flow shop scheduling with strong engineering background is proved a typical NP-complete problem,which is very hard to solve because of the correlation of lot-size and sequence when non-unique jobs exist.This paper reasonably combines the probabilistic jumping property of simulated annealing with the parallel searching structure of genetic algorithm to propose a hybrid optimization strategy dealing with a class of flow shop scheduling problem with non-unique jobs.The proposed algorithm is able not only to improve efficiency by dynamically reducing the search space,but also enhance the ability to avoid being trapped in local minimum by introducing reraise temperature technique based on elitism.Simulation results demonstrate the effectiveness and the rapidness of the strategy.