摘要：针对带一台搬运机器人的job—shop调度问题，提出了一种并行禁忌搜索算法，目标是最小化最大完工时间。首先，充分利用问题的特点，构造2个启发式的初始排序。然后，利用这2个初始排序，使用禁忌搜索算法并行的搜索。在禁忌搜索算法的领域部分，先建立析取图模型，然后查找关键路径，再查找关键路径上的机床块和机器人块，在块上采取移动或交换的策略来建立领域。实验结果表明算法是有效的。

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

单位：广东工业大学机电工程学院广东省计算机集成制造重点实验室 广东广州510006