半导体生产车间智能AGV路径规划与调度

李昆鹏，刘腾博+，阮炎秋

(1.华中科技大学 管理学院，湖北 武汉 430074；2.新加坡科技与设计大学 工程系统与设计，新加坡 487372)

1 问题的描述

近年来，在人工智能、物联网、5G等创新技术的推动下，半导体行业的应用场景不断扩展，同时半导体芯片作为信息技术产业的基石，对信息安全、国民经济起着至关重要的作用，已成为各国竞相角逐的“国之重器”。2015年在国务院印发的《中国制造2025》中将集成电路放在发展新一代信息技术产业的首位，以推动半导体国产化进程。从2015年至今，中国一直稳居全球最大半导体消费市场，市场需求规模占全球41%，而自给率却只能达到12%，这严重制约了我国信息产业的发展。半导体芯片制造是迄今为止最复杂的工艺过程，以14 nm晶圆工艺为例，全部流程需要1 100个步骤，生产线技术工艺复杂，涉及加工设备数量及类型繁多。随着电子通信、计算机、网络技术三大领域的需求不断增加，传统生产车间的人工作业模式显然已难以满足半导体的市场需求，松下、西门子等国际知名半导体企业纷纷尝试将智能机器人自动导引小车(Automated Guided Vehicle, AGV)应用于半导体生产车间，以实现柔性自动化生产线。目前，我国半导体制造业尚处于起步阶段，进口依赖问题依然严峻，在制造精度和自动化程度上与国际水平仍存在较大差距，而AGV凭借高灵活性、高稳定性，已成为半导体行业实现自动化生产的关键设备之一。然而，如何设计更适用于半导体生产车间的AGV调度算法，以实现更快更精准的生产任务运输作业，是当前国内半导体制造业向智能制造转型面临的巨大挑战。

目前，已有少数企业尝试利用AGV特性升级现有制造执行系统(Manufacturing Execution System, MES)，在应用MES的生产车间内，电子货架与加工机台分别位于两侧，货架用来存放半导体工件的半成品和成品，AGV来往于货架与机台之间，完成半导体运送任务，主要工作流程如图1所示。首先根据客户需求制定半导体工件生产计划，然后将机台与货架间的工件运送任务分配至AGV，最后规划AGV在机台与货架间的行走路径，以实现半导体生产过程的自动化运输作业。在半导体生产车间中，有若干加工机台和电子货架，根据半导体的加工工序要求，工件需在不同时间多次访问同一机台，具有明显的可重入性。AGV的主要任务是将暂存在货架上的工件运送至机台加工，并将已完成加工的工件从机台运送至货架暂存。若机台生产计划时间开始，而工件未能被AGV及时运送到达机台，或机台加工完成，而工件未能被及时运走，则会导致机台等待闲置及生产计划的延后。在半导体车间中，设备购置费用高，生产调度的一个重要目标是机台闲置率最小。因此，为了保证各道工序顺畅衔接以及机台工作效率，AGV调度的总体目标为：基于生产计划决策AGV运送任务的顺序及运送路线，以最小化AGV完成运送任务的总时间。该问题在设计AGV调度方案时不仅要考虑每道工序的计划加工和完工时间，还要从全局对多台AGV进行路径规划以避免碰撞发生，是一个十分复杂的作业车间调度问题与AGV路径规划问题。

基于MES工作流程，本文所研究的半导体生产车间智能AGV路径规划与调度问题可提炼为半导体车间生产调度问题和AGV路径规划问题。关于半导体车间生产调度问题的研究，KUMAR[1]最早提出了半导体生产线属于可重入生产系统，是不同于Job-shop和Flow-Shop系统调度的第三类调度问题；UZSOY[2]首先证明半导体单批处理机调度问题为强NP-hard。大多数文献将最小化最大完工时间作为优化目标[3-5]，部分文献考虑了加权总完工时间[6]、平均延误时间[7]、总延误时间[8]、平均等待时间[9]等目标。在求解方法上，KUMAR等[10]设计了启发式规则应用于半导体生产过程实时调度；BAEZ等[11]设计了一种基于人工神经网络技术的多目标遗传算法；马慧民等[12]和郭乘涛等[13]分别提出了双层粒子群算法和混合蚁群算法。极少学者采用精确算法求解，JIANG等[6]和CHOI等[14]分别提出了基于代理次梯度的拉格朗日松弛算法和分支定界算法。以上研究均仅对生产环节进行优化，尚未将AGV行驶路径考虑在内，无法应用于多AGV协同工作的半导体生产车间。

