本发明涉及一种带有批处理机的跨作业单元调度方法，包括以下步骤：1、定义三种不同结构的信息素；2、初始化信息素；3、按照加工顺序，将每个零件的批处理工序之前的每道工序分派至机器；4、按照时间顺序，将每个机器上的每道工序排序；5、将零件组批、调度批处理工序；6、按照加工顺序，将每个零件的批处理工序之后的每道工序分派至机器；7、按照时间顺序，将每个机器上的每道工序排序；8、根据形成的解，更新信息素；9、若循环次数达到上限，或连续若干次最优解无变化，则结束；否则，转第2步。本发明能够解决生产过程中零件跨单元调度问题；(2)能够处理生产过程中的批处理工序和非批处理工序的集成调度，并保证运行效率。
1.一种带有批处理机的跨作业单元调度方法，包括以下步骤：第1步：定义如下表所示的索引和变量：表1索引和变量
同时，定义三种不同结构的信息素：a)工序分派中的信息素结构
在工序选择机器的过程中，定义一个O×M大小的矩阵来表示信息素，其中O表示工序总数，M表示机器总数，矩阵中的元素(Oij，k)表示工序Oij在机 器k上加工对应的信息素浓度；
在每台机器上的工序排序时，定义M个O×O大小的矩阵来表示信息素，其中O表示工序总数，第m个矩阵中的元素(Oij，k)表示机器m上工序Oij在此机器上第k个加工对应的信息素浓度；
c)批处理机工序组批中的信息素结构在批处理工序组批的过程中，定义N×N大小的矩阵来表示信息素，其中N表示零件总数，元素(i，j)表示零件i与零件j在同一批次对应的信息素浓度；
批处理工序组批时从可选零件列表中每次选择一个零件加入现有批，而批次的数目无法确定，故有式(1)所示定义：
其中，τi，b表示将零件i加入批次b对应的信息素浓度，τi，k表示零件i与零件k在同一批次对应的信息素浓度，|Bb|表示Bb中已有的零件个数；式(1)表示若批次b不为空，则零件i加入批次b对应的信息素浓度为零件i分别与批次b中现有的零件在同一批次的信息素浓度之和，否则为定值1；
进行初始化，输入机器信息、单元划分、单元间转移距离、须加工的零件总数及各零件的工艺信息，然后按照如下说明初始化信息素：a)初始化工序分派中的信息素
其中，τi，j，m表示工序oij在机器m上加工对应的信息素浓度，ε为信息素浓度初始值，定为
其中，在机器m上τm，i，j，k表示工序oij在第k个加工对应的信息素浓度，ε为 信息素浓度初始值，定为0.01；
c)初始化批处理机工序分批中的信息素其中，τi，k表示零件i和零件k在同一批次上加工对应的信息素浓度，ε为信息素浓度初始值，定为0.01；
按照加工顺序，将每个零件的批处理工序之前的每道工序分派至机器，即对于每个零件按照工序的加工顺序依次为每道工序选定加工机器，每台机器被选中的概率为：其中，Pri，j，m表示工序oij在机器m上加工的概率，ρi，j，k表示对应的启发式信息，α1、β1分别表示信息素浓度、启发式信息所占权重；
由于考虑了零件的跨单元转移时间，故ρi，j，k定义如下：其中，Pi，j，k表示oij在机器k上的加工时间，TTiDm′，k表示零件i单位距离转移时间与前道工序加工的机器m’到机器k的转移距离之积，即零件i对应的转移时间；由启发式信息公式可看出，在工序分派时优先选择加工时间和转移时间之和较小的机器；
得到工序在每台可选的机器上加工的概率后，以轮盘赌算法随机选定某台机器加工该工序；
按照时间顺序，将每个机器上的每道工序排序，即在工序分派的基础上，确定每台机器上工序的加工先后顺序以及起始时间；具体方法为：对于每台机器，从其可调度工序中，根据以下公式所示概率，以轮盘赌算法随机选择一道工序安排在下一个加工；重复此过程，直至所有工序均被调度；
其中，Prm，i，j，k表示机器m上Oij在第k个加工的概率，ρm，i，j，l表示对应的启发式信息，α2、β2分别表示信息素浓度、启发式信息所占权重；
零件排序的启发式信息综合考虑了零件的跨单元转移时间和机器的准备时间，同时零件的跨单元转移时间和机器的准备时间事实上是可以重叠的，即在零件的转移过程中，对应的机器可以开始为加工该零件做准备，故启发式信息定义如式(8)所示：其中，fi，j-1表示零件i的第j-1道工序加工结束的时间，Dm′，m表示从加工零件上一道工序的机器m’到机器m的转移距离，li，j用于标记机器上前一个加工的零件所属零件族：li，j＝
0表示零件i在机器上第一个加工或机器上前一个加工的零件与零件i属于同一零件族，li，j＝1表示机器上前一个加工的零件与零件i不属于同一零件族，TEm，i，j表示机器m上Oij的前一道工序的结束时刻，max(fi，j-1+TTiDi，j，m，TEm，i，j+li，jSTi，m)-TEm，i，j则表示从前一道工序结束到oij开始加工所花费的实际时间；由启发式信息公式可知，在工序排序时，优先调度能较早开始加工的工序；
在工序排序过程中，对于任意一台机器，其可调度工序为分派至该机器的工序中，任一零件的第一道工序或前一道工序已被排序的工序的集合；
将零件组批、调度批处理工序，即决策将哪些零件的批处理工序放在批处理机的同一批次进行加工，具体方法为：
Step2.更新候选零件集，候选零件集的定义为：若b为任一批次，则其候选零件集为以下集合：
即任一批次的候选零件集，为所有与其中零件同一零件族且加入此批次后不会使批次中零件总大小超过批处理机容量或批次浪费和空闲空间增加的零件的集合；
对于批处理机的一个批次b，b的浪费和空闲空间WISb为该批次浪费空间WSb和空闲空间ISb之和，ΔWISb为批次b的浪费和空闲空间的变化量；对于一 个批处理工序的调度解S，WIS(S)表示S的浪费和空闲空间，等于S的所有批次的浪费和空闲空间之和；批次b的浪费空间WSb和空闲空间ISb的定义如下：ISb＝CB·(BSb-BEb-1) (11)其中，BSb，BEb分别表示批次b的开始和结束时间，Pi，m为零件i的批处理工序加工时间，且当b＝0时，令BEb-1为初始时刻，故有：
Step3.按照以下公式计算候选零件集中零件被选中的概率，然后以轮盘赌算法选择其中一个零件加入本批次；
其中，α3、β3分别表示信息素浓度、启发式信息所占权重，Pri，b表示零件i加入批次b的概率，ΔWSi，b＝WSb‘-WSb＝CB·(Pb‘-Pb)-SiPi，m (15)b’代表批次b加入零件i之后的批次，WSb‘表示加入零件i后的批次b’的浪费空间；
Step4.若候选零件集不为空，转至Step2，否则继续执行Step5；
Step5.若还有零件尚未组批，转至Step 1，继续组建下一批次，否则结束；
按照加工顺序，将每个零件的批处理工序之后的每道工序分派至机器，方法同第3步；
按照时间顺序，将每个机器上的每道工序排序，方法同第4步；
根据形成的解，更新信息素，更新规则为：对于最优解集合中每一个解，
a)若工序Oij分派至机器m，则τi，j，m＝(1-ρ)·τi，j，m+ρ·Δτb)若工序Oij在机器m上第k个加工，则τm，i，j，k＝(1-ρ)·τm，i，j，k+ρ·Δτc)若零件i加入批次b，则
其中，τi，k表示零件i与零件k在同一批次上加工时对应的信息素浓度，ρ表示信息素挥发率，Δτ为信息素更新量：Q为信息素更新量影响因子，γ1，γ2，γ3为三个优化目标的权值，分别表示对三个优化目标：最大完工时间、批处理机利用率、非批处理工序和批处理工序之间等待时间的重视程度，且γ1+γ2+γ3＝1， 分别表示该调度解的总完工时间，批处理机利用率，非批处理工序和批处理工序之间总等待时间与当前最优解的比值；
若循环次数达到上限，或连续若干次最优解无变化，则结束；否则，转第2步；
τ_max为一个预设定值，它限制了信息素浓度的最大值。
2.根据权利要求1所述的一种带有批处理机的跨作业单元调度方法，其特征在于，按照下表所示设置用户参数：
一种带有批处理机的跨作业单元调度方法
技术领域
[0001] 本发明涉及一种制造系统的调度方法，特别涉及一种带有批处理机的跨作业单元调度方法，属于先进制造生产控制与调度优化领域。
背景技术
[0002] 单元制造系统(Cellular Manufacturing System，CMS)是成组技术(Group Technology，GT)在制造领域的典型应用，体现了精益生产的哲理。在CMS中，将机器根据零件工艺的相似性进行分组，形成加工能力相对独立的单元，每个单元能完成一个或多个零件族的生产过程。然而在实际生产中，由于产品日益多样化且单元内生产能力有限，存在某些零件的若干道部分工序需要在其他单元的机器上加工的情况。同时，另一方面，考虑到生产经济学、预算以及空间限制等原因，为每个单元购买额外机器并不可行。因为这类机器通常价格昂贵，启动一次耗费较大，考虑到生产经济学、预算以及空间限制等原因，只能将其放置在某个特定的单元内。这些设备作为稀缺资源，往往可以加工多个零件族的零件(下文中将这种设备称为共用关重设备，Critical Shared Machine，CSM)。在这种情况下，需要跨多个单元才能完成的特殊零件(Exceptional parts，EP)，在单元间的转移就形成了跨单元转移问题(inter-cell move)。跨单元转移导致各单元不能独立进行调度，需要单元间协同安排零件的加工顺序。
[0003] 早在上世纪九十年代初，Garza和Smunt就指出由于跨单元转移难以避免，理想的CMS将难以实施，须定量分析跨单元转移对生产系统产生的影响，但大部分研究一直集中在如何进行单元构造及如何进行单元内部管理等问题上。直到近年来，随着CMS的实施逐渐深入并遇到困难，跨单元调度这一问题才开始被关注，相关研究可以分为跨流水单元和跨作业单元两种类型。
[0004] 跨流水单元调度方面，Yang和Liao考虑零件至多在两个单元间移动转移，且只移动转移一次。以flow-time最短为目标，采用分支定界法和启发式算法，解决每个单元内工序的加工顺序。然而，随着工厂布局向单元制造不断转变，跨单元移动转移呈普遍趋势，且越来越复杂，因此零件在两个以上单元之间的移动转移问题更值得关注。Solimanpur等人考虑了特殊零件在两个以上单元间的移动转移问题，以makespan最小为目标，采用启发式算法分两步解决跨单元调度问题。Golmohammadi等人考虑了单元间移动转移，采用改进的ElectroMagnetism-like(EM-like)算法集成解决零件族调度顺序和每个零件族内零件的调度顺序。Mosbah等人以最小化makespan，总完工时间和机器空闲时间为优化目标的采用Extended Grate Deluge(EGD)算法和启发式算法来解决单元制造系统中具有特殊零件的
调度问题。为了解决零件在单元内和单元间的多目标调度问题，Gholipour等人提出一种基于分散搜索的元启发式算法。
[0005] 跨作业单元方面，Tang等人使用分散搜索方法解决特殊零件跨单元调度问题。Elmi等人在Tang等人问题模型的基础上，允许可重入零件，即一个零件的不连续工序可以在同一台机器上加工；采用模拟退火的方法，编码方式和Tang等人的方案相同，同时利用邻近结构优化最终解。Xiao等人考虑了零件随机动态到来的情况，采用基于信息素的Agent协商方法解决了柔性路径下的跨作业单元调度问题。
[0006] 上述参考文献研究中的对跨单元调度问题的研究考虑的问题模型是都按照基于传统的调度问题模型，生产模式(如流水车间或调度模型、作业车间)进行划分的调度模型。
然而在实际生产中，机器类型同样对生产调度产生重要影响，该问题来源于车辆关键零部件的实际生产过程。
[0007] 零件的加工过程不仅需要车铣刨磨等机械加工工序，还需要进行退火、淬火、回火、渗碳等热处理工序以获得预期的力学性能和物理性能。据调研结果显示，车辆关键零部件的生产过程中有35％的零件既有机加工序也有热处理工序。一般来说，通常将机加阶段和热处理阶段的调度分开考虑，原因是零部件的热处理时间通常远大于机加时间。但我们的调研结果显示：从整体上看，机加工序时间虽较短，但是数量较多，因此整个机加阶段的时间占生产全过程的39％左右，而热处理阶段则占42％左右，二者大体相当；另一方面，我们在调研中发现目前已有一部分复杂机加工序的加工时间达到数千分钟，这些现象都使得机加阶段和热处理阶段在最重要的优化指标——时间上得以相提并论。热处理设备作为一类CSM，仅放置在某一特定单元内。因此不同零件族对热处理设备的访问所引起跨单元转移同时也是单处理机(机加设备)和批处理机(热处理设备)之间的转移。机加工序需要满足机器唯一性约束(一台机器同一时刻只能加工一个零件)和零件唯一性约束(一个零件同一时刻只能被一台机器加工)，属于车间调度问题范畴；热处理工序无须满足机器唯一性约束，属于批量调度问题范畴。经典的作业车间调度问题是一个NP-hard问题，而批量调度问题的引入使其更加复杂。目前从不同设备类型的角度分析跨单元调度问题的研究尚未见成果发表。
发明内容
[0008] 本发明的目的是针对现有技术的不足，在跨单元协作模式下，为带有批处理机的作业单元找到高效可行的调度方法，以最小化完工时间、最大化批处理机利用率、以及最小化非批处理工序和批处理工序之间等待时间为目标，来保证单元制造系统整体高效的运作。
[0009] 本发明考虑的制造系统由多个单元组成，每个单元中有若干台加工能力不同的机器，可以完成工艺相似的零件族的生产；系统中有且只有一台批处理机，放置在其中一个单元中；单处理机一次只能加工一个零件，批处理机则可以同时加工多个零件；制造系统还满足以下条件：
[0010] 1)所有零件在零时刻到达；
[0011] 2)批处理机有一定的空间限制，零件的尺寸规格已知，在不超过空间限制的条件下，同一零件族的零件可以同时在批处理机上加工；
[0012] 3)零件的加工过程由多道具有次序约束的工序组成，其中每个零件有且只有一道工序需要在批处理机上完成，且批处理工序不为最后一道工序；
[0013] 4)由于单元之间机器加工能力部分重叠，导致零件具有柔性路径，但对于某个零件的特定工序，在每个单元内至多有一台可加工机器且加工时间已知；
[0014] 5)批处理工序的加工时间为当前批次中所有零件批处理时间的最大值；
[0015] 6)考虑单元间转移时间，而忽略单元内转移时间，不同单元间转移时间因距离和零件类别而不同；
[0016] 7)考虑不同零件族之间的主要准备时间，而忽略同一零件族内部的次要准备时间，即当同一机器上连续加工同一零件族的零件时，忽略准备时间；其中主要准备时间已知且不随调度次序改变而发生变化；
[0017] 8)批处理设备之前的缓冲区容量足够大；
[0018] 9)每台机器加工零件都是非中断非抢占式的；
[0019] 10)不考虑机器故障、原材料短缺及操作人员空缺的情况。
[0020] 针对满足以上条件的制造系统，本发明提供了一种带有批处理机的跨作业单元调度方法，包括以下步骤：
[0021] 第1步：定义如下表所示的索引和变量：
[0022] 表1 索引和变量
[0023]
[0024]
[0025] 同时，定义三种不同结构的信息素：
[0026] a)工序分派中的信息素结构
[0027] 在工序选择机器的过程中，定义一个O×M大小的矩阵来表示信息素，其中O表示工序总数，M表示机器总数，矩阵中的元素(Oij，k)表示工序Oij在机器k上加工对应的信息素浓度；
[0028] b)工序排序中的信息素结构
[0029] 在每台机器上的工序排序时，定义M个O×O大小的矩阵来表示信息素，其中O表示工序总数，第m个矩阵中的元素(Oij，k)表示机器m上工序Oij在此机器上第k个加工对应的信息素浓度；
[0030] c)批处理机工序组批中的信息素结构
[0031] 在批处理工序组批的过程中，定义N×N大小的矩阵来表示信息素，其中N表示零件总数，元素(i，j)表示零件i与零件j在同一批次对应的信息素浓度；
[0032] 批处理工序组批时从可选零件列表中每次选择一个零件加入现有批，而批次的数目无法确定，故有式(1)所示定义：
[0033]
[0034] 其中，τi，b表示将零件i加入批次b对应的信息素浓度，τi，k表示零件i与零件k在同一批次对应的信息素浓度，|Bb|表示Bb中已有的零件个数；式(1)表示若批次b不为空，则零件i加入批次b对应的信息素浓度为零件i分别与批次b中现有的零件在同一批次的信息素浓度之和，否则为定值1；
[0035] 第2步：
[0036] 进行初始化，输入机器信息、单元划分、单元间转移距离、须加工的零件总数及各零件的工艺信息，然后按照如下说明初始化信息素：
[0037] a)初始化工序分派中的信息素
[0038]
[0039] 其中，τi，j，m表示工序Oij在机器m上加工对应的信息素浓度，ε为信息素浓度初始值，定为0.01；
[0040] b)初始化工序排序中的信息素
[0041]
[0042] 其中，在机器m上τm，i，j，k表示工序Oij在第k个加工对应的信息素浓度，ε为信息素浓度初始值，定为0.01；
[0043] c)初始化批处理机工序分批中的信息素
[0044]
[0045] 其中，τi，k表示零件i和零件j在同一批次上加工对应的信息素浓度，ε为信息素浓度初始值，定为0.01；
[0046] 第3步：
[0047] 按照加工顺序，将每个零件的批处理工序之前的每道工序分派至机器，即对于每个零件按照工序的加工顺序依次为每道工序选定加工机器，每台机器被选中的概率为：
[0048]
[0049] 其中，Pri，j，m表示工序Oij在机器m上加工的概率，ρi，j，k表示对应的启发式信息，α1、β1分别表示信息素浓度、启发式信息所占权重；
[0050] 由于考虑了零件的跨单元转移时间，故ρi，j，k定义如下：
[0051]
[0052] 其中，Pi，j，k表示Oij在机器k上的加工时间，TTiDm′，k表示零件i单位距离转移时间与前道工序加工的机器m’到机器k的转移距离之积，即零件i对应的转移时间；由启发式信息公式可看出，在工序分派时优先选择加工时间和转移时间之和较小的机器；
[0053] 得到工序在每台可选的机器上加工的概率后，以轮盘赌算法随机选定某台机器加工该工序；
[0054] 第4步：
[0055] 按照时间顺序，将每个机器上的每道工序排序，即在工序分派的基础上，确定每台机器上工序的加工先后顺序以及起始时间；具体方法为：
[0056] 对于每台机器，从其可调度工序中，根据以下公式所示概率，以轮盘赌算法随机选择一道工序安排在下一个加工；重复此过程，直至所有工序均被调度；
[0057]
[0058] 其中，Prm，i，j，k表示机器m上Oij在第k个加工的概率，ρm，i，j，l表示对应的启发式信息，α2、β2分别表示信息素浓度、启发式信息所占权重；
[0059] 零件排序的启发式信息综合考虑了零件的跨单元转移时间和机器的准备时间，同时零件的跨单元转移时间和机器的准备时间事实上是可以重叠的，即在零件的转移过程中，对应的机器可以开始为加工该零件做准备，故启发式信息定义如式(8)所示：
[0060]
[0061] 其中，fi，j-1表示零件i的第j-1道工序加工结束的时间，Dm′，m表示从加工零件上一道工序的机器m’到机器m的转移距离，li，j用于标记机器上前一个加工的零件所属零件族：li，j＝0表示零件i在机器上第一个加工或机器上前一个加工的零件与零件i属于同一零件族，li，j＝1表示机器上前一个加工的零件与零件i不属于同一零件族，TEm，i，j表示机器m上Oij的前一道工序的结束时刻，max(fi，j-1+TTiDi，j，m，TEm，i，j+li，jSTi，m)-TEm，i，j则表示从前一道工序结束到Oij开始加工所花费的实际时间；由启发式信息公式可知，在工序排序时，优先调度能较早开始加工的工序；
[0062] 在工序排序过程中，对于任意一台机器，其可调度工序为分派至该机器的工序中，任一零件的第一道工序或前一道工序已被排序的工序的集合；
[0063] 第5步：
[0064] 将零件组批、调度批处理工序，即决策将哪些零件的批处理工序放在批处理机的同一批次进行加工，具体方法为：
[0065] Step1.选择到达时间最早的零件，加入本批次；
[0066] Step2.更新候选零件集，候选零件集的定义为：若b为任一批次，则其候选零件集为以下集合：
[0067]
[0068] 即任一批次的候选零件集，为所有与其中零件同一零件族且加入此批次后不会使批次中零件总大小超过批处理机容量或批次浪费和空闲空间增加的零件的集合；
[0069] 对于批处理机的一个批次b，b的浪费和空闲空间WISb为该批次浪费空间WSb和空闲空间ISb之和，ΔWISb”为批次b的WIS空间的变化量；对于一个批处理工序的调度解S，WIS(S)表示S的浪费和空闲空间，等于S的所有批次的WIS之和；WS和IS的定义如下：
[0070]
[0071] ISb＝CB·(BSb-BEb-1) (11)
[0072] 其中，BSb，BEb分别表示批次b的开始和结束时间，Pi，m为零件i的批处理工序加工时间，且当b＝0时，令BEb-1为初始时刻，
[0073] 故有：
[0074]
[0075] Step3.按照以下公式计算候选零件集CLb中零件被选中的概率，然后以轮盘赌算法选择其中一个零件加入本批次，其中CLb由式(9)定义；
[0076]
[0077] 其中，α3、β3分别表示信息素浓度、启发式信息所占权重，Pri，b表示零件i加入批次b的概率，ρi，b表示启发式信息，定义如下：
[0078]
[0079] ΔWSi，b＝WSb′-WSb＝+CB·(Pb′-Pb)-SiPi，m (15)
[0080] b’代表批次b加入零件i之后的批次，WSb′表示加入零件i后的批次b’的浪费空间；
[0081] Step4.若候选零件集不为空，转至Step2，否则继续执行Step5；
[0082] Step5.若还有零件尚未组批，转至Step 1，继续组建下一批次，否则结束；
[0083] 第6步：
[0084] 按照加工顺序，将每个零件的批处理工序之后的每道工序分派至机器，方法同第3步；
[0085] 第7步：
[0086] 按照时间顺序，将每个机器上的每道工序排序，方法同第4步；
[0087] 第8步：
[0088] 根据形成的解，更新信息素，更新规则为：
[0089] 对于最优解集合中每一个解，
[0090] a)若工序Oii分派至机器m，则
[0091] τi，j，m＝(1-ρ)·τi，j，m+ρ·Δτ
[0092] b)若工序Oii在机器m上第k个加工，则
[0093] τm，i，j，k＝(1-ρ)·τm，i，j，k+ρ·Δτ
[0094] c)若零件i加入批次b，则
[0095]
[0096] 其中，τi，k表示零件i与零件k在同一批次上加工时对应的信息素浓度，ρ表示信息素挥发率，Δτ为信息素更新量：
[0097]
[0098] Q为信息素更新量影响因子，γ1，γ2，γ3为三个优化目标的权值，分别表示对三个优化目标：最大完工时间、批处理机利用率、非批处理工序和批处理工序之间等待时间的重视程度，且γ1+γ2+γ3＝1， 分别表示该调度解的总完工时间，批处理机利用率，非批处理工序和批处理工序之间总等待时间与当前最优解的比值；
[0099] 第9步：
[0100] 若循环次数达到上限，或连续若干次最优解无变化，则结束；否则，转第2步。
[0101] 本发明采用最大最小蚂蚁系统(MMAS)的信息素更新方法，在更新的过程中，始终保持信息素浓度处于区间[τmin，τmax]内(τmin和τmax为预设定值)，该方法可以避免方法过早的收敛于局部最优解。
[0102] 参与更新的仅为本次循环中若干个局部最优解(下称为最优解集合)。这样的更新策略的好处是，使得蚁群搜索的范围集中在较优解的附近，而又不会因仅使用循环中的局部最优解或全局最优解更新信息素而使收敛速度过慢。
[0103] 有益效果
[0104] 本发明针对跨带有批处理机的跨作业单元调度问题提出的解决方案，主要有以下3点有益效果：
[0105] (1)能够解决生产过程中零件跨单元调度问题；
[0106] (2)能够处理生产过程中的批处理工序和非批处理工序的集成调度；
[0107] (3)运行效率得到保证。
附图说明
[0108] 图1为解决方案流程图。
具体实施方式
[0109] 下面具体说明本发明的优选实施方式。
[0110] 本实施例按照发明内容中的执行步骤实现本发明提出的基于蚁群优化算法的带有批处理机的跨作业单元调度算法，如图1所示。
[0111] 对本实施例进行如下试验仿真：
[0112] 本发明用于模拟仿真的单元制造系统设置如下：分别设置了20台非批处理机和1台批处理机，各机器所属单元划分如表2所示。非批处理机使用1～20索引，批处理机使用21索引。
[0113] 表2 单元划分
[0114]
[0115] 注释：表中可选机器索引M1-20表示非批处理机，B21表示批处理机。
[0116] 零件的制造工艺路线是柔性的，即对于同一道工序，有至少一个以上单元内的机器可以加工这道工序，而且不同机器相应的处理时间一般不相同。针对本发明提出的问题模型，分别设置了36个零件，每个零件有着不同的工艺流程，且按照假设条件，每个零件有且只有一道批处理工序，其余工序为非批处理工序，批处理工序不为第一道工序。
[0117] 仿真实验数据的每道工序对应的可处理机器是通过随机算法生成的。对于非批处理工序，随机生成每个1～5台机器，分别位于不同单元。零件的大小在20～40之间随机选取，每个零件的工序数在5～19之间随机选取。不同零件在单元间的移动距离各异，移动距离在6～50之间随机选取，由于属于不同零件族的零件在同一台机器上切换而产生的准备时间在1～10之间随机选取。每道非批处理工序的加工时间在2～50之间随机选取，批处理工序的加工时间在100～200之间随机选取。
[0118] 仿真实验的环境如下：
[0119] (1)操作系统：Microsoft Windows 7 32位
[0120] (2)CPU：Intel Core 2 Duo CPU T6400 2.00GHz
[0121] (3)内存：2G
[0122] (4)开发环境：Microsoft Visual Studio 2010
[0123] (5)开发语言：C#
[0124] ACO算法中的参数对其性能有着很大的影响。令参数α1＝α2＝α3＝1，通过调整不同的β1，β2，β3值反映信息素浓度和启发式信息所占权重。除此之外，信息素挥发比ρ，信息素更新量影响因子Q，信息素浓度最大值τmax等参数也对ACO的性能有不同程度的影响，因此进行下文所述实验确定参数的合理取值。由于Q值仅与信息素浓度的更新量有关，故只需确定Q与τmax比值的合理取值即可，因此在实验时将τmax定为常数5，以简化实验过程。本文提出的算法中需要确定的参数以及仿真实验中取值范围见表3。
[0125] 表3 参数仿真实验设计
[0126]参数 范围
β1＝β2 (0.2，0.5，1，2)
β3 (0.01，0.1，0.5，1)
Q/τ_max (0.1，0.2，0.4)
ρ (0.1，0.2，0.4)
[0127] 对于表3中的参数设置，仿真时进行了对比试验。由于问题模型中定义3个不同的调度目标，而其中交货期又是生产实际中较为常见和重要的一个，因此，仿真实验进行时，将交货期、批处理机利用率、总等待时间的权重分别设置为0.7、0.2、0.1，评价算法使用不同参数所得到的解的优劣时，使用解对应的三个调度目标的值在所有解中的排名的加权和作为标准。实验结果如表4所示(受篇幅所限，此处仅列出加权排名在前的前20组数据)：
[0128] 表4 参数仿真实验结果
[0129]
[0130]
[0131] 从实验结果可以得出，β1＝2，β3＝0.01，ρ＝0.2，Q/τ_max＝0.2时，得到的解的性能最优。
[0132] 因此，用户实现本发明时，建议对参数进行如下设置：
[0133]参数 取值范围 建议值
α1＝α2＝α3 1 1
β1＝β2 (0，4) 2
β3 (0，4) 0.01
ρ (0，1) 0.2
τ_max (1，10) 5
Q (0，τ_max) 0.2*τ_max
[0134] 在本实施例的性能比较中，算法的性能是基于上述建议值得到的。
[0135] 仿真实验采用表5中不同的候选零件集规则和(或)不同的启发式规则的组合进行对比试验(下文用CACO方法，Combinational Ant Colony Optimization，代指本发明所提出的算法)。
[0136] 在批处理工序调度时采用了候选零件集的概念，并使用了WS作为ACO算法的启发式信息；在其他工序调度时，采用处理时间和跨单元转移时间、准备时间相结合的公式作为启发式信息。为验证CACO方法的性能，设计实验考虑2种不同候选零件集规则和组批启发式信息，1种工序分派启发式信息，1种工序排序启发式信息分别与CACOI-CACOIV算法进行组合，将上述11种组合情况与本文提出的算法CACO进行对比。具体如表5所示。
[0137] 表5 对比仿真实验设计
[0138]
[0139]
[0140] 下面以最大完工时间、批处理机利用率、非批处理工序和批处理工序之间总等待时间三个性能指标，分析仿真实验的结果。为了能直观的进行三个性能指标的综合对比，分析时分别计算三个性能指标上其他对比组合与CACO方法相比的Gap值，并按照0.7、0.2、0.1的权重计算加权Gap值，并以此Gap值作为评价算法性能的指标。计算公式如下：
[0141]
[0142]
[0143]
[0144]
[0145] 式中，Makespan、UseRate、WaitTime分别代指三个性能指标最大完工时间、批处理机利用率、非批处理工序和批处理工序之间， 分别表示三个性能指标上某一组合与CACO方法相比的Gap值，Gapi为其加权值。
[0146]
[0147]
[0148] 由上述仿真实验结果可以看出，在本实施例中，采用FB作为候选零件集仍然可明显提升批处理机利用率，但会严重影响其余两个性能指标，加权Gap多在10％～30％，性能较差。
[0149] CACOI+WIS+CACOIII+CACOIV的组合解得的完工时间略优于CACO的解，但批处理机利用率却有明显下降，同时，也存在若干种组合，在某一性能指标上接近或略微优于CACO，但在其余指标上均存在一定差距。这种情况下可以得出结论，CACO算法所采用的候选零件集策略和启发式信息总体性能最优。
[0150] 应该理解的是，本实施方式只是本发明实施的具体实例，不应该是本发明保护范围的限制。在不脱离本发明的精神与范围的情况下，对上述内容进行等效的修改或变更均应包含在本发明所要求保护的范围之内。
