logo资料库

论文研究-车间作业调度(JSSP)技术问题简明综述.pdf

发布时间：2022-05-30 发布人：admin 分类：说明书 资料大小：0.19M 资料格式：pdf 举报 版权申诉
第1页 / 共7页
第2页 / 共7页
第3页 / 共7页
第4页 / 共7页
第5页 / 共7页
第6页 / 共7页
第7页 / 共7页
资料共7页，全文预览结束
    2 2 2 2 2 　2003 年 1 月 文章编号: 1000 6788 (2003) 01 0049 07 系统工程理论与实践 第 1 期　 车间作业调度 (J SSP) 技术问题简明综述 (1. 北方交通大学机电学院, 北京 100044; 2. 中国科学院自动化研究所, 北京 100080) 王书锋1, 邹益仁2 摘要: 　介绍了车间作业调度技术问题的理论、算法分类、特点及一般框架 为两类: 最优化方法和近似 展和存在的问题, 并指明了将来的发展方向 关键词: 　车间作业调度问题; 调度技术; 调度算法; 最优化; 启发式 中图分类号: 　T P29　　　　　　　　文献标识码: 　A 　　　 启发式方法, 对各种算法逐一分析比较 将 JSSP 问题的研究方法分 总结了近年来该研究领域取得的进 T echn iques fo r the Job Shop Schedu ling P rob lem : a Su rvey (1. Co llege of M echan ical & E lectrical Engineering, N o rthern J iao tong U n iversity, B eijing 100044, Ch ina; 2. A u tom ation, Ch inese A cadem y of Sciences, B eijing 100080, Ch ina) In stitu te of W AN G Shu feng1, ZOU Y i ren 2 Abstract: 　 T h is p ap er aim s to p rovide a concise su rvey of schedu ling theo ries concern ing job shop schedu ling p rob lem by dealing w ith classification of related algo rithm s, characteristic and general fram e w o rk of JSSP. T he research m ethods are divided in to tw o classes: the op tim ization and the heu ristics. T he m ethods under each app roach are analyzed and com p ared w ith the o thers. A t last, p rob lem s, w h ich need fu rther investigating and po ssib le research direction s, are po in ted ou t. Key words: 　JSSP; schedu ling techn iques; schedu ling algo rithm s; op tim ization; heu ristic 1　引言 生产调度是 C IM S 研究领域生产管理的核心内容和关键技术, 车间作业调度问题 (J SSP) 是最困难的 约束组合优化问题和典型的 N P 难问题, 其特点是没有一个有效的算法能在多项式时间内求出其最优 解 1, 2 现代经济日益强化的竞争趋势和不断变化的用户需求要求生产者要重新估价生产制造策略, 如更 短的产品生产周期和零库存系统等, 而 J SSP 生产环境最适宜满足现有经济和用户的需求 3 利用有限的 资源满足被加工任务的各种约束, 并确定工件在相关设备上的加工顺序和时间, 以保证所选择的性能指标 最优, 能够潜在地提高企业的经济效益, J SSP 具有很多实际应用背景, 开发有效而精确的调度算法是调度 和优化领域重要的课题 研究 J SSP 问题最初主要采用最优化方法, 但计算规模不可能很大, 且实用性差 近年来, 基于生物学、物理学、人工智能、神经网络、计算机技术及仿真技术的迅速发展, 为调度问题的研究 开辟了新的思路 本文根据 J SSP 问题的大量文献, 对研究理论与方法进行系统的分类并介绍这一领域的 最新进展, 讨论进一步的研究方向 2　JSSP 问题的一般框架 2. 1　问题描述 J SSP 问题可描述为: m 台机器 (用集合M = {M j}m j = 1表示) 加 n 工个工件 (用集合 J = {J i}n i= 1表示) , 每 收稿日期: 2001 资助项目: 国家“九·五”攻关项目 (97 02 07 562 01 05) 　　作者简介: 王书锋 (1966- ) , 女, 河南郑州人, 讲师, 博士, 研究方向: 智能生产调度与优化理论 © 1995-2005 Tsinghua Tongfang Optical Disc Co., Ltd. All rights reserved.
    Ù Ù Λ 2003 年 1 月 Φ Φ 05 系统工程理论与实践 个工件包含由多道工序组成的一个工序集合 定的时间内每个机器只能加工一个工件, 并且每个工件只能由一台机器处理 制, 工序不允许中断; 要求在可行调度中确定每个工序的开始时间 sij , 使总完工时间 Cm ax最小, 即 C m in (Cm ax) = m in{m ax (sij + tij ) : 问题. 工件有预先确定的加工顺序, 每道工序的加工时间 tij, 在给 不同工件的加工顺序无限 m ax = J i∈J , M j ∈M }, 求解满足以上条件的工件加工顺序即构成 J SSP 调度 流水作业调度问题 (FSSP) 是 J SSP 问题的特殊形式 (即所有工件有相同的加工工序) 此外目标函数 可选取等待时间、流程时间和延期时间的平均值或者最大值等, 或多个目标组合形成的多目标问题 2. 2　JSSP 的模型表示 2. 2. 1　整数规划 ( IP) 模型 整数规划模型由B aker 4 提出, 需要考虑两类约束: 工件工序的前后约束和工序的非堵塞约束 和 cjk分别表示工件 j 在机器 k 上的加工时间和完工时间 用 tjk 如果机器 h 上的工件加工工序先于机器 k (用 J h J k 1, J h 0, 其他 , J k 表示) , 则有关系式 cjk- tjk cjh; 反之, 如果 J k J h, 有 cjh- tjh cj k 定义指示系数 a ihk = x ij k = i 先于 j 到达机器 k 1, 0, 其他 ,M 为一个大数, 则工序的前后约束表示为 cik- tik+ M (1- a ihk) cih: 工序的 非阻塞约束表示为: cj k- cik+ M (1- x ijk) 以表示为 tj k, i, j = 1, 2, …, n; k = 1, 2, …, m , 以 Cm ax为目标的 IP 模型可 m in m ax m n 1 1 k i {cik} s. t. cik - cj k - cik tik + M (1 - cik + M (1 - 0, 　a ihk, x ijk = 0, 1　i, j = 1, 2, …, n; h, k = 1, 2, …, m a ihk) x ijk) cih tjk 　　 如果以平均流程时间为目标函数, 可以改成m in 由V an H u lle 5 给出: M > 2. 2. 2　线性规划 (L P) 模型 n m i= 1 k= 1 tik - m in ( tik) 1 n n i= 1 m ax 1 m k {cik} 大数M 在可行区域范围内的取值 A dam s 提出的 L P 模型 6 用集合 N = {0, 1, 2, …, n}表示工序, 0 和 n 表示虚设的起始和完成工序;M 是机器集合; E k 是机器 k 上加工的工序对集合, 加工时间 d i 是确定的, 工序的起始时间 ti 是优化变量, 则 J SSP 问题的L P 模型表示为: m in tn s. t. tj - tj - ti ti d i, 　 ( i, j ) ∈A d i　 或 　ti - tj ti 0, 　 ( i, d j j ) ∈ E k, k ∈M 2. 2. 3　图模型 J SSP 的非连接图模型 G = (N , A , E ) 由 B alas 提出 7 , N 包含代表所有工序的节点, A 包含连接同一 工件的邻接工序的边, E 包含连接同一机器上加工工序的非连接边, 非连接边可以有两个可能方向 调度 过程将固定所有非连接边的方向, 以确定同一机器上工序的顺序, 并采用带有优先箭头的连接边取代非连 接边 3　JSSP 的研究方法 通过对大量文献的分析将 J SSP 的研究方法分为两大类: 最优化方法和近似 最优化方 法主要包括混合整数线性规划 (M IL P)、分枝定界 (B &B ) 法以及拉氏松弛法等; 近似 启发式最初是由于计 算量小并且算法易实现而引入 J SSP 问题的 6, 7 , 主要包括优先分派规则 (PDR s)、人工智能 (A I)、神经网 启发式方法 © 1995-2005 Tsinghua Tongfang Optical Disc Co., Ltd. All rights reserved.
    Λ 车间作业调度 (JSSP) 技术问题简明综述 Λ 15 第 1 期 络 (NN ) 及邻域搜索法 (N S) , 邻域搜索法又包括禁忌搜索 (T S)、遗传算法 (GA ) 和模拟退火 (SA ) 等可以称 之为亚启发式 (M eta 3. 1　最优化方法 heu ristic) 的近似优化方法 最优化方法是能够产生一个精确最优解的方法, John son 最早提出的针对 (n son 规则 8 , 虽然是针对流水作业的求解方法, 但它对以后的研究有很大的影响 时间算法求解 2 J 经典调度理论的基础 F m ax) 问题的 John 2 此后相继有利用多项式 11 等特殊的 J SSP 问题, 这些研究奠定了 10 和 J 2 9 , J 2 j = 1 Cm ax Cm ax Cm ax m F J 2 在 20 世纪 60 年代, 针对整数规划问题的求解, 提出利用更加复杂的数学结构消除隐含非最优解的搜 对一个 n×m 的 J SSP 索空间以提高搜索效率的枚举算法, 分枝定界法 (B &B ) 在理论研究上有很大成果 70 年代后侧重计算复 问题有 (n! ) m 种可能的解, 因此大规模问题用完全枚举法在计算上是不可能的 12 Cm ax三种情况都是 N P 难问 杂性方面的研究, L en stra 等 13 证明了 3 B alas 7 最早提出 J SSP 问题的 B &B 算法, 此后 Carlier 等 14 基于 J ack son 15 的剩余总加工时间最长 题 为克服数学表示和软件方法的局限性, 近期 (MW R ) 规则提出预占先调度 (J PS) , 取得了较好的结果 D avis 等 16 提出基于数学规划的分解策略, 将调度问题分解为多个子问题, 分别考虑各子问题及其限制, 提高了计算能力 3. 2　近似 启发式方法 3. 2. 1　优先分派规则 Cm ax和 J 3 Cm ax, J 2 3 3 2 J J J 最早的分派规则由 J ack son 15 和 Sm ith 17 等提出, J SSP 的分配规则有 SPT (最短加工时间)、L PT (最 长加工时间)、MW R (剩余总加工时间最长)、LW R (剩余总加工时间最小)、M O R (剩余工序数最多)、LO R (剩余工序数最小)、EDD (最早交货期) 和 FCFS (选择同一机器上工件队列中的第一道工序) 等 Pan w alkar 等 18 通过性能指标对 113 个分派规则归类总结,W u 19 把调度规则分为三大类, 即同作业信息相关 的优先级规则、优先级规则的组合和切换以及加权规则 优先分派规则的近似优化方法, 关键在于如何针 从各规则的优化效果看, SPT 能够减小所有作业的平均流程时间, 对给定问题的性能, 选择最好的规则 EDD 用于优化最大延期相关的目标 对规则之间的切换及由此产生的问题 (如出错修复) 是近期活跃的研 究领域 3. 2. 2　人工智能技术 80 年代出现的人工智能和专家系统在调度研究中占据重要地位, 可以产生比优先规则更复杂的基于 对整个调度系统的启发式, 并能从特殊数据结构中获取大量信息, 缺点是计算比较耗时 IS IS 20 是最早基 于A I 技术解决特定 J SSP 的专家系统之一, 使用约束指导的搜索方法, 其目标约束基于交货期和在制品, IS IS 分为三层结构, 分别为选择订单、能力分析、执行调度, 同时加入重 把资源的处理能力作为物理约束 对大规模问题限于单个专家系统的有限知识和能力, 加入资源代理、任务代理 构和修改调度的学习功能 及代理间的协作机制, 近期出现了分布式调度系统 21 A I 技术对如何协调各代理机制, 目前还没有统一 的设计和指导思路, 对作业调度的集中化和分散化思想还在讨论之中 3. 2. 3　神经网络方法 神经网络应用于调度问题已有十几年的历史, 利用指导学习神经网络找到系统输入、输出之间的关 系, 输入特性包含作业特征 (如数量、路径、交货期和处理时间等) , 输出为相关排序和性能指标 目前应用 最多的是 B P 网, R abelo 22 针对不同的到达模式、过程计划和程序排序提出使用后增值神经网解决 J SSP 问题, 针对由能量函数定义的基于松弛模型的神经网提出的 Hop field 网解决了一类经典的调度问题 23 由于计算时产生大量不可行解且计算时间较长, NN 解决实际调度问题的效率不高, 而指导学习神经网试 图通过训练类型找到输入输出之间的关系, 随着问题规模的增大, 网络的规模也急剧增大 3. 2. 4　邻域搜索方法 求解 J SSP 的亚启发式方法是基于邻域搜索策略发展起来的 24, 25 , 启发式并不企图在多项式时间内 求得最优解, 而是在计算时间和调度效果上进行折衷 下面是三种有代表性的亚启发式: 1. 模拟退火 (SA ) © 1995-2005 Tsinghua Tongfang Optical Disc Co., Ltd. All rights reserved.
    Λ Λ Λ 25 系统工程理论与实践 2003 年 1 月 SA 是基于M en te Carlo 迭代求解的一种全局概率型搜索算法, 是一种串行优化算法, 其收敛性要求 初温应足够高, 使解空间各状态能以几乎相同的概率出现 V an L aarhooven 等 26 提出对于 J SSP 问题, 邻 域函数的重要标志是相邻关键操作工序处理顺序的改变, 且必须服从在同一机器上处理的工序条件 Ko lonko 27 证明标准的 J SSP 的邻域具有非对称性, 且由于 SA 的弱收敛性, 提出了在 SA 基础上结合 GA 文献 28 利用 SA 以一定的概率接受较差个体的性质, 结合遗传算法而改进了选择机制, 的混合启发式 使收敛速度有所提高 近期在调度问题研究领域的一大趋势是将不同的邻域搜索法结合形成混合启发式 2. 禁忌搜索 (T S) T S 是 G lover 29 提出的模拟智能过程的一种具有记忆功能的全局逐步优化算法, 对变动的排序在其 可行解的所有空间中进行搜寻 通过设置禁忌表, 避免陷入局部最优或重复过去的搜索, 利用中、长期的存 储机制进行强化和多样化搜索, 对 J SSP 问题 L aguna 等 30, 31 提出三个基于简单移动的 T S 排序策略 T aillard 32 结合加速搜索策略防止重复计算工序的开始时间, 提出一种快速估值策略, 但只对半活动调度 有效 而N ow ick i 等 33 考虑到解的质量和计算时间, 结合 T aillard 32 的 T S 算法, 在V an L aarhooven 26 邻 域的基础上, 把单个关键路径分割为不同块应用于严格限制的邻域中, 计算效率大大提高 3. 遗传算法 (GA ) 遗传算法是 Ho lland 基于自然遗传进化的绝对模型提出的并行搜索机制 34 , GA 的 5 个要素是编码、 由于对 J SSP 问题要考虑工序的前后约束和非堵塞约束, 使 适应值函数、初始种群、遗传算子和参数设置 如果编码不当, 会在遗传算子操作时产生不可行解, 失去了交叉或变异算 得染色体的编码表示非常重要 子的有效性 Cheng 等 35 把编码表示分为两类共 9 种, 分别是直接的方法 (基于工序、基于工件、基于工件 对关系、基于完成时间和基于随机键表示法) 和间接的方法 (基于优先规则、基于优先表、基于非连接图和 基于机器的表示法) D avis 36 首先基于优先表的间接编码表示求解 J SSP, Falkenauer 等 37 则利用把工序 编码为字符串的方法 T am ak i38 基于非连接图的间接编码, 其染色体用非连接边顺序表的二进制串表示 B ean 39 采用随机键表示法, 每个基因由两部分组成: 整数部分表示机器的分配, 分数部分以非减顺序排列 的 (0, 1) 之间的随机数来确定每个机器上的工序 曹承煜等 40 提出结合拉氏松弛法的遗传算法, 能够克服 纪树新等 41 对 J SSP 应用连锁基因编码法与遗传进化算子相结合, 显示算法的可行 震荡并减小计算量 性 GA 对初始种群很敏感, 交叉 研究表明, 随机产生的初始种群不如用其他启发式 (如 SA ) 算子和编码表示对算法结果会产生不利影响 产生的初始种群好, 而修复非法染色体相对容易些, 需要对遗传算法进行改进 调度问题中使用的 GA 技 术, 大多只强调了遗传算法的独立使用, 限制了问题的复杂性 3. 2. 5　其他理论和技术 王海英等 42 采用定界遗传算法与逆序调度策略, 在收敛速度上有所提高 从 J SSP 的研究发展来看, 理论及应用上都取得了一定的进展, 出现了一些新的研究方法和技术: 1) 当系统有不确定的处理时间或调整时间时, 通过模糊集理论建模和求解的模糊逻辑方法 G rabo t 等 43 对多目标问题结合分派规则使用模糊逻辑准则, 而 K rucky 44 提出对产品混合生产线的最小化调整 时间的模糊逻辑 2) 反应式调度 (R eactive Schedu ling) 是系统因突发事件对一个已完成的调度的修复能力 45 突发事 反应式调度已成为生产调度研 件包括紧急订单和资源中断等, 出现突发事件时要重调度 ( reschedu ling) 究中的热点之一, 但其技术还不够成熟 3) 考虑作业提前 拖期费用的非正规性能指标的作业排序是基于准时制 (J IT ) 的生产管理技术, 为 J SSP 理论研究开拓了一个崭新的研究领域 4) 在调度理论同实际生产结合的应用中, E liyahu 46 提出基于同步制造的限制理论 (T heo ry of Con strain ts) , 即在同市场需求相联系的生产过程中试图迅速而灵活地转移物资的系统方法, 其核心是存在少 量关键限制, 调度即对这些限制操作的计划排序 限制理论是已有成功的应用于调度系统的例子 47 4　问题讨论与展望 分析 J SSP 调度问题近 40 年的应用和发展现状, 有丰硕的成果同时也暴露出许多尚待解决的问题 © 1995-2005 Tsinghua Tongfang Optical Disc Co., Ltd. All rights reserved.
    2 2 2 35 2 2 2 2 2 第 1 期 车间作业调度 (JSSP) 技术问题简明综述 但近似 启发式算法的明显优势在于: 启发式算法相对比较简单; 计算效率高, 算法灵活 与最优化算法相比, 近似 启发式算法有明显不足之处, 即有可能出现所产生的解比全局最优解差很多的情况, 而且差 多变 因此, 合理的计算时间和所求出的解的最优性就成为衡量启发式算法性能的标准 的程度总是不够明确 邻域搜索以一定的 单独使用一种启发式不如两种启发式结合起来形成的混合启发式算法取得的结果好 概率接受劣解, 从而逃离局部最优, 但其主要缺点是需要多步实现, 如何选择从局部到全局最优的邻域结 GA 的停止条件设置为一个大数时, 会出现达到 构, 使其具有强化性和多样性的搜索机制这一点很重要 最优而算法不能停止的问题, 关键是如何协调两者关系 对 A I 技术和神经网络, 如何通过内部的并行分 布处理能力快速找到搜索空间而减小计算量的大规模问题有待进一步研究 作者认为可从以下几个方面 进行拓展研究: 1. J SSP 问题的一般框架、模型及研究方法对解决生产调度和其他复杂的组合优化问题是有借鉴的, 应展开对 m > n 和m n 条件下更具一般性 J SSP 问题的研究 2. 需要对局部搜索算法的限制条件以及加强收敛性和计算速度的进一步研究 3. 大规模问题作为限制性 J SSP 最优化问题仍然是一个挑战, 虽然启发式算法能较好解决大规模问 题, 但应从理论上更深入研究其收敛性及其有限时间性问题 4. 实际的生产环境是动态的, 具有变化的结构和目标, 还存在调度的中断 产过程, 使等待时间和在制品量增加, 设备利用率、产品质量及批处理性能降低 active schedu ling) 和在线调度的研究是今后的研究方向 如果用离线的调度指导生 因此对交互式调度 (in ter 5. 寻求新的数学工具和分析方法, 建立 J SSP 算法复杂性、收敛性的分析研究理论, 对算法的收敛速 度和优化度进行估计 5　结束语 总结 40 年来 J SSP 问题的理论及各种技术方法, 并归纳出该领域已有的分散成果和各算法的技术应 作者认为今后在进行各种算法理论与应用研究的同时, 应注重统一的结构框架和研究体 今后的研究应以可应用的调 用方面的优缺点 系, 吸收交叉学科的成果, 引入新的研究工具, 进而开发新的混合策略或算法 度系统为重点, 使研究朝着真正有利于实际生产这一最终目的方面发展 参考文献: 1 　Garey M , John son D , Seth i R. T he com p lex ity of flow shop and job shop schedu ling [J . M athem atics of O p eration s R esearch, 1976, 1: 117- 129. 2 　B lazew icz J , Ecker K H , Schm idt G, et al. Schedu ling in Com p u ter and M anufactu ring System s[M . Second R evised Edition. B erlin: Sp ringer V erlag, 1996. 3 　Jain A S. A M u lti L evel H yb rid F ram ew o rk fo r the D eterm in istic Job Shop Schedu ling P rob lem [D . D undee, Sco t land, U K: U n iversity of D undee, 1998. 4 　B aker K. 5 　V an H u lle M M. A goal p rogramm ing netw o rk fo r m ixed in teger linear p rogramm ing: a case study fo r the job In troduction to Sequencing and Schedu ling[M . N ew Yo rk: John W iley & Son s, 1974. shop schedu ling p rob lem [J . In ternational Jou rnal of N eu ral N etw o rk s, 1991, 2 (3) : 201- 209. 6 　A dam s J , B alas E, Q aw ack D. T he sh ifting bo ttleneck p rocedu re fo r job shop schedu ling[J. In ternational Jou rnal of F lex ib le M anufactu ring System s, 1987, 34 (3) : 391- 401. 7 　B alas E. M ach ine sequencing via disjunctive grap h s: an im p licit enum eration algo rithm [J . O p eration s R esearch, 1969, 17: 941- 957. 8 　John son S. O p tim al tw o and th ree stage p roduction schedu les w ith setup tim es included [J . N aval R esearch L ogis tics Q uarterly, 1954, 1: 61- 68. 9 　A kers S B. A grap h ical app roach to p roduction schedu ling p rob lem s[J . O p eration s R esearch, 1956, 4: 244- 245. 10 　Jack son J R. A n ex ten sion of john son’s resu lt on job lo t schedu ling[J . N aval R esearch L ogistics Q uarterly, 1956, 3 (3) : 201- 203. 11 　H efetz N , A diri I. A n efficien t op tim al algo rithm fo r the tw o m ach ines un it tim e job shop schedu le length p rob lem © 1995-2005 Tsinghua Tongfang Optical Disc Co., Ltd. All rights reserved.
    2 2 2 2 2 2 2 45 系统工程理论与实践 2003 年 1 月 [J. M athem atics of O p eration s R esearch, 1982, 7: 354- 360. 12 　F rench S. Sequencing and Schedu ling - W iley & Son s, 1982. N ew Yo rk: John an In troduction to the M athem atics of the Job Shop [M . E llis Ho rw ood, 13 　L en stra J K, R innooy Kan A H G, B rucker P. Com p lex ity of m ach ine schedu ling p rob lem s[J. A nnals of D iscrete M athem atics, 1977, 7: 343- 362. 14 　Carlier J , P in son E. A p ractical u se of Jack son’s p reem p tive schedu le fo r so lving the job shop p rob lem [J. A nnals of O p eration s R esearch, 1990, 26: 269- 287. 15 　Jack son J R. Schedu ling a P roduction L ine to M in im izeM ax im um T ardiness, R esearch R epo rt 43, M anagem en t Sci ence R esearch P ro jects[R . L o s A ngeles, U SA : U n iversity of Califo rn ia, 1955. 16 　D avis W , Jones A. A real tim e p roduction schedu ler fo r a stochastic m anufactu ring environm en t[J . In ternational Jou rnal of Com p u ter In tegrated M anufactu ring, 1988, 1 (2) : 101- 112. 17 　Sm ith W E. V ariou s op tim izers fo r single stage p roduction [J . N aval R esearch L ogistics Q uarterly, 1956, 3: 59- 66. 18 　Panw alkar S S, 19 　W u D. A n Exp ert System s A pp roach fo r the Con tro l and Schedu ling of F lex ib le M anufactu ring System s[D . Penn Iskander W. A su rvey of schedu ling ru les[J. O p eration s R esearch, 1977, 25 (1) : 45- 61. sylvan ia State U n iversity, 1987. 20 　Fox M S, Sm ith S F. IS IS: A know ledge based system fo r facto ry schedu ling[J. Exp ert System , 1984, 1 (1) : 25 - 49. 21 　Parunak H , Irish B , K indrick J , et al. Gractal acto rs fo r distribu ted m anufactu ring con tro l[A . P roceedings of the Second IEEE Conference on A rtificial In telligence A pp lication s[C , 1985, 653- 660. 22 　R abelo L. H yb rid A rtificialN eu ralN etw o rk s and Know ledge B ased Exp ert System s A pp roach to F lex ib leM anufac tu ring System Schedu ling[D . U n iversity of M issou ri Ro lla, 1990. 23 　Hop field J , T ank D. N eu ral com p u tation of decision s in op tim ization p rob lem s[J . B io logical Cybernetics, 1985, 52: 141- 152. 24 　Grabow sk i J , N ow ick i E, Zdrzalka S. A b lock app roach fo r single m ach ine schedu ling w ith release dates and due dates[J. Eu rop ean Jou rnal of O p erational R esearch, 1986, 26 (2) : 278- 285. 25 　N ow ick i E, Sm u tn ick i C. A fast taboo search algo rithm fo r the job shop p rob lem [J. M anagem en t Science, 1996, 42 (6) : 797- 813. 26 　V an L aarhooven P J M. , A arts E H L , L en stra J K. Job shop schedu ling by sim u lated annealing [J . O p eration s R esearch, 1992, 40 (1) : 113- 125. 27 　Ko lonko M. Som e new resu lts on sim u lated annealing app lied to the job shop schedu ling p rob lem [J . Eu rop ean Jou rnal of O p erational R esearch, 1999, 113: 123- 136. 28 　翁妙凤. 解 Job 29 　Glover F. T abu search - Part I[J. O R SA Jou rnal on Com p u ting, 1989, 1 (3) : 190- 206. 30 　L aguna M , B arnes J W , Glover F. T abu search m ethods fo r a single m ach ine schedu ling p rob lem [J. shop 调度问题的混合模拟退火进化规划[J. 信息与控制, 1999, 28 (2) : 81- 84. Jou rnal of In telligen t M anufactu ring, 1991, 2: 63- 74. 31 　L aguna M , B arnes J W , Glover F. In telligen t schedu ling w ith tabu search: an app lication to job s w ith linear delay p enalties and sequence dep enden t setup co sts and tim es[J . Jou rnal of A pp lied In telligence, 1993, 3: 159- 172. 32 　T aillard E. Parallel taboo search techn iques fo r the job shop schedu ling p rob lem [J . O R SA Jou rnal on Com p u ting, 1994, 16 (2) : 108- 117. 33 　N ow ick i E, Sm u tn ick i C. A fast taboo search algo rithm fo r the job shop p rob lem [J. M anagem en t Science, 1996, 42 (6) : 797- 813. 34 　玄光男, 程润伟. 遗传算法与工程设计[M . 北京: 科学出版社, 2000. 35 　Cheng R , Gen M , T su jim u ra Y. A tu to rial su rvey of job shop schedu ling p rob lem s u sing genetic algo rithm s I. rep resen tation [J. Com p u ters & Indu strial Engineering, 1996, 30 (4) : 983- 997. 36 　D avis L. Job shop schedu ling w ith genetic algo rithm [A . Grefen stette J J. P roceedings of the 1st In ternational Conference on Genetic A lgo rithm s and T heir A pp lication s, P ittsbu rgh [C. PA , U SA , L aw rence, E rlbaum , 1985, 136- 140. © 1995-2005 Tsinghua Tongfang Optical Disc Co., Ltd. All rights reserved.
    第 1 期 车间作业调度 (JSSP) 技术问题简明综述 55 37 　Falkenauer E, Bouffou ix S. A genetic algo rithm fo r the job shop [A . P roceedings of the IEEE In ternational Con ference on Robo tics and A u tom ation, Sacram en to [C , Califo rn ia, U SA , 1991, 824- 829. 38 　T am ak i H , N ish ikaw a Y. A p aralleled genetic algo rithm based on a neighbou rhood m odel and its app lication to the shop schedu ling[A . M anner, R and M anderick B. PPSN ’2 P roceedings of the 2nd In ternationalW o rk shop on job Parallel P rob lem So lving from N atu re, B ru ssels, B elgium , 1992, 573- 582. 39 　B ean J. Genetic algo rithm s and random keys fo r sequencing and op tim ization [J . O R SA Jou rnal on Com p u ting, 1994, 6 (2) : 154- 160. 40 　曹承煜, 李人厚, 樊健. 车间调度算法的研究开发[J . 控制理论与应用, 2000, 17 (1) : 31- 34. 41 　纪树新, 钱积新, 孙优贤. 遗传算法在车间作业调度中的应用[J. 系统工程理论与实践, 1998, 5: 34- 40. 42 　王海英, 王凤儒, 柳崎峰. 用定界遗传算法解有交货期的非标准 Job shop 调度问题 [A . P roceedings of the 3th W o rld Congress on In telligen t Con tro l and A u tom ation [C. Ch ina, 2000, 532- 636. 43 　Grabo t B L geneste. D isp atch ing ru les in schedu ling: a fuzzy app roach [J . In ternational Jou rnal of P roduction R e search, 1994, 32 (4) : 903- 915. 44 　K rucky J. Fuzzy fam ily setup assignm en t and m ach ine balancing[J. H ew lett 45 　Zw eben M , D aun B , D avis E. Schedu ling and reschedu ling w ith iterative rep air In telligen t Schedu ling[M . Zw eben Packard Jou rnal, 1994, 6: 51- 64. M , Fox M , San F rancisco, Califo rn ia: M o rgan Kaufm an, 1995, 241- 256. 46 　Go ldratt E. T heo ry of Con strain ts[M . Great B arrington, M assachu setts: N o rth R iver P ress, 1990. 47 　Go ldratt E. T he Goal[M . Great B arrington, M assachu setts: N o rth R iver P ress, 1992. (上接第 48 页) Seifo rd 函数解决多人的决策问题; 而 Cook 合, 然后用 Cook A H P 法则先解决各个准则下 的多人决策问题, 然后用 A H P 法解决多准则问题, 不过后种方法若不用 Bo rda 法给出各准则下待选技术 的的相对权重, 结果会有不同 Seifo rd Bo rda Cook 2. 第三种方法: A H P 先解决多准则选择问题后解决多人选择问题还有另一种方法 — A H P Seifo rd 函数法 该法与 加权距离法不同的是要多次全过程应用 A H P 法, 以求出每一个成员对被选方案的多准则排序, 然后用 这种方法计算量很大, 而且严格说 Cook 来它也不算是对 Cook Seifo rd 函数对个人的意见进行集结, 从而得到群体选择的结果 Seifo rd 函数的扩展, 故本文没有用其进行案例研究 Seifo rd 函数法 Cook 5　结束语 为了处理多准则的群体决策问题, 本文用两种方法对 Cook 一般说来, 不同的集结多准则及多人意见的方法, 有不同的集结规则及结果 Seifo rd 社会选择函数进行了扩展, 在扩 文中还用上述方法对广东省 IT 业 2005- 2010 年重点发展技术进行了 展中使用了Bo rda 法及 A H P 法 选择 本文的两种方法本质 相近, 在对广东省 IT 业 2005- 2010 年重点发展技术的选择的结果大同小异, 对于其它问题是否有同样的 结论还要继续研究 　　感谢　作者对岳超源、尹俊勋、祁明、毛宗源教授的帮助表示衷心的感谢! 参考文献: 1 　岳超源. 群决策讲义[M . 武汉: 华中理工大学系统工程研究所, 1990. 2 　陈王廷. 决策分析[M . 北京: 科学出版社, 1997. 3 　Saaty T L. D ecision M ak ing fo r L eaders: the A nalytic H ierarchy P rocess: fo r D ecision in Com p lex W o rld[M . RW S Pub lication, 1990. © 1995-2005 Tsinghua Tongfang Optical Disc Co., Ltd. All rights reserved.
    分享到：
    赞 收藏

    相关推荐

    资料库

    开发技术

    共收录19306份资料，累计14个分类，关注成员有19位，主要包括：Actionscript,Javascript,PHP,VB,Perl,Delphi,Python,C#,C,Java,C++,Web开发,硬件开发,其它

    热门标签

    Actionscript Javascript PHP VB Perl Delphi Python C# C Java C++ Web开发 硬件开发 其它

    最新资料