综上所述：①国内外学者主要研究了采用传统流水线生产的调度优化问题，由于半导体制造工艺流程具有可重入性高、不确定性大、批处理加工及大规模生产等显著区别于其他制造业的特点，而已有文献中的调度算法在可重入式生产流水线的适用性不强；②AGV路径规划方面，多数文献在已知障碍物的静态环境下设计AGV避撞策略，无法适用于采用多台AGV协同工作的智能化半导体生产车间；③由于采用AGV实现自动化生产已成为发展趋势，而在半导体车间对AGV进行路径规划的文献较少，且很少有文献涉及多种AGV避撞方式。因此，如何在动态环境下将工件生产任务分配、AGV路径规划及碰撞避免结合起来，设计多种避撞措施以灵活变换路径，形成一套完整的AGV自动化物料运输系统解决方案，将是本文研究的重点。

本文结合半导体生产线的工艺流程，在自动化物料运输系统下研究AGV路径规划与调度问题，提出了两阶段优化算法，如图2所示。第1阶段生成单AGV初始可行路径，分别采用基于数学模型和基于时间优先级的任务分配方法，将货架与机台之间的半导体工件运送任务分配至AGV，并根据一定的行驶规则生成每台AGV的初始路径;第2阶段考虑碰撞避免获得多AGV全局无碰路径，设计碰撞检测及避免算法检测初始路径中AGV可能发生冲突的节点，并采取相应避撞策略对AGV路径进行动态调整，最终实现所有AGV能够高效、无碰撞地完成半导体生产车间的物料运输任务。最后通过算例实验证明本文提出的两阶段算法能够调度AGV在具有4个货架和4个机台的半导体车间中完成480个工件的运送任务，在求解效果和时间上均有较好的表现。相较于已有研究，本文不仅考虑了AGV任务分配方法，还提出了AGV在动态环境中的避撞策略，并通过灵敏度分析对AGV配置数量给出建议。研究成果丰富了AGV在不同场景中的应用，能够为半导体生产车间采用AGV实现自动化物料运输系统提供参考。

2 初始路径生成

AGV初始路径生成主要包括两个步骤：首先，将货架与机台之间的半导体工件运送任务分配至AGV，得到每台AGV的运送任务序列，然后根据一定的行驶规则生成每台AGV的初始路径。本文分别在两种任务分配方法下得到每台AGV的运送任务序列：①以工件加工总完成时间最短为目标建立数学模型进行精确求解；②考虑生产计划中工件计划时间的紧急程度设计启发式算法进行高效求解。

2.1 基于数学模型的AGV任务分配方法

2.1.1 问题描述及假设

AGV路径规划与调度问题可描述如下：在采用AGV的半导体生产车间中，每个货架有多个储位且每个储位仅暂存一种半导体工件。当AGV运送加工工件时，先到暂存该工件的货架取货，再将其运送至机台加工，若AGV实际到达机台的时间小于计划加工时间，则在机台处等待；当AGV运送完工工件时，先到加工该工件的机台取货，若AGV实际到达时间小于计划完工时间，则在机台处等待至计划完工时间，再将其运送至货架暂存。在MES的生产计划中，对于工件的每道工序均有计划加工时间和计划完工时间，根据计划时间下达指令至AGV完成工件加工上机和完工上架的运送任务。本文以AGV完成所有工件运送任务的时间最短为目标建立数学模型，在满足生产计划的时间约束下，将工件运送任务分配至AGV，并对AGV执行运送任务的顺序进行决策。

