CAJ | 학술논문

自动化制造单元最小完工时间调度问题属于NP-hard难题.目前尚缺乏有效的调度方法.为此,提出基于遗传和禁忌搜索的混合启发式算法,用以搜索一组最满意的机器人搬运作业排序.以遗传算法为基本结构,在初始种群产牛和交叉、变异操作中引入禁忌搜索技术,以提高优化质量.基于搬运作业规则的初始种群构造算法和两阶段交叉、变异算子克服了传统算子对可行搬运作业排序的破坏,而邻域移动算子则保证了禁忌搜索的多样性和集中性.最后,随机实验结果验证了算法的有效性.
자동화제조단원최소완공시간조도문제속우NP-hard난제.목전상결핍유효적조도방법.위차,제출기우유전화금기수색적혼합계발식산법,용이수색일조최만의적궤기인반운작업배서.이유전산법위기본결구,재초시충군산우화교차、변이조작중인입금기수색기술,이제고우화질량.기우반운작업규칙적초시충군구조산법화량계단교차、변이산자극복료전통산자대가행반운작업배서적파배,이린역이동산자칙보증료금기수색적다양성화집중성.최후,수궤실험결과험증료산법적유효성.
There was no effective scheduling methods for the makespan scheduling problem in robotic cell, which was a NP-hard problem. A hybrid heuristic algorithm based on gentic algorithm and tabu search was proposed to search the optimal robot moving sequence for this problem. This algorithm borrowed basic structures of the genetic algorithm,and tabu search was introduced after the generation of initial population, crossover and mutation operations to improve the qualities of the solutions. Besides, a constructive heuristic method and two-phase crossover and mutation operations were respectively designed to overcome the faults of the traditional operations. A move opcration was proposed to reach the neighborhood in the tabu search to guarantee the diversification and intensification. Finally, computation results based on the randomly generated instances indicated the effectiveness of this algorithm.