维普资讯 http://www.cqvip.com １８４ ２００７，４３（２７） Ｃｏｍｐｕｔｅｒ Ｅｎｇｉｎｅｅｒｉｎｇ ａｎｄ Ａｐｐｌｉｃａｔｉｏｎｓ计算机工程与应用 解特殊工艺约束拖后调度问题的并行遗传算法 高家全 ，赵端阳 ，何桂霞 ，王雨顺 ＧＡＯ Ｊｉａ－ｑｕａｎ ，ＺＨＡＯ Ｄｕａｎ—ｙａｎｇ ，ＨＥ Ｇｕｉ－ｘｉａ ，ＷＡＮＧ Ｙｕ－ｓｈｕｎ １．浙江工业大学之江学院，杭州３１００２４ ２．南京师范大学数学与计算机科学学院，南京２１００９７ １．Ｚｈｉｊｉａｎｇ Ｃｏｌｌｅｇｅ，Ｚｈ￣ｉａｎｇ Ｕｎｉｖｅｒｓｉｔｙ ｏｆ Ｔｅｃｈｎｏｌｏｇｙ，Ｈａｎｇｚｈｏｕ ３１００２４，Ｃｈｉｎａ ２．Ｓｃｈｏｏｌ ｏｆ Ｍａｔｈｅｍａｔｉｃｓ ａｎｄ Ｃｏｍｐｕｔｅｒ Ｓｃｉｅｎｃｅ，Ｎａｎｊｉｎｇ Ｎｏｒｍａｌ Ｕｎｉｖｅｒｓｉｔｙ，Ｎａｎｊｉｎｇ ２１００９７，Ｃｈｉｎａ Ｅ－ｍａｉｌ：ｓｐｒｉｎｇｆ１２＠１６３．ｃｏｒｎ ＧＡＯ Ｊｉａ－ｑｕａｎ，ＺＨＡＯ Ｄｕａｎ－ｙａｎｇ，ＨＥ Ｇｕｉ—ｘｉａ，ｅｔ ａ１．Ｐａｒａｌｌｅｌ ｇｅｎｅｔｉｃ ａｌｇｏｒｉｔｈｍ ｆｏｒ ｔａｒｄｉｎｅｓｓ ｓｃｈｅｄｕｌｉｎｇ ｐｒｏｂｌｅｍ、ｖｉｔｈ ｓｐｅｃｉａｌ ｐｒｏｃｅｓｓ ｃｏｎｓｔｒａｉｎｔ．Ｃｏｍｐｕｔｅｒ Ｅｎｇｉｎｅｅｒｉｎｇ ａｎｄ Ａｐｐｌｉｃａｔｉｏｎｓ．２００７。４３（２７）：１８４—１８６． Ａｂｓｔｒａｃｔ：Ｉｎ ｏｒｄｃＦ ｔｏ ｓｏｌｖｅ ｐａｒａｌｌｅｌ ｍｕｌｔｉ－ｍａｃｈｉｎｅ ｔａｒｄｉｎｅｓｓ ｓｃｈｅｄｕｌｉｎｇ ｐｒｏｂｌｅｍ ｗｉｔｈ ｓｐｅｃｉａｌ ｐｒｏｃｅｓｓ ｃｏｎｓｔｒａｉｎｔ ｉｎ ｔｅｘｔｉｌｅ ｅｎｔｅｒ－ ｐｒｉｓｅ，ａ ｇｅｎｅｔｉｃ ａｌｇｏｒｉｔｈｍ ｂａｓｅｄ ｏｎ ｖｅｃｔｏｒ ｃｏｄｉｎｇ ｍｅｔｈｏｄ ｉｓ ｐｒｅｓｅｎｔｅｄ．Ｔｈｅ ａｌｇｏｒｉｔｈｍ ｓｈｏｗｓ ｔｈｅ ｆｏｌｌｏｗｉｎｇ ａｄｖａｎｔａｇｅｓ：ｉｔｓ ｃｏｄｉｎｇ ｍｅｔｈｏｄ ｉｓ ｓｉｍｐｌｅ ａｎｄ ｃａｎ ｅｆｆｅｃｔｉｖｅｌｙ ｒｅｆｌｅｃｔ ｔｉｌｅ ｖｉｒｔｕａｌ ｓｃｈｅｄｕｌｉｎｇ ｐｏｌｉｃｙ，ｗｈｉｃｈ ｃａｎ ｖｉｖｉｄｌｙ ｒｅｆｌｅｃｔ ｔｈｅ ｎｕｍｂｅｒｓ ａｎｄ ｓｅｑｕｅｎｃｅｓ ｏｆ ｔｈｅｓｅ ｐｒｏｄｕｃｅｄ ｐｒｏｄｕｃｔｓ ｆｒｏｍ ｅｖｅｒｙ ｍａｃｈｉｎｅ，ａｎｄ ｔｈｅｎ ｓａｔｉｓｆｉｅｓ ｐｒｏｃｅｓｓ ｃｏｎｓｔｒａｉｎｔ ａｕｔｏｍａｔｉｃａｌｌｙ．Ｍｅａｎｗｈｉｌｅ，ｕｎｄｅｒ ｔｈｅ ｍｏｄｅ ｏｆ ｍａｓｔｅｒ—ｓｌａｖｅ ｃｏｎｔｒｏｌ ｎｅｔｗｏｒｋｓ，ｐａｒａｌｌｅｌ ｇｅｎｅｔｉｃ ａｌｇｏｒｉｔｈｍ ｉｓ ａｐｐｌｉｅｄ ｉｎ ｏｒｄｅｒ ｔｏ ａｄａｐｔ ｔｏ ｌａｇｅｒ ｓｃａｌｅ ａｎｄ ｒｅａｌ—ｔｉｍｅ ｓｃｈｅｄｕｌｉｎｇ ｐｒｏｂｌｅｍｓ ｏｆ ｔｈｅｓｅ ｅｎｔｅｒｐｒｉｓｅｓ．Ｔｈｅ ｃｏｍｐｕｔａｔｉｏｎａｌ ｒｅｓｕｌｔｓ ｓｈｏｗ ｔｈａｔ ｉｔ ｉｓ ｅｆｆｅｃｔｉｖｅ．ａｎｄ ｉｓ ａｄｖａｎｔａｇｅｏｕｓ ｏｖｅｒ ｃｏｍｍｏｎ ｇｅｎｅｔｉｃ ａｌｇｏ— ｒｉｔｈｍｓ，ａｎｄ ｈａｓ ｍｕｃｈ ｂｅｔｔｅｒ ｐａｒａｌｌｅｌ ｃｈａｒａｃｔｅｒｉｓｔｉｃｓ． Ｋｅｙ ｗｏｒｄｓ：ｔａｒｄｉｎｅｓｓ ｓｃｈｅｄｕｌｉｎｇ；ｐａｒａｌｌｅｌ ｇｅｎｅｔｉｃ ａｌｇｏｒｉｔｈｍ；ｓｐｅｃｉａｌ ｐｒｏｃｅｓｓ ｃｏｎｓｔｒａｉｎｔ；ｔｅｘｔｉｌｅ ｅｎｔｅｒｐｒｉｓｅｓ 摘要：非等同拖后调度问题作为家纺企业的车间调度问题重要组成部分，有着独特的特点，一方面生产设备非等同，另一方面受 特殊工艺的约束。针对该问题的特点，设计了一个基于向量编码的遗传算法。此算法编码方法简单，能有效地反映实际调度方案， 并能保证满足约束条件，收敛速度快。同时为更好地适应调度实时性和解大型企业此类问题的需要，在基于遗传算法自然并行性 特点的基础上，实现了主从式控制网络模式下并行遗传算法。仿真结果表明，此算法是有效的，优于普通的遗传算法，具有较高的 并行性。 关键词：拖后调度；并行遗传算法；特殊．Ｙ－艺约束；家纺企业 文章编号：１００２—８３３１（２００７）２７—０１８４—０３ 文献标识码：Ａ 中图分类号：ＴＰ３０１．６ １引言 家纺企业是我国传统的制造企业，Ｊｏｂ—Ｓｈｏｐ调度是其核心 问题，其中，拖后并行机调度问题是其调度问题中的重要组成 部分。目前针对拖后并行机调度问题的研究一般都集中在机器 加工能力完全相同的调度类型上，主要包括启发式算法Ｉｌ＿和遗 传算 等等，并取得一定的成果，但从实际应用上看，仍然满 足不了家纺企业实际拖后并行机调度问题的需要。一方面目前 式下并行遗传算法。仿真实验和实际应用实验表明此算法是有 效的，具有较高的并行性。 ２问题描述 家纺企业拖后调度问题的生产运作情况可描述为：有ｎ个 相互的产品，ｍ台机器设备（ｍ≥２，且各台机器不一定相 同），每个产品只有一道工序，且可由此ｍ台机器中的某一台 研究成果考虑的机器多数是等同的；另一方面没有考虑到特殊 工艺的约束，即每个机器只能加工满足某工艺条件的产品。对 于家纺企业来说，不仅生产设备各式各样，生产能力不同，而且 每台机器可加工的产品种类受工艺约束。为此，本文以拖后惩 罚最小为目标，对家纺企业的带特殊工艺约束非等同并行机调 度问题进行研究，针对其特点，提出了一种基于向量编码新的 遗传算法，并对其种群初始化方法，交叉、变异等方面进行了研 究，同时为满足调度实时性和大规模调度问题的需要，在基于 遗传算法自然并行性特点的基础上，实现了主从式控制网络模 完成生产任务，此ｍ台机器可生产的产品类型受。例如一 些仅能生产小提花类型产品，一些仅能生产大提花类型幅宽窄 的产品，一些不仅能生产大提花类型幅宽宽的产品，同时也能 生产大提花幅宽窄的产品等等，每个产品的交货期窗口不同但 确定，拖后受惩罚，提前完成不受惩罚。要找一最优调度方案， 即确定每台机器上加工的产品代号及其加工顺序，使加工完所 有产品后拖后惩罚的总和最小。这里假设每台机器每时刻只能 生产一个产品，且一个产品一旦被某机器生产就不能中断直至 生产完成 基金项目：国家自然科学基金（ｔｈｅ Ｎａｔｉｏｎａｌ Ｎａｔｕｒａｌ Ｓｃｉｅｎｃｅ Ｆｏｕｎｄａｔｉｏｎ ｏｆ Ｃｈｉｎａ ｕｎｄｅｒ Ｇｒａｎｔ Ｎｏ．４０４０５０１９）；浙江省教委基金（Ｎｏ．２００５１４３６）。 作者简介：高家全（１９７２－），男，副教授，博士，研究方向为企业信息化系统与工程，并行数据挖掘，并行生产计划与调度，并行算法 维普资讯 http://www.cqvip.com 高家全，赵端阳，何桂霞，等：解特殊工艺约束拖后调度问题的并行遗传算法 有轮盘赌选择法、局部选择法、随机遍历抽样 假设Ⅳ＝ｆ１，２，…，ｎｌ为产品集合， ＝ ２，…，ｍｌ为机器设 常用选择算法，备的集合，所有能生产产品 的机器集合记为 （． Ｎ），ｔ 表示 产品ｉ由机器 生产所用的生产时间，其中如果某产品ｉ不能 由某机器 口工，则对应的￡ ＝０。ｃ 是产品ｉ的完工时间，［ｄ ｆＪ 表示产品ｉ的交货期窗口，其中ｄ…ｅ分别表示产品 的最早和 最晚交货期，如果产品ｉ在其交货期窗口内完工或提前完工， 则不受惩罚，否则对产品ｉ进行拖后惩罚，其惩跖值是Ｗ ｍａｘ（０，ｃｉ－ｅ ），其中Ｗ 是产品ｉ的单位拖后惩罚。显然，对每个 产品ｉ的惩罚值是其完工时问ｃ 的函数。问题的目标是找到一 个调度使下面的式子最小化。 法、截断选择法等。由于在仿真实验中发现种群内的较多个体 的适应度值彼此非常接近，这里使用排序选择机制来获得个体 被选中的概率，即首先将种群（包括父代和子代）内的个体按适 应值大小排序，其中适应值最大的排第一位；然后对所有排序 号以某种规则选取，使排位越靠前的个体被选中的机会越大。 本文采用线性选择机制，被选中个体的序号定义为： ．， ＬｎⅡｅ ＝～５ （３－ｓｑｒｔ（ 一４（６—１）＊ｒａｎｄｏｍ（））） ２ （６—１） 其中：３＝２为偏置量；ｓ为种群的规模。适应度最大的个体被选 Ｆ（ ）：∑ ｍ ｄｘ（０，ｃ广 ） ｊ＝ｌ 其中０为一个调度方案。 ３串行遗传算法设计 ３．１编码设计 根据问题的特征，提出了基于向量的编码方法。对每个产 品 （ｉ Ｎ），如生产的机器为ｅ （ｅ ｍ ），则定义基因为 ｒ １ 二维向量ｇｉ：ｒ ｆ，于是染色体的基因编码为【譬。，ｇ ，…，ｇ ］＝ ｌｅＩ Ｊ 『 ｌ ２… １，其长度等于待加工产品的总数 。 ｌｅ１ ｅ２‘一ｅｎ Ｊ 如何对编码进行译码，用下面过程来说明： （１）令ｉ＝１； ｒ １ （２）读取基因ｇ ： ｆ； ｌｅｉ Ｊ （３）将产品ｋ 分配到机器ｅ 上； （４）扛 １： （５）如果 ≤ｎ，则转向（２）； （６）分配到同一个机器上的产品根据其在染色体中的排列 位置依次加工，计算每个产品ｉ的完工时间ｃ 从而依据式（１） 计算出目标函数值。 ３．２种群初始化 对于遗传算法来说，初始种群的大小和优劣对算法的执行 效果有明显的影响。为防止产生不可行解，在初始化种群时，采 取如下的初始化方法。 随机产生Ｐｏｐ＿Ｓｉｚｅ（初始种群尺寸）个ｎ维向量（ 。， ，…， ）分别作为初始种群中Ｐｏｐ—Ｓｉｚｅ个染色体的第一行，其中 （ｉ Ⅳ）为互不相同的自然数。对每一个向量（ 。， ：，…， ）中的 元素 （ｉ Ｎ），从可加工其的机器集合ｍ 中随机选择一个机 器代码作为其加工机器，不妨记作为ｅ ，按此办法就生成每个 染色体的第二行向量（ …，ｅｎ）。 可以看出，此种种群初始化方法不仅保证了种群的多样 性，同时又能保证产生的个体能够自动满足约束条件。 ３－３适应值的计算 定义适应值如下： Ｅｖａｌ（Ｏ）：ｄ．ｅ 其中ＯＺ和口为大于０的常数。 ３．４遗传算子 ３．４．１复制 在遗传算法中，按照适应值在亲代种群中选择优良个体的 中的概率大致等于正中间个体的两倍。 ３．４．２交叉 该操作目的是产生新的个体，从而增加搜索到更优个体的 机会。然而传统的交叉方法在处理约束时很容易产生非可行 解，需额外对染色体进行可行性检验，降低了运行速度和寻优 效果。对于设计适合约束化问题的交叉算子一直是遗传算法研 究的热点，其中比较典型的有部分映射交叉法ＰＭＸ（Ｐａｒｔｉａ１１ｖ Ｍａｐｐｅｄ Ｃｒｏｓｓｏｖｅｒ）和顺序交叉法ＯＸ（Ｏｒｄｅｒ Ｃｒｏｓｓｏｖｅｒ）［６１，二者 的区别主要在于ＰＭＸ考虑基因问的绝对顺序，而ＯＸ强调的 是基因问的相对顺序，二者互有优劣。本文在ＰＭＸ和ＯＸ基础 上，针对向量组编码方法，提出了扩展的顺序交叉算子ＥＯＸ （Ｅｘｔｅｎｄｅｄ Ｏｒｄｅｒ Ｃｒｏｓｓｏｖｅｒ）。具体的过程如下： 不妨假设交叉的两个父代个体为 和 ，随机取 中的 一段基因串ｓ，取出ｓ中第一行元素，把 中第一行元素与ｓ 中第一行元素进行比较，如某元素存在于ｓ第一行元素中，则 从 中删除掉对应元素的基因，最后将ｓ插入到 中被删除 掉的基因第一行元素与ｓ中第一行元素第一个元素相同的地 方，形成一个新的子代个体。 下面举例来说明整个交叉过程，假设两个父代个体 和 分别为： １ ３ ２ ４ ７ ５ ６ １『２ ３ ４ ｊ ５ ６ ７ ｛２ １ ３ ２ １ ｉ ３ ２Ｉ’３ ２ １｛２ １ ２ ３ ｉ 则交叉后产生的个体为： ３ ５ ６ １ １ ２ ３．４．３变异 启发式变异：为使变异的染色体有较好的特征，这里采用 了启发式插入变异的方式，即随机地选择要变异的基因ｇｉ，采 用邻接搜索的方法，将集合ｍ 中机器号（但不包括要变异的基 因号）都插入到此一次，覆盖原有的基因，这样产生ｍ 一１个染 色体，选择其中最好的作为变异产生的后代。 此种变异不仅改变了产品的加丁Ｊ岷宁，而且也能较好地保 证种群的多样性，变异后个体质量及产生的个体满足可行性。 ４并行遗传算法 本文的并行混合遗传算法是基于主从式控制网络，具体方 法如下：将其中一个子群体设置成中心，其它子群体均与中心 子群体通讯。中心子群体中始终保存当前最优个体，其它子群 体通过“引进”中心子群体中的最优个体来加快收敛速度。 下面根据主从式控制网络并行遗传算法定义，采用纯节点 编程模式，解决家纺企业带特殊工艺约束条件下拖后并行机调 维普资讯 http://www.cqvip.com
１８６ ２００７，４３（２７） Ｃｏｍｐｕｔｅｒ Ｅｎ ｎｅｅｒｉｎｇ ａｎｄ Ａｐｐｌｉｃａｔｉｏｎｓ计算机工程与应用 度问题的并行遗传算法实现如下： 步骤ｌ产生一个进程（该进程为父进程）； 步骤．２由父进程产生ｍ一１个子进程； 步骤３各子进程（包括父进程）进行串行遗传算法，当子 进程中遗传代数被１０整除，子进程发送最优个体至父进程； 步骤４父进程选择当前各子进程中最优个体（记为ｇｏｏｄ）， 发送给各子进程； 步骤５各子进程用ｇｏｏｄ替换自己当前代种群中适应值最 低的个体； 结果。 从表２中可以看出，对于不同的规模，ＰＧＡ计算的最优计 算值和平均值都略优于文献［３］设计的遗传算法，并且随着规模 的扩大，ＰＧＡ的优势更明显，这表明ＰＧＡ是有效的。 表２ ＰＧＡ与遗传算法 步骤６如果遗传代数大于预先设定的最大遗传代数，则 结束，否则转向步骤３。 ５实验结果 在ＩＢＭ ＰＩＶ ２．８处理器，Ｌｉｎｕｘ９．０操作系统，ＭＰＩ环境下 最后，以两个处理器为例，在表３里列出在不同规模下，算 法结束后各个处理器的通讯时问及总计算时问（单位是秒）。 表３进程通讯时问表 的Ｃｌｕｓｔｅｒ ４个节点机群上对上述方法（记为ＰＧＡ）进行了数值 实验。 ５．１仿真实验和分析 首先，将本文提出的ＥＯＸ交叉算子和经典的ＰＭＸ、ＯＸ算 子进行比较，以验证本文提出的遗传交叉算子的有效性。取种 群规模５０，交叉率为０．８，变异率为０．２５，对不同规模（ｒｔ￣ｍ）进 行了大量的对比实验，其中每种产品的生产机器集合和对应的 生产时间随机产生，且要满足均匀分布。由于篇幅有限，仅列出 表１所示的６组实验结果，对每种规模的问题，表中的拖后调 度惩罚最优计算值、最优计算值的平均值数据为程序运行５０ 次的结果。 表１三种不同交叉算子的ＰＧＡ运行结果比较 从表３可以看出，ＰＧＡ有着较少的通讯时问，并且受规模 的影响较小。也就是说，ＰＧＡ具有较高的并行性。 综合上面三个例子可以看出，本文提出的算法具有如下明 显的优点： （１）编码简单，并能满足工艺约束条件； （２）算法运行速度快，复杂度仅为０（ｎ），优于其它一般的 遗传算法； （３）算法具有较高的并行性。 ５．２实际应用实例 以浙江余杭的一家家纺企业为例，来验证此算法在实际应 用中的可行性和有效性。假设在汁划期要用４台机器生产１５ 种产品，每台机器可生产的产品种类数及生产每种产品所需的 从表１可以看出，对于不同的规模，除带“ ’号标记的少许 处外，采用ＥＯＸ计算得到的最优值和平均值部优于ＰＭＸ和 ＯＸ，并且随着规模的扩大，效果更明显，这表明ＥＯＸ是有效的。 其次，为验证本文提出的算法有效性，将本文算法与文献 时问分别见表４，其中横排为产品种类，纵排为机器号，如果在 横排和纵排的交叉处数值不为０，表示对应机器可生产此产 品，并且生产时问为此数值。 这里初始种群规模为５０，交叉概率为０．７５，变异概率为 ０．２５，对所有的产品，单位拖后惩罚为１．２，则利用ＰＧＡ运算后 得到的拖后调度惩罚最优值为１３．８８４，最优染色体为： 『６ ７ ５ １３ ４ ８ １ ９ １２ １０ １１ ３ １５ ２ １４ １ ［３】中的算法进行比较，实验数据同上，为具有可比较性，假设每 种产品的生产机器集合等于所有机器的集合。同样仅列出表２ 所示的６组实验结果，对每种规模的问题，表中的拖后调度惩 罚最优计算值、最优计算值的平均值数据为程序运行１００次的 ｌ ２】３ ４ ３ ４ ２ ２ ４ ３ 】４ ３ ２】Ｉ 表４机器及对应产品生产时间表 （下转２０８页） 维普资讯 http://www.cqvip.com ２０８ ２００７，４３（２７） Ｃｏｍｐｕｔｅｒ Ｅｎｇｉｎｅｅｒｉｎｇ ａｎｄ Ａｐｐｌｉｃａｔｉｏｎｓ计算机工程与应用 要很多次累加才能使总误差∑ 超过 。 考虑到滚动过程中手指滑动造成的图像平移在１０个像素 以内，因此限定模板图像的搜索范围，配准速度进一步提高。 的ＳＳＤＡ算法，提高了图像的配准速度。 ５总结 本文提出了一个基于ＶＦｗ的滚动按捺指纹拼接系统的实 现方案，ｖＦｗ的采用提高了视频捕获编程的灵活性，同时减少 了对视频设备的依赖。实时准确地检测出当前图像是否含有指 纹是实现自动拼接的首要前提，通过背景自适应更新、双阈值 判决技术，实现了此功能；改进的ＳＳＤＡ算法，提高了图像配准 的速度。试验结果表明本文所述指纹采集方法优于平面按捺采 集，对外界光照的变化、图像噪声具有很好的鲁棒性，在作者所 ４试验结果 在Ｃｅｌｅｒｏｎ ＣＰＵ １．８０ ＧＨｚ，ＲＡＭ ２５６ ＭＢ的ＰＣ机上，使用 Ｗｉｎｄｏｗｓ ＸＰ操作系统，以２０帧／ｓ的采集速率，实现了滚动按 捺指纹图像采集的功能，效果如图６所示。 ■■ 在实验室的指纹建库中得到了很好的应用，有一定的实用价 值。（收稿日期：２００７年１月） 参考文献： ［１】余采霏．生物辨识技术不容错过的新兴产业［Ｊ１ｌ电子技术，２００６（１）： 图６指纹拼接图 １５—２Ｏ． 同时以食指为例将该指纹采集方法与平面按捺作了比较， ［２】Ｈｅ Ｄｉ，Ｒｏｎｇ Ｇａｎｇ．Ｉｍａｇｅ ｍｏｓａｉｃｋｉｎｇ ａ￣ｏｒｉｔｈｍ ｆｏｒ ｒｏｉｌｅｄ ｆｉｎｇｅｒ－ 结果如表１所示，其中有效面积比指前景面积比。从表１可以 ｐｒｉｎｔ ｃｏｎｓｔｒｕｃｔｉｏｎ［Ｊ］．Ｔｓｉｎｇｈｕａ Ｓｃｉｅｎｃｅ ａｎｄ Ｔｅｃｈｎｏｌｏｇｙ，２００２，７（３）： ３１７—３２１． 看出，滚动按捺采集优于平面按捺采集，指纹特征点个数的增 ［３】Ｃｈｏｉ Ｋ，Ｃｈｏｉ‘Ｈ．Ｆｉｎｇｅｒｐｒｉｎｔ ｍｏｓａｉｃｋｉｎｇ ｂｙ ｒｏｉｌｉｎｇ ａｎｄ ｓｌｉｄｉｎｇ［Ｃ］／／ 多势必会提高指纹匹配的性能。通过大量试验证明：本文所设 Ｐｒｏｅ ｏｆ Ａｕｄｉｏ—－ａｎｄ Ｖｉｄｅｏ—－ｂａｓｅｄ Ｂｉｏｍｅｔｒｉｅ Ｐｅｒｓｏｎ Ａｕｔｈｅｎｔｉｃａｔｉｏｎ 计的指纹拼接方法，由于采用了背景自适应更新、双阈值判决 （ＡＶＢＰＡ），Ｒｙｅ Ｂｒｏｏｋ，ＮＹ，２００５，３５４６：２６０—２６９． 技术，对外界光照变化、图像噪声具有很好的鲁棒性；采用改进 【４１张亮．指纹图像传感器技术关键及发展趋势…．传感器技术， 表１两种采集方法的比较 ２００５，２４（９）：１—３． ［５】任观就，张永林．实时视频图像捕获的实现方法【Ｊ１．计算机工程， ２００２，２８（８）：２６８—２７０． 【６】林喜荣，苏晓生，丁天怀．Ｇａｂｏｒ滤波器在指纹图像处理中的应用［Ｊ１． 仪器仪表学报，２００３，２４（２）：１８３—１８６． （上接１８６页） 参考文献： 从计算结果上看，所有的产品几乎都是在最小生产时间的 ［１１常俊林，张春慨，邵惠鹤．求解一类并行多机调度问题的混合启发式 机器上生产，也就是说，机器都是在最大能力生产，因此ＰＧＡ 得到的最优调度方案比较合理，满足企业的实际调度需求。 算法『Ｊ１．计算机仿真，２００４，２１（３）：１２１—１２３． ｆ２】刘民，吴澄．用遗传算法解决并行多机调度问题『ＪＪ－系统工程理论与 ６结束语 实践，１９９８，１９（１）：１４—１７． 本文针对家纺企业的带特殊工艺约束拖后调度问题，提出 ［３１王莉，李大卫，王梦光．交货期窗口下的并行机调度问题的遗传算 了一个基于向量编码的并行遗传算法。从实验结果可以看出， 法ｆＪ１．系统工程学报，２００２，１７（１）：４５—４９． 此算法收敛速度快，能有效地解决本文提到的这类家纺企业拖 【４１宋存利，时维国，黄明．遗传算法在并行多机调度问题中的应用［Ｊ１’ 后调度问题，并能较好地适应解大规模的这类企业调度问题的 大连铁道学院学报，２００４，２５（２）：４２—４５． 需要，且生成的调度方案的质量比较优化，有着较好的并行效 ［５】高家全，王雨顺＿解并行多机提 拖后调度问题的并行遗传算法［Ｊ１ ．率。为更好地解决家纺企业车间调度问题，下一步将针对带特 计算机工程与应用，２００６，４２（２０）：１０—１２． 殊工艺约束条件下成本最小、提前胞后惩罚最小等多目标调 ［６】汪定伟，唐加福，黄敏．遗传算法与工程设ｉ十【Ｍ】．北京：科学出版社， 度问题进行深入的探讨。（收稿１３期：２００７年４月） ２Ｏｏｏ （上接１９８页） ［４】Ｚｈａｎｇ Ｌ，Ｚｈｅｎｇ Ｂ，Ｙａｎｇ Ｚ．Ｃｏｄｅｂｏｏｋ ｄｅｓｉｇｎ ｕｓｉｎｇ ｇｅｎｅｔｉｃ ａｌｇｏ— 于识别的码字数，从而提高识别效率。类别特征的优化以及基 ｒｉｔｈｍ ａｎｄ ｉｔｓ ａｐｐｌｉｃａｔｉｏｎ ｔｏ ｓｐｅａｋｅｒ ｉｄｅｎｔｉｆｉｃａｔｉｏｎ ＩＪＪ．Ｅｌｅｃｔｒｏｎｉｃｓ 于此类特征的抗噪声说话人识别方法的研究将是进一步的工 Ｌｅｔｔｅｒｓ，２００５，４１（１０）． 作。（收稿１３期：２００７年１月） ［５】王炳锡，屈丹，彭煊．实用语音识别基础【ＭＪ．北京：国防工业出版社， ２ｏ０５． 参考文献： ［６】Ｋｉｎｎｕｎｅｎ Ｔ Ｓｐｅｃｔｒａｌ ｆｅａｔｕｒｅｓ ｆｏｒ ａｕｔｏｍａｔｉｃ ｔｅｘｔ—ｉｎｄｅｐｅｎｄｅｎｔ ｓｐｅａｋ－ ［１ Ｊ韩纪庆，张磊，郑铁然．语音信号处理【Ｍ】．北京：清华大学出版社， ｅｒ ｒｅｃｏｇｎｉｔｉｏｎ［Ｄ１．Ｕｎｉｖｅｒｓｉｔｙ ｏｆ Ｊｏｅｎｓｕｕ，Ｄｅｐａｒｔｍｅｎｔ ｏｆ Ｃｏｍｐｕｔｅｒ ２００４． Ｓｃｉｅｎｃｅ，２００３ ［２】张庆芳，赵鹤鸣．基于改进ＶＱ算法的文本无关的说话人识别［Ｊ１．计 ［７］ｈａｋｕｒａ Ｆ Ｍｉｎｉｍｕｍ ｐｒｅｄｉｃｔｉｏｎ ｒｅｓｉｄｕａｌ ｐｒｉｎｃｉｐｌｅ ａｐｐｌｉｅｄ ｔｏ ｓｐｅｅｃｈ 算机工程与应用，２００６，４２（１０）：６５—６８． ｒｅｃｏｇｎｉｔｉｏｎ［Ｊ］．ＩＥＥＥ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ａｃｏｕｓｔｉｃｓ，Ｓｐｅｅｃｈ，ａｎｄ Ｓｉｇｎａｌ ［３】Ｋｉｎｎｕｎｅｎ Ｔ，Ｋａｒｐｏｖ Ｅ，Ｆｒａｎｔｉ Ｐ．Ｒｅａｌ—ｔｉｍｅ ｓｐｅａｋｅｒ ｉｄｅｎｔｉｉｆｃａｔｉｏｎ Ｐｒｏｃｅｓｓｉｎｇ，１９７５，２３（１）：６７－７２． ａｎｄ ｖｅｒｉｉｆｃａｔｉｏｎＩＪ】．ＩＥＥＥ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ａｕｄｉｏ，Ｓｐｅｅｃｈ，ａｎｄ Ｌａｎｇｕａｇｅ 【８】张炜，胡起秀，吴文虎．距离加权矢量量化文本无关的说话人识 Ｐｒｏｃｅｓｓｉｎｇ，２００６，１４（１）：２７７—２８８． 别『Ｊ１＿清华大学学报：自然科学版，１９９７，３７（３）：２０—２３．