为了方便建模，考虑以下假设：①AGV电量充足；②加工机台无开工准备时间；③每台AGV每次最多运送一种工件；④AGV在货架或机台前的位置进行操作；⑤所有AGV同质且每秒匀速行驶1个单元格；⑥将AGV行驶区域抽象为矩形网格，AGV沿网格行驶，故其行走距离为折线距离。

2.1.2 模型建立

根据问题描述，参数及变量定义如表1所示。

表1 参数符号及定义

基于上述问题描述、假设条件及参数变量，构建如下数学模型：

(1)

s.t.

(2)

(3)

(4)

(5)

(6)

(7)

(8)

(9)

(10)

(11)

(12)

(13)

(14)

(15)

(16)

(17)

模型的决策为工件运送任务在AGV上的分配及每台AGV完成运送任务的先后顺序。目标函数(1)表示最小化用时最长的AGV运送任务时间；式(2)和式(3)表示AGV从停靠点出发完成任务后返回停靠点；式(4)和式(5)保证每个运送任务均被执行；式(6)为线路流平衡约束；式(7)为AGV与运送任务之间的服务关系；式(8)和式(9)为AGV完成加工上机运送任务i的结束时间不得早于其开始时间与运送时间之和，且不得早于计划加工时间；式(10)和式(11)为AGV执行完工上架运送任务i的开始时间不得早于该工件加工上机运送任务的结束时间与加工时间之和，且不得早于计划完工时间；式(12)表示若AGV先后执行运送任务i和j，则任务j的开始时间不早于AGV完成任务i后走折线路线到达任务j起点的时间；式(13)和式(14)为消除子循环约束；式(15)表示0-1变量；式(16)和式(17)表示整数变量。该问题可简化为任务分配问题(assignment problem)，为NP难题。

2.2 基于时间优先级的AGV任务分配算法

全球半导体行业已经进入成熟发展的存量竞争阶段，这对半导体的加工精度和生产能力提出了更高的要求，为了更好地利用AGV精准、快速的特点，从而进一步提高生产效率，本文以尽快完成半导体工件生产计划为目标，提出一种基于时间优先级的AGV任务分配算法，主要流程如图3所示。由MES制订的工件生产计划包括工件的暂存货架、加工顺序、每道工序的加工机台及计划加工时间和计划完工时间。首先根据工件的计划加工和完工时间对所有运送任务进行排序，即优先完成时间最紧急的任务，由此得到运送工件加工上机和完工上架的任务序列。然后按照AGV先完成先分配的原则依次安排AGV完成工件运送任务，并更新每台AGV的运送任务序列，直至所有运送工件加工上机和完工上架的任务均分配至AGV执行，最终得到每台AGV的运送任务序列。

2.3 AGV行驶规则及路径生成方法

本文对半导体生产车间进行栅格化处理并用编号表示位置节点，如图4所示，包括AGV停靠点、加工机台、电子货架以及一个3×3的AGV行驶区域，机台和货架前的栅格为AGV操作位。在半导体生产车间中，AGV没有任务时停靠在角落，当接收到工件加工上机任务时，AGV将其从所在货架取出并运送至机台；当接收到工件完工上架任务时，AGV将其从加工机台取出并运送至货架。AGV在停靠点、货架及机台之间行走，完成工件的运送任务，为了保证半导体生产车间各工序顺畅衔接，AGV按照“先横后纵”的行驶规则有序运行，以降低碰撞概率，从而高效完成运送任务。根据AGV执行每个运送任务的起点和终点，基于“先横后纵”的行驶规则，可知AGV执行每个运送任务时的初始路径，如图5所示。当任务起终点同在横向或纵向时，行驶路线为a/b/c/d；当任务起终点均不在同一横纵方向时，行驶路线为e/f/g/h。例如，如图4所示，若AGV当前运送任务为货架1上的工件需在机台3进行加工，则其行驶路径为4→5→6→9。AGV根据已确定的工件运送任务序列，在此规则下可得到每台AGV完成其所有运送任务的初始路径。

3 AGV碰撞检测及避免算法

3.1 算法设计

