【作者】 陈琳；

【导师】 李冬妮；

【作者基本信息】 北京理工大学 ， 计算机科学与技术， 2016， 硕士

【摘要】 当前单元制造系统内存在工件在单元间转移的情况,由此带来跨单元调度问题。由于零件需要频繁地跨单元转移,而小车的运输能力有限,如何协调生产和运输成为制约此类问题的关键。因此,本文考虑了运输能力受限的跨单元调度问题,基于相关领域研究现状的调研,分析了运输能力受限的跨单元调度问题的复杂性和重要性。同时,群智能算法因其灵活性、健壮性等特点,近年来已经受到研究人员的普遍关注;深入调研发现,人工蜂群算法作为群智能算法的重要一员,在解决车间调度问题上,已经发挥了重要作用。因此本文拟采用人工蜂群算法解决运输能力受限的跨单元调度问题。首先,通过问题假设、符号定义、目标函数和约束条件,详细描述了运输受限的跨单元调度问题,并针对问题特点建立了数学模型。其次,针对运输能力受限的跨单元调度问题,提出了一种基于衰老机制的人工蜂群算法。该算法采用人工蜂群算法的框架,将进化过程分为雇佣蜂、观察蜂和侦查蜂三个阶段:在雇佣蜂阶段,对当前食物源进行邻域搜索;在观察蜂阶段,对雇佣蜂分享的食物源信息使用二元锦标赛选择算法选择其中一个食物源作为搜索目标,并采用基于精英群体的衰老机制,引导群体的搜索方向,避免算法陷入局部最优;在侦查蜂阶段,随机搜索新的食物源。此外,在生成调度解过程中,根据工件的运输代价创建每个候选目的单元的局部组批,同时在考虑小车容量的前提下采用一种启发式方法决策运输路径,创建组批。最后,针对本文提出的基于衰老机制的人工蜂群算法,进行参数实验以及多组对比实验。对比实验表明,相比经典的人工蜂群算法,本文提出的算法在优化性能、收敛速度以及稳定性方面均得到明显改善;另一方面,与其它跨单元调度方法的比较结果,也充分验证了算法在寻优能力上的优越性。更多还原

【Abstract】 The existence of intercell transfers has made the idea of creating independent cells impossible, intercell scheduling therefore comes into being. Owing to the limited capacity constraint, it is essential to coordinate between part scheduling and transportation among cells. In this paper, an intercell scheduling problem with a limited capacity constraint is considered. The complexity of the addressed problem is analyzed and it is worth an effort to study. Swarm intelligent algorithms are known to researchers for their robustness, flexibility and good labor division. As one of the swarm intelligent algorithms, artificial bee colony(ABC) algorithm plays an important role in part scheduling problems. An ABC with an aging leader in the elite group approach is proposed.Firstly, the intercell scheduling with limited transportation capacity is described and mathematically formulated given the constraints in practice.Secondly, an ABC with an aging leader in the elite group and transportation strategy(ALTSABC) approach is proposed. The colony of artificial bees is composed of employed bees, onlooker bees and scout bees. The basic ABC algorithm searches food sources iteratively through the following three phases. In the first phase, employed bee searches food sources in the neighborhood of the current position. In the second phase, a scout bee evaluates the information provided by employed bees. A food source is selected for further exploitation based on a binary tournament selection method. An aging mechanism namely aging leader in the elite group is used to guide the whole colony, so that the algorithm will not be trapped in local optima. In the third phase, a scout bee generates a new food source randomly once a food source is abandoned by an employed bee. When constructing solutions, a transportation strategy is designed. Each part is assigned a cost based on which a partial batch is formed on the vehicle without breaking the capacity constraint. Then, a heuristic is employed to determine the sequence of visiting different destination cells.Finally, several comparison experiments are conducted to evaluate the effectiveness of ALEGABC. The result shows that ALEGABC is better than the basic ABC algorithm in solution quality and speed of convergence. The comparison with other scheduling approaches again verifies the superiority of ALEGABC.更多还原