带搬运机器人的job-shop问题的并行禁忌搜索算法  

Parallel Tabu Search Scheduling Algorithm for Job-Shop with Transport Robot

作　　者：何之洲[1] 杨煜俊[1] 陈新度[1] 

机构地区：[1]广东工业大学机电工程学院广东省计算机集成制造重点实验室,广东广州510006

出　　处：《工业工程》2013年第4期122-125,132,共5页Industrial Engineering Journal

基　　金：国家自然科学基金资助项目(51105082);广东省战略性新兴产业核心技术攻关资助项目(2011A091101003);国家科技支撑计划资助项目(2012BAF12B10)

摘　　要：针对带一台搬运机器人的job-shop调度问题,提出了一种并行禁忌搜索算法,目标是最小化最大完工时间。首先,充分利用问题的特点,构造2个启发式的初始排序。然后,利用这2个初始排序,使用禁忌搜索算法并行的搜索。在禁忌搜索算法的领域部分,先建立析取图模型,然后查找关键路径,再查找关键路径上的机床块和机器人块,在块上采取移动或交换的策略来建立领域。实验结果表明算法是有效的。In this paper, scheduling problem of job-shop with a single transport robot is addressed. A parallel tabu search algorithm is presented to minimize the makespan. First, with the characteristic of the problem, two schedules are created as the initial solutions by using a heuristic. Then, the tabu search algorithm is used for parallel search. By this algorithm, a disjunctive graph model is established such that the critical path and the block are found. Then, a strategy of moving or changing on block is used for the neighborhood in the algorithm. Experimental results show that the algorithm is effective.

关 键 词：禁忌搜索 job—shop 搬运机器人 

分 类 号：O224[理学—运筹学与控制论]