当多台AGV在停靠点、货架、机台之间行走执行工件的运送任务时，极有可能发生碰撞，为了解决AGV碰撞问题，以免造成死锁情况，确保多AGV系统安全顺畅地运行，本文设计碰撞检测及避免算法对AGV初始路径进行实时重调度，以保证在行走区域内不存在两台AGV同时占用相同位置。为了表示AGV位置和时间两个维度，本文基于栅格化车间建立二维预约表，采用数字编号表示AGV每时刻的行驶位置，如[1,1]、[2,4]、[3,5]表示AGV在1 s～3 s的行走路径为1→4→5。此外，采用重复编号表示AGV静止等待，如[3,8]、[4,8]、[5,8]表示AGV在3 s～5 s时段停留在编号为8的位置。

碰撞检测及避免算法流程如图6所示，主要步骤为：

(1)基于AGV初始路径建立初始二维预约表，考虑到工件加工所需时间大致相同，为了降低AGV集中到达机台前等待造成拥堵的概率，因此需要对AGV的相邻运送任务设置出发时间间隔，即在AGV路径中加入停留节点表示机台加工时间，以更新二维预约表。

(2)根据更新后的二维预约表计算AGV实际到达加工机台的时间。若AGV实际到达时间早于计划加工时间或计划完工时间，则加入停留节点，使AGV在机台处等待至计划时间再投放或取出工件，以此更新二维预约表。

(3)检查AGV预约表中是否存在与其他AGV同时刻同位置，若在相同时间同一位置被重复占用，则表示发生冲突，此时根据避撞策略采取相应调整措施，更新二维预约表并再次进行碰撞检测，直到该运送任务的所有路径不存在冲突。

(4)同理完成AGV所有运送任务的碰撞检测和调整。

3.2 避撞策略

在半导体生产车间环境中，多AGV系统出现冲突的情况复杂多样，但其本质都是时空重叠问题，即同一时间，两台AGV在同一位置相遇而发生碰撞，此时采取相应的调整措施。由生产计划表可知AGV执行当前运送任务的计划加工时间和计划完工时间，按时间的紧急程度确定AGV的优先级，即时间越靠前的运送任务AGV优先级越高。由于优先级低的AGV需要对优先级高的AGV进行避让，以尽快满足时间更紧急的加工任务，从优先级最高的AGV依次对每台AGV进行路径调整。由AGV的二维预约表可知每台AGV每时刻所在的位置，若检测到当前AGV初始路径中存在行驶栅格在某时刻已被其他优先级更高的AGV占用，则表示两台AGV将在该位置发生碰撞，此时优先级较低的AGV根据其任务起终点的位置关系进行路径变换，如图7所示，具体调整措施如下：

(1)任务起终点同在横向或纵向 在初始路径中AGV沿直线从任务起点行驶至终点，当检测到某位置发生碰撞时，根据AGV起终点位置关系变换路径。若AGV起终点同在横向上，采取a/b变换。若同在纵向上，采取c/d变换。以上4种变换AGV均多转向4次。

(2)任务起终点均不在同一横纵方向 根据初始路径中AGV按照“先横后纵”的折线路线从起始点行驶至终点，若AGV在沿横向行驶的过程中发生碰撞，采取e/f/g/h变换，即AGV在碰撞点前一栅格进行转向；若AGV在沿纵向行驶的过程中发生碰撞，采取E/F/G/H变换，即AGV在转向点前一栅格提前进行转向。以上4种变换AGV均多转向1次，但不会增加AGV行走时间。当转向变换后AGV行驶至终点的过程中再次发生碰撞，此时先采取E/F/G/H转向次数较少的变换方式，若仍无法避开碰撞，再根据AGV行驶方向及终点位置采取a/b变换以有效规避碰撞点。

(3)若AGV路径终点被其他优先级更高的AGV占用，此时优先级较低的AGV在其终点前一栅格静止等待，即延迟避撞策略，如A、B、C、D所示。

4 仿真实验及数据测试

4.1 小规模仿真实验

本节构建了一个大小为3×3的半导体生产车间，布局如图4所示。车间中设置2个电子货架用于暂存工件，3个机台用于加工工件，2台AGV初始状态均位于车间左下角且速度为每秒匀速行驶1个单元格。实验中运送任务算例根据半导体可重入性的特征随机生成。所有测试在Intel Core i7 2.8 GHz CPU, 8 GB RAM的计算机上运行，采用CPLEX作为模型求解器，启发式算法采用Python编码，在Python 3.7平台上实现。

为了比较基于数学模型的任务分配方法和基于时间优先级的任务分配算法在两个阶段的求解效果差异，分别采用两个方法求解并进行比较，结果如表2所示。在表2和以下阐述中，为便于表述，将这两种方法分别描述为：两阶段算法(数学模型)与两阶段算法(时间优先级)。展示结果为AGV完成所有工件运送任务的时间。其中：ItemNum表示运送任务数量；Period 1表示碰撞调整前的初始路径总时间，即第1阶段结果；Period 2表示经过碰撞调整后的最终路径总时间，即第2阶段结果；Gap1表示两种方式在碰撞调整前的运送时间差异度；Gap2表示两种方式经过碰撞调整后的运送时间差异度；Time表示求解所用时间(单位:s)。

表2 小规模实验结果

结果表明，对于第1阶段，两阶段算法(时间优先级)与两阶段算法(数学模型)的初始路径在个别算例上存在一定差异，但最大仅相差3.51%；对于第2阶段，两个方法得到的结果一致。这说明对于小规模算例，由于在生产计划中已考虑加工顺序，AGV只需按照生产计划的时间要求执行任务即可，实际完成时间与AGV在执行任务时发生的碰撞相关，与任务执行顺序关系不大。此外，在小规模算例中仅由两台AGV执行较少运送任务数且任务起终点多不在相同横纵方向上，因此当检测到碰撞时，优先采取e/f/g/h或E/F/G/H变换路径，可在避开碰撞的同时不增加总完成时间。

综上可知，由于多AGV在同一车间行驶必须考虑碰撞影响，系统实际完成时间取决于碰撞调整后的运送时间，即第2阶段的最终结果。对于本文小规模算例，采取两种方式求解的最终结果一致，因此本文提出的两阶段算法(时间优先级)能有效解决小规模问题。在计算时间方面，随着数据规模增大，CPLEX求解时间呈指数型增长，且当加工任务数达到36时，CPLEX在90 min内无法得到结果，由于受CPLEX求解限制，在小规模问题中算例数量较少。而实际半导体生产车间规模较大，进行大规模最优解求解不可行，因此本文提出的两阶段算法(时间优先级)具有很好的实用性。

4.2 大规模仿真实验

本节构建了一个大小为4×9的半导体生产车间，与图4所示布局相同，仅在数量上不同，电子货架、加工机台数均为4。首先采用基于时间优先级的任务分配方法得到AGV运送任务序列，再根据行驶规则生成AGV初始路径；然后采用AGV碰撞检测和避免算法获得全局AGV无碰路径，得到AGV完成所有运送任务的时间；最后通过对比两阶段算法结果与生产计划最优时间的差异，以验证本文算法的求解效果，通过对比仅采用延迟避撞策略与采用本文3.2节所有避撞策略的结果，以说明设计多种避撞策略的必要性。在仅采用延迟避撞策略中，AGV采取等待措施而非变换路径，当检测到当前AGV行驶栅格中存在某时刻被其他优先级更高的AGV占用，则该AGV在碰撞点前一栅格等待，直到目标栅格处于空闲状态。结果如表3所示，其中，ItemNum表示运送任务数量，Expected time表示生产计划的最优完成时间，Priority表示第1阶段初始路径完成时间，Only delay表示仅采用延迟避撞策略的结果，All method表示采用所有避撞策略的结果。Gap1、Gap2、Gap3分别表示采用本文所有避撞策略的完成时间与最优完成时间、第一阶段初始路径完成时间、仅采用延迟避撞策略完成时间的结果差异，负号表示相对减少。

表3 大规模实验结果

由表3结果可知：

(1)Gap1表明采用本文所有避撞策略的完成时间与最优时间的差值均小于11%，在可接受范围内，说明本文提出的两阶段算法(时间优先级)在求解大规模问题时效果较好，能够在获得全局AGV无碰路径的同时按生产计划高效地完成运送任务。

(2)由Gap2可以看出，采用本文所有避撞策略与第一阶段未进行碰撞避免的完成时间相差不超过4%，说明采用避撞策略对完成时间的影响不大。在采用多台AGV协同工作的生产车间，必须采取合理的避撞措施以实现生产车间稳定运行，而本文两阶段算法(时间优先级)可在保证运行效率的同时获得AGV无碰路径，具有一定的可行性。

(3)Gap3表明仅采用延迟避撞策略的完成时间比采用本文所有避撞策略的完成时间基本增加1%～5%，说明仅采取延迟等待措施可能会造成时间浪费，增加整体作业完成时间，十分有必要采取多种路径变换方式对AGV进行碰撞避免，而本文考虑多种情况对AGV路径进行调整，符合生产车间复杂的工作情况，具有一定的灵活性。

4.3 AGV数量灵敏度分析

对于企业来说，生产车间的运营需考虑效率和成本两个方面，若能在保证高效率的同时减少AGV数量，可进一步降低运营成本。基于此，本节在4×9的生产车间中，采用两阶段算法(时间优先级)探讨最优数量的AGV调度问题，在不同规模的运送任务下测试不同数量AGV对系统运作效率的影响。结果如表4所示，其中，N表示运送任务数，A表示AGV数，每个任务的第1行为任务总完成时间(单位：s)，第2行为系统碰撞次数。

表4 不同情况的系统效率

由表4可知，在不同的运送任务规模下，AGV数量由1增加至4时，任务完成时间减幅明显，碰撞次数缓慢增加；当由5逐步增加时，两者均增幅明显，如图8和图9所示。导致该情况的原因是：在一定范围内增加AGV数量可以减少每台AGV的平均任务数，且不会造成太多碰撞；当AGV数量较多时，虽然每台AGV完成任务数减少，但碰撞的可能性急剧增加，此时AGV不断变换路径导致行走时间增加，因此不断增加AGV数量对减少运送任务的完成时间、改善系统工作效率影响不大。综上，在4×9的半导体生产车间中合适的AGV配置数量为3～4台，此时完成时间和碰撞次数均相对较少。通过对车间中AGV的使用数量进行灵敏度分析，可为不同车间规模的AGV数量配置提供参考，以实现采用较少AGV高效完成工件运送任务，达到合理利用车间资源、提高企业经济效益的目的。

5 结束语

本文研究了半导体生产车间中采用自动化物料运输系统的AGV调度优化问题，主要包括单AGV路径规划问题及多AGV碰撞避免问题，并基于此设计了两阶段优化方法进行求解。首先，分别采用数学模型求解和基于时间优先级的任务分配算法将半导体工件运送任务分配至AGV，并根据每台AGV的运送任务序列和AGV行驶规则生成初始路径。其次，设计碰撞检测及避免算法，针对不同碰撞情况采取相应的调整策略，从而获得高效可行的全局AGV调度方案。然后，通过算例实验表明本文两阶段算法(时间优先级)能够调度AGV在具有4个货架和4个机台的半导体车间中完成480个工件运送任务，并且在算法效率和求解时间上均具有很好的实用性。最后，通过实验证明了本文提出的多种避撞策略能够在获得AGV无碰路径的同时，按生产计划高效地完成运送任务，并对AGV数量进行灵敏度分析，给出了半导体生产车间最优的AGV数量配置建议。综上所述，本文根据半导体制造工艺流程对AGV进行任务调度，并对AGV进行路径规划及碰撞避免，最终获得自动化物料运输系统实时调度方案，可为我国建设智能化半导体生产车间提供参考。此外，本文提出的算法可扩展到其他采用AGV的自动化码头、智能仓库等实际应用场景，具有很强的实用价值。未来将考虑AGV非匀速的情况以及AGV的充电问题。