（管理科学与工程专业论文）两机器最小总误工数分组排序问题算法研究.pdf

复旦大学硕士学位论文 摘要： 成组技术在现代生产中有着广泛的应用，对分组排序问题的研究有着重要的 实际意义。本文以现代生产制造业中成组生产为实际背景，研究了类两机器分 组排序的最小总误工数问题( f 2i 黾，黾，d d mi v ) 。本文证明了此问题是 n p h a r d 问题，因此此类问题在规模较大的情况下，要用有限的资源在合理的时 间内获得最优解将比较困难。本文研究了此类问题的最优解结构和优势准则，并 着重研究了此类问题的遗传算法优化。 本文的主要创新和贡献如下： 1 最优解结构性质的提出和证明。本文提出了关于此类问题最优解结构的 一个引理和两个定理，并加以证明。为本文研究的遗传算法优化提供了 理论支持，并有助于分支定界等算法的研究。 2 优势准则的提出和证明。本文提出了此类问题的一个优势准则，可作为 分支定界算法的剪枝规则。 3 整数规划模型的提出。 4 此类问题遗传算法的提出。本文介绍了此类问题的遗传算法编码、适应 度函数及尺度变换、选择算子、交叉算子和变异算子。并用v b 语言编程 实现，给出了计算结果。 本文的研究成果在实际生产环境中具有相当的实用价值，可以应用在企业的 生产排程系统中用来解决此类问题。 关键词：成组技术、成组排序、生产排序、组合优化、分支定界、遗传算法 中图分类号：1 7 9 3 复旦大学硕士学位论文 a b s t r a c t g r o u pt e c h n o l o g yi sw i d e l yu s e di nt h em o d e mm a n u f a c t u r i n g ，s ot os t u d yt h e g r o u ps c h e d u l i n gp r o b l e m si so fg r e a tp r a c t i c a ls i g n i f i c a n c e t h i sp a p e rs t u d i e st h e t w om a c h i n e sf l o w s h o pg r o u ps c h e d u l i n gp r o b l e m ；t h eo b j e c t i v ei st om i n i m i z et h e n u m b e ro fl a t ej o b s w i t ht h r e ep a r a m e t e rm e t h o d s ，t h i sp r o b l e mc a nb en o t e d a s f 2 s s , ，s a ，d d m u i nt h i sp a p e rt h e n p h a r dp r o p e r t yo ft h i sp r o b l e mi s d e m o n s t r a t e d t h i sp a p e ra l s op r o v i d e st h r e et h e o r e m sa b o u tt h es t r u c t u r eo ft h eb e s t s c h e d u l e ，a n do n ed o m i n a n c er o l ei sa l s op r o v i d e d t h i sp a p e ra l s os t u d i e st h e h e u r i s t i ca l g o r i t h m sf o rt h i sp r o b l e m t h er e s e a r c hh a st h ef l o w i n gf o u rc o n t r i b u t i o n s ： 1 t h i sp a p e rp r o v i d e st h ep r o o fo ft h r e et h e o r e m sa b o u tt h eb e s ts o l u t i o n s s t r u c t u r e t h e s et h e r et h e o r e m ss u p p o r tt h es t u d yo ft h i sp r o b l e m sg e n e t i c a l g o r i t h ms o l u t i o n ，a n da r eh e l p f u lf o rt h es t u d yo ft h eb r a n c ha n db o u n d a l g o r i t h m 2 t h i sp a p e rp r o v i d e st h ep r o o fo fo n ed o m i n a n c em l e ，w h i c hc a nb eu s e dt o c u tb r a n c h e si nb r a n c ha n db o u n da l g o r i t h m 3 t h i sp a p e rp r o v i d e st h ei n t e g e rp r o g r a m m i n gm o d e lf o rt h i sp r o b l e m 4 t h i sp a p e rp r o v i d e st h eg as o l u t i o no f t h i sp r o b l e m t h i sg ai si m p l e m e n t e d w i t ht h ev bp r o g r a m m i n gl a n g u a g e ，t h ec o m p u t a t i o nr e s u l ti sa l s op r o v i d e d i nt h i sp a p e r t h er e s e a r c ho ft h i sp a p e ri sv a l u a b l ef o rt h ep r a c t i c a lp r o d u c t i o n t h eg as o l u t i o n c a nb eu s e di nt h ee n t e r p r i s e s p r o d u c t i o ns c h e d u l i n gs y s t e m k e y w o r d s ：g r o u pt e c h n i q u e ，p r o d u c t i o ns c h e d u l i n g ，f a m i l ys c h e d u l i n g ， c o m b i n a t i o no p t i m i z a t i o n ，b r a n c ha n db o u n d ，g e n e t i ca l g o r i t h m c l a s s i f i c a t i o nn o ：c 9 3 3 复旦大学硕士学位论文 1 绪论 1 1 引言 随着全球竞争的不断加剧和客户需求的变化，整个制造业都在重新调整自己 的生产系统。一直以来，价格和准时交货都是客户所关心的两个要素，客户期望 较低的购买价格和准时地交货。从制造企业的角度，成本控制和提高客户满意度 是企业形成自身竞争优势的重要环节。生产作业排序就是制造业降低成本和提高 客户满意的一个关键成功因子。同时，排序问题不仅仅存在于生产过程中，而且 在其他环节，例如运输、分销等物流过程中也同样存在。 在制造企业的运营管理中生产作业排序是一个基本问题，排序问题解决的好 坏直接影响着企业的运作效率和最终的客户满意程度，最终影响着企业对市场的 反应能力和竞争力。大规模定制生产计划控制理念与柔性制造系统的发展，给成 组排序的研究带来了新的生机和活力，受到了国内外学者的广泛关注。 全球化市场背景下企业所面临的市场个性化需求和现场共性化生产要求间 的矛盾，是制造企业当今面临的主要挑战。大规模定制生产计划控制理念是解决 这一矛盾的主要方法。在生产计划的整体框架中，越是靠近计划执行阶段或者说 越临近生产现场的计划控制，越需要考虑问题的细节和更多地运用定量分析的方 法。因此，制造行业生产现场作业调度与控制始终是运营管理和优化控制学科最 具挑战性的领域之一。困难之处在于生产现场作业调度涉及的变数太多以及这些 系统参数的动态变化。这使得严格的理论结果和完美的优化模型的建立几乎变得 不可能。用于研究这类问题的理论方法包括排队论( 又称随机服务系统) 和各种 各样的排序方法。历时半个多世纪的发展，排队论也只是对单阶段服务系统的简 单情形在严格的假设条件下给出了明确的解析结果，而多数已建立的生产作业排 序方法也是针对多项工作单台机器的情形。实际的生产现场作业调度问题往往面 i | 缶多台机器，多项工作的调节控制和多阶段多通道的排队网络难题。 进入2 1 世纪，随着整个制造业生产制造技术和管理理念的不断更新和演进， 企业日常所面临的生产排序问题的背景也在发生着一些根本的变化。同时，信息 技术的发展和理论研究的突破，在解决排序问题的方法论上，也有了一些不同于 以往经典排序理论的成果，在研究方向上正发生着变化。 排序问题，从关于它的第一篇文章发表( s m j o h n s o n ，1 9 5 4 ) 到现在有5 0 多年历史。从两台机器、同顺序的一个简单问题开始，到今天关于千姿百态问题 的研究；从少数几个人开始进行工作，到今天的数以千计的庞大队伍从事研究。 排序问题，作为一个研究项目，5 0 年来的发展不可谓不大，不可谓不快。其所 复旦大学硕士学位论文 以划此，土蛋是出于在生广头环中所涉及的排序问题可以说是无处不在，而排序 问题的好坏常会在经济、时问、工效等产生很大的影响。虽然在有些情况，不管 排序好坏，照样可以进行生产，但如果有好的排序方法可以采用，所产生的经济 效益则可能是令人吃惊的，不少的例子可以说明这一点。由于生产规模日愈庞大， 生产管理同愈复杂，其中自然就会出现许多新的排序问题有待解决，这就使得这 门学科r 愈得到重视，使之具有广阔的前景。 在我国，对排序问题的研究起步较晚。通过学者们的共同努力，在有关的理 论和应用方面取得了一些很好的成果，但总的说来，与国外一些先进国家相比仍 有相当大的差距。 本文就是讨论随着成组加工技术( g r o u pt e c t m o l o g y ) 在制造业的广泛应用， 很多大型制造企业所面临的一类成组排序问题( f a m i l ys c h e d u l i n gp r o b l e m s ) 的 解决方法。 成组排序问题是指在企业考虑的待排序的工作中，由于某些工作工艺上或技 术上的相似性，这些工作可以归并以一类，这些同类别的工作在同一台机器上连 续加工处理时，不需要对机器本身进行重新的安装配置。因此，机器的安装切换 时间为零或者很短，但是当不同类别的工作连续加工时，就需要相当的安装时间 ( s e t u pt i m e ) 。一个最典型的例子就是在很多工业生产过程中用到的涂漆设备。 对于需要不同着色处理的产品，涂漆设备需要进行清洗，然后才能进行不同颜色 的处理。 基于成组排序问题广泛的应用背景，本文对其一类问题的最优化算法和近似 搜索算法进行了研究。由于该类问题是n p h a r d 问题，因此，我们将研究重心 放在了搜索算法的研究上。 1 2 成组技术在制造业的应用 随着人类社会生产力的提高，人们追求个性化、特色化的思想日益普遍，整 个制造业已经进入了买方市场。作为提供人们同常生活所需各种产品的制造业， 大批量生产的产品越来越少，单件小批量的产品生产模式越来越多，约占各类机 器生产的7 6 8 5 。在社会对产品需求多样化的趋势不断延伸的情况下，传统 的生产组织模式暴露出了很多问题： 1 由于产品品类过多，导致生产计划和组织管理复杂化； 2 零件从投料到加工完成的总生产时间较长，无法适应市场需求的迅速波 动； 3 由于生产时需要频繁切换产品品类，生产准备工作量大： 复旦大学硕士学位论文 4 由于产品生产批量小，使得先进制造技术的应用受到限制； 为此，制造技术的研究者提出了成组技术的科学理论及实践方法，它能从根 本上解决生产由于品种多、产量小带来的矛盾。成组技术g t ( g r o u p t e c h n o l o g y ) 是一门生产技术科学，它研究如何识别和发掘生产活动中有关事务的相似性，并 对其进行充分利用。即把相似的问题归类成组，寻求解决这一组问题相对统一的 最优方案，以取得所期望的经济效益。 成组技术起源于前苏联。1 9 5 9 年米特洛凡诺夫发表成组加工的科学原理， 首先提出成组技术的概念和基本原理，为改变多品种小批量生产的传统生产方式 开辟了一条重要的途径。随后成组技术传入欧美和日本，并得到了进一步发展。 德国的阿亨工业大学的奥匹兹教授( o p i t z ) 曾对不同行业许多产品的零部件的 相似性作了大量的统计分析，发表了工作统计学，指出各行各业的机械产品 中相似件约占7 0 7 5 ，为在多品种小批量生产中应用g t 的可能性提供了可靠 的依据。他还领导制定了一套工作分类编码系统( 国际上称之为o p i t z 分类法 则) ，为g t 与计算机技术结合，进一步应用于产品设计和制定零件工艺奠定了 重要的基础。英国的伯尔毕齐( j l b u r b i d g e ) 教授对分析工作工艺过程的相似 性提出了工艺流程分析法，为建立成组生产单元，组织成组生产提供了有效的方 法。美国与日本将g t 与数控技术和计算机技术很好地结合，为在g t 基础上 发展c a d 、c a p p 和建设f m s 创造了必要的条件，使g t 的作用得到了充分 的发挥，对改善多品种小批量生产的经济效益作出了重要的贡献 3 3 1 。 成组技术应用于机械加工方面，乃是将多种零件按其工艺的相似性分类成组 以形成零件族，把同一零件族中零件分散的小生产量汇集成较大的成组生产量， 从而使小批量生产能获得接近于大批量生产的经济效果。成组技术将品种众多的 零件按其相似性分类以形成为数不是很多的零件族，把同一零件族中诸零件分散 的小生产量汇集成较大的成组生产量。这样，成组技术就巧妙地把品种多转化为 “少”，把生产量小转化为“大”，由于主要矛盾有条件地转化，这就为提高多品种、 小批量生产的经济效益提供了一种有效的方法。 计算机辅助制造( c o m p u t e ra i d e dm a k i n g ，简称c a m ) 的发展对成组技术的 研究也有很大的推动作用，c a m 的核心是计算机数值控制( 简称数控) ，是将计 算机应用于制造生产过程的过程或系统。通过计算机辅助编程完成生产的自动控 制，为了对制造过程进行优化，合理的生产排序是必要到。 柔性制造系统( f l e x i b l em a n u f a c t u r i n gs y s t e m ) 是在2 0 世纪6 0 年代后期诞 生和发展起来的。它综合应用了现代数控技术、计算机技术、自动化物料输送技 术 3 3 1 ，进一步发展了成组技术。 复且大学硕士学位论文 关于柔性制造系统的定义很多，权威性的定义有：美国国家标准局把f m s 定 义为：“由一个传输系统联系起来的一些设备，传输装置把工作放在其他联结装 置上送到各加工设备，使工作加工准确、迅速和自动化。中央计算机控制机床和 传输系统，柔性制造系统有时可同时加工几种不同的零件。” 国际生产工程研究协会指出“柔性制造系统是一个自动化的生产制造系统， 在最少人的干预下，能够生产任何范围的产品族，系统的柔性通常受到系统设计 时所考虑的产品族的限制。”而我国国家军用标准则定义为“柔性制造系统是由数 控加工设备、物料运储装置和计算机控制系统组成的自动化制造系统，它包括多 个柔性制造单元，能根据制造任务或生产环境的变化迅速进行调整，适用于多品 种、中小批量生产。”简单地说，f m s 是由若干数控设备、物料运贮装置和计算 机控制系统组成的并能根据制造任务和生产品种变化而迅速进行调整的自动化 制造系统。目前常见的组成通常包括4 台或更多台全自动数控机床f 加工中心与 车削中心等) ，出集中的控制系统及物料搬运系统连接起来，可在不停机的情况 下实现多品种、中小批量的加工及管理。目前反映工厂整体水平的f m s 是第一 代f m s ，日本从1 9 9 1 年开始实施的“智能制造系统”( i m s ) 国际性开发项目，属于 第二代f m s 。柔性制造技术的应用，既解决了近百年来中小批量和中大批量多 品种加工自动化的问题，亦很好地适应了产品不断迅速更新的需求。它解决了 6 0 年代以来，一直是以提高切削用量、减少切削时间，缩短或重和辅助时间为手 段，来达到提高生产率效果不理想的问题。 实用表明，柔性制造技术具有如下特点： 1 具有较高的柔性、机构性和通用性； 2 转产快、准备时间短； 3 设备利用率高，可实现无人看管2 4 小时连续工作； 4 加工质量高且稳定： 5 所需费用低； 6 相同产量占地面积是传统设备的6 0 ： 由此可见，正是由于柔性制造技术的这种高效、灵活的特性使其成为实施敏 捷制造、并行工程、精益生产和智能制造系统的基础，且应用日益广泛，己成为 整个机械制造领域的核心技术。由于这些先进制造技术的广泛应用，给企业所面 临的生产作业排序的研究带来了新的问题，本文所讨论的成组加工排序问题实际 上就是在成组技术和柔性制造系统不断得到应用的背景下所出现的。 复旦大学硕士学位论文 1 3 本文的问题定义与研究背景 本文是笔者在宝钢宽厚板车间分日生产排序项目的背景之下完成的。宝钢宽 厚板生产项目是国家级重点项目。宽厚板轧机工程作为上海宝钢集团公司宽厚板 轧机及其配套连铸工程的核心部分，由宽厚板厂及其辅助设施两大部分组成。宽 厚板厂主要由板j j 口l x ( 板坯库及加热炉) 、轧机区、冷床区、剪切线区、精整区、 特厚板处理设备、热处理线、涂漆线、磨辊间、成品库、主电室和电气室等部分 组成。为适应新的市场竞争的需要，该重点项目拟采用大规模定制的主流生产模 式和高度信息化的生产控制方式。 宝钢宽厚板车间周分日生产排序项目要求对在未来需要在宽厚板车间生产 的合同，在满足车间各关键生产设备能力、库存和工艺要求等诸多约束的前提下， 合理的安排合同生产计划，达到如期交货的目的。 本文的成组机器生产排序就是以宽厚板生产中几个关键设备为实际背景，并 进行了抽象和简化。 在宽厚板生产过程中，有两台关键设备热处理设备和涂漆机的生产有一定的 特殊性。从工程上来讲，热处理设备可以进行正火、淬火、退火和回火四种工艺， 一份合同可能需要多种热处理工艺，但是从实际生产来看，在热处理机器上频繁 的切换工艺，不仅会带来热能上的损失和对机器的损害，在现场操作上也不太可 行。因此，实际生产要求能够合理的安排各种工艺，不能过于频繁的对热处理工 艺进行调整，但是又能尽量满足各份合同的交货期。同样的情况也出现在涂漆生 产线上，在最后对合同钢板进行涂漆处理时，实际生产过程中也不能频繁的切换 涂漆颜色，因为每次切换需要对涂漆设备进行清洗，这需要花费相当的人工和时 间。因此，在安排生产排序时，应尽量安排同种颜色要求或近似颜色的合同连续 生产，同时也能尽量满足合同的交货时间要求。 从这两种情形下，抽象出来的就是本文所研究的成组排序问题。本文所研究 问题用下文介绍的三参数法表示可以表示成f 2 l s ，s ，d d m i y u ，即两机器 f l o w s h o p 的分组排序，两机器上的安装时间顺序独立，两台机器的加工时间以 及安装时间满足m 。 鸩，即m i n ( a ，) s 。+ m a x ( b ，) ，本文考虑的问题认为前后两机 器的分组相同，排序的目标是总误工工件数最小。 在本文的第三部分将就此问题的n p h a r d 性质进行证明。由于此问题是 n p - h a r d ，所以本文的研究重点将是此问题的搜索算法，本文着重研究了此问题的 基于一些启发式规则的遗传算法。 复黾大学硕士学位论文 2 相关的排序问题 2 1 排序理论 随着全球竞争的不断加剧和客户需求的变化，整个制造业都在重新调整自己 的生产系统。一直以来，价格和准时交货都是客户所关心的两个要素，客户期望 较低的购买价格和准时地交货。从制造企业的角度，成本控制和提高客户满意度 是企业形成自身竞争优势的重要环节。本文的主题，生产作业排序就是制造业降 低成本和提高客户满意的一个关键成功因子。同时，排序问题不仅仅存在于生产 过程中，而且在其他环节，例如运输、分销等物流过程中也同样存在。 通常认为，排序是在有限的资源约束条件下，为了达到一定的优化目标而对 一系列任务或工作进行决策的过程 3 4 1 。这些任务可能会有不同的优先级、不同 的就绪时间和不同的加工时间等等。而优化的目标也有可能是最小化完成时间、 最小化延误的工作数目等。 一般在排序过程中考虑两个问题：如何将待完成的工作分配到不同的机器以 及如何确定分配到同台机器的工作的加工顺序。 研究排序问题的主要原因是：合理的排序方案能够给企业带来巨大的经济效 益。但是，也应该意识到，排序问题通常都是一个多目标、多约束的优化问题， 一般都是n p 完全问题。不同的生产环境其解决的排序方案是不同的，不存在通 用的排序方案。而且生产环境是动态变化的，因此排序问题的解决不能单纯依靠 人和计算机，必须把人、人工智能技术、数学规划和计算机有机地结合起来去研 究排序问题。 排序问题是一个分支庞杂的问题，由于实际生产中的问题的多样性，导致了 排序问题的多样性，按照一些方法可以分为几个大类： 1 按生产线中各工件的加工路径分：单机生产线排序，并行机生产线排序； f l o ws h o p 生产线排序，j o bs h o p 生产线排序，o p e ns h o p 生产线排序； 可重入式微电子生产线排序，f m s 生产线排序，装配型生产线排序。 2 按调度目标分：最小化完工时间；最小化拖期任务数；最小化提h i s 拖 期成本；最小化总拖期时间；多目标排序。 3 根据工件进入加工状态的特点分：离线排序( o f f - l i n e ) ，排序问题的所有 信息，包括工件的个数、就绪时间、加工时间等等在开始排序前都是知 道的；在线排序( o n 1 i n e ) ，工件的信息是逐个释放的，在决定当前工件 加工时对其后面就绪的工件的信息是一无所知的，并且一旦决定工件的 复旦大学硕士学位论文 安排后就不允许改变；半在线( s e m io n 1 i n e ) 的，半在线排序是介于在 线和离线之间的，即不允许对已经安排的工件重排，在排序之前不知道 所以的信息，但是知道后面的就绪工件的部分信息。 4 按调度中是否存在不确定性因素分：确定性排序( d e t e r m i n i s t i c ) ；非确定 型( n o n d e t e r m i n i s t i c ) 排序。 5 按是否带特殊工艺约束分：带普通工艺约束的排序问题；带特殊工艺约 束的排序问题。 2 1 1 排序问题的描述方法 最常用且能详细刻画不同类型排序问题特点的描述方法有下列两种： 1 四参数表示法( b c d ) 1 9 6 7 年c o n w a y 等首先提出用四个参数来描述一个排序问题。其中： a 表示工作数量( 大于1 的整数) ； b 表示机器数量( 大于1 的整数) ； c 表示机器环境类型，如流水车间类型，用f 表示； d 表示优化目标函数，即性能指标； 2 三参数表示法( 口卢y ) 1 9 7 9 年g r a h a m 、l a w l e r 、l e n s t m 和r i n n o o yk a r l 等在四参数表示法基础上 提出改用三参数，这也成为目前国际上标准的描述方法。 参数口表示机器环境类型，参数口描述了具体的工作的处理要求和相关的约 束，参数y 描述了排序的目标函数。 对成组排序问题的描述方法： g t 技术的应用以及f m s 的进一步发展，使得在这种制造环境下的排序问题 的特征与经典排序的一些假设有所区别。经典排序中更换工作所需要的安装时间 是假设与机器和前续工作无关的，因此，加工工作前的安装时间在经典排序模型 中可以合并到工作的加工时间里。然而，在成组技术环境之下，工作可以被划分 为一些工作组，当同组的工作连续加工时，加工设备并不需要或者需要较少的安 装时间，而当不同组的工作连续加工时，则需要较多的安装时间。而且，一般来 讲工作的安装时间是依赖于工作顺序的。 近年来，国外已经注意到了g t 环境下生产的这些特征，因此出现了一些研 复旦大学硕士学位论文 究，开始重视工作分组后组内工作的排序和组与组之间的排序。这个问题，在英 文文献里用词是s c h e d u l i n gw i t hf a m i l i e s ，也就是成组排序问题 1 9 。 我们首先对成组排序的模型进行描述，并给出全文通用的一些符号和记号。 在实际的成组排序问题中，可能会面临在单台机器、多台机器上排序等不同 的情形。而对于多台机器的情况，有可能是多台并行机( 工作可以在多台机器中 任意一台加工) 、也有可能是工作需要在m 台串行的机器上加工。后者有可能分 为：工作需要在卅台机器上逐一的顺序的进行加工( f l o ws h o p ) ；工作的加工顺 序事先已知但并不需要逐一和顺序在所有的机器上进行加工( j o bs h o p ) ；工作需 要在所有m 台机器上都进行加工，但并不需要顺序进行( o p e ns h o p ) 。 对于每台机器而言，实际中有可能该机器可以同时处理多个工作的情形出 现。但对于本文而言，仅考虑机器同时只能处理一个工作的情形，同时处理多个 工作的模型是另一类排序模型，文献中称之为s c h e d u l i n gw i t hb a t c h i n g 。 对分组排序按照工件什么时候可以下线或者可以进行下一步加工可分为两 大类：集批可用( b a t c ha v a i l a b i l i t y ) 和单件可用( i t e ma v a i l a b i l i t y ) ，对于前者必须 整批工件都加工完毕才可以下线或到下一道工序加工，而对于后者只要单件加工 完毕就可以。 按照同一组内的工件是否必须连接放在一起加工成组排序可以分成两类：一 类是b a t c h i n gu n d e rt h eg r o u pt e c h n o l o g ya s s u m p t i o n ，即同一组内的工件必须连接 放在一起加工，我们成为必须满足成组技术要求的成组排序三；另一类是不受成 组技术的限制，同一组内的工件不必接连进行加工，称为不受成组技术的限制的 成组排序。 由于不受成组技术的限制，因此一个组中的工件可以分成若干小组( b a t c h ) 并分开被加工。在许多实际情况中“必须满足成组技术要求”不是一个最好的策 略，而把同一个组的工件分成若干小组进行加工可能会更好。考虑下面这个具有 两个组的简单例子：共四个工件分为两组 1 ，2 和 3 ，4 ，安装时间分别为 s j = 3 ，s ，= 4 ，四个工件的处理时间分别为5 ，7 ，1 0 和3 。交货期分别为1 0 ，2 5 ， 1 5 ，2 0 。如果必须满足成组假设要求，即不对组进行拆分，则工件1 和2 误工， 或者工件3 和4 误工。但是如果我们对组进行拆分可得到更优的解，将两个组都 拆成两个小组则有最优序( 1 ，4 ，2 ，3 ) ，这个序只有工件3 误工。 我们记m 台机器前有待加工的个工作： 1 ，2 ， ，每个工作，有一个交 货期d ，。这些工作可以被分成f 个组，组f ( 1 f f ) 内的工作数记为竹，因此 组f 内的工作又可编号为( 1 ，厂) ，( 2 ，) ，( n r ，厂) ，而工作( ，厂) 在机器上f 的加工 时间可以记为p 。属于同一个组的工作连续处理时不需要安装时间( s e t u p 复旦大学硕士学位论文 t i m e ) ，但不是同一个组连续在机器f 上加工时，在工作加工前需要一定的安装时 间。组g 内的工作在机器i 上加工前，如果在机器i 上加工的前续工作属于组， 那么需要的安装时间为。如果组g 内工作第一个在机器i 上加工，那么需要的 安装时间为j 。 如果对于任意组g ，且厂g ，有s ，o g23 瞻2s w ，那么称之为安装时间是顺 序独立的，否则，称之为顺序依赖的。 对于每台机器f ，如果对于任意的厂，有= ，其中包括厂= 0 的情形 那么称之为安装时间是机器独立的，否则，称之为机器依赖的。 另外，我们假设有+ 对于任意的，g ，矗成立，包括，= 0 。这个条 件显然这个条件在现实环境下是合理必要的。 下面，我们定义相关的其它变量。 c ：工作，的完成时间； l j = q 一一：工作，的延迟时间； = ：篓考：2 ：工作是否拖期； r = m a ) 【 q 一嘭，o ) ：工作的延误时间； 下面我们利用三参数方法帆i ：i 忆来描述成组排序模型。 1 ) 参数= a m 描述了排序问题中涉及的“机器的环境”( m a c h i n e e n v i r o n m e n t ) 。 其中参数口 p ，q ，r ，f ，j ，0 描述机器的类型： 口= p 表示同型( 号) 机器 口= q 表示同类( 别) 机器 口= r 表示非同类型机器 口= f 表示流水作业机器( f l o ws h o p ) 睇= t ，表示异序作业机器( j o bs h o p ) 口= 0 表示自由作业机器( o p e ns h o p ) 参数m 反映机器的数量： 2 ) 参数妒2 描述“工作的特征”( j o bc h a r a c t e r i s t i c s ) ，例如，可能的参数特征 有： 复旦大学硕士学位论文 p ，= p 所有共建有共同的加：亡时间 d i = d 所有工件具有相同的交货期 包在机器i 上集批最大为6 ， s f2s 所有组有共同的安装时间 g t ：同类工件需一起加工，即满足成组假设 b d ：工件成组交货 ：工作的就绪时间 d ：工作的交货期 f = k ：共有有常数k 个工作组； h ，= h f ：每个组有相同的工作数n f ； t m ：工作的安装时间； s 。：机器独立环境下工作的安装时间； 呀：顺序独立环境下工作的安装时间； 5 ，：顺序独立且机器独立环境下工作的安装时间； 3 ) 参数，描述排序问题的目标函数 成组排序问题中一般涉及的目标函数为最小化如下的函数： t j = m a x c 。一d j ，o l 工伪的拖期长度 c m a x2 m a x q 1 1 ，m ：最大完工时间 y w j c ，：带权的各项工作的完工时间之和 k 2 m a x l ，1 1 ，m ：最大延迟时间 ( _ ) ：带权的延迟工作之和 ( 叶) 7 ：| ：带权的工作的延误时间总和 例如：问题f 2s ，ic m 。表示的是在流水作业的两台机器上，某个工作组内的 的安装时间仅与工作组自身有关，目标是最小化最大的工作完工时间。 2 1 2 排序问题的复杂性及研究方法 生产排序问题的本质决定了这类问题具有的复杂特性，主要表现在 3 5 】： 排序对象和排序目标的多样性【3 6 】：在制造业中，产品种类的多样化决定了 复旦大学硕士学位论文 加工路线的多样性，而生产路线的特征与参数是选取排序方法的依据，各种 排序方案的性能是依问题中机器特征的变化而变化的：同时，在不同类型生 产企业和制造环境下，约束条件和评价指标也是千差万别的；实际生产系统 常用的性能指标有产品成品率、产品制造周期、生产率、设备利用率和拖期 率等。如果必须考虑实际中的诸多约束条件，则运用传统的分析方法很难找 到满足所有约束的可行解，通常所用的方法都对实际问题进行了简化和忽略 了某些约束。 2 制造环境的不确定性：排序决策通常依据的是现实环境的模型而非现实环境 本身，而加工时间的波动、机器设备的故障、加入临时订单的调整等不确定 性因素，使得现实环境与其所建立的模型之问存在差异。 3 问题求解过程的复杂性：排序问题本质上的组合优化特征导致了问题的计算 复杂性，大多数问题已被证明是n p 难问题 3 7 】，如果再同时考虑多个评价 指标或排序环境的随机性，则问题将变得更为复杂。 自从上世纪5 0 年代以来，排序问题在学术界得到了广泛的研究。四十多年 来，出现了大量的理论研究。这些研究基本上都致力于寻找各种各样排序问题的 多项式算法。但是，很多的排序问题是不存在多项式算法的，在此过程研究中， 导致了计算复杂性概念的诞生。此后，排序问题的理论研究变为或者寻找到问题 的多项式算法或者证明该问题不存在多项式算法。 在对经典的排序问题取得大量的理论成果之后，9 0 年代开始，理论研究的重 心转移到将这些经典的算法更多的与实际的排序问题结合上【3 8 】。然而，由于大 量的实际问题非常的复杂，甚至无法建立数学模型。这样，以往应用较为广泛的 如分支定界法、动态规划等技术很难应用到实际的排序问题中。即使有的问题能 够归结为数学模型，但是，计算的复杂性也使得要迅速的找到一个满意的排序结 果变得很困难。 面对这种研究的困境，学术界转向了对复杂排序问题的启发式算法和搜索技 术的研究。这些近似算法能够在一个相对合理的时间内找到一个满意的排序方 案。 下面，我们简单介绍通常出现在理论研究文献中的排序求解算法。这些求解 方法可分为最优化算法和近似启发式算法两类。 优化算法又分为有效最优化方法和精确最优化方法。有效最优化方法是指在 多项式时间内求得最优化排序的一类方法。但是，由于多数调度问题的n p h a r d 特性，这类有效最优化算法是不存在的。精确最优化算法是一类具有一般性的组 合最优化方法，主要包括线性规划l p 、非线性规划n l p 、动态规划d p 、拉格朗 复旦人学硕士学位论文 日乘子法和分支定界等 3 9 - - 4 1 1 。l p 作为一种精确的运筹学方法，是较成熟的方 法之一，但实际中很多问题不能以简单的线性关系精确表达，且涉及的变量多为 整数，因此限制了l p 的使用。分支定界的使用效率与定界的方法及搜索空间的 结构密切相关，仅适用于中小规模的问题，在解决受多重复杂条件约束和含有不 确定因素的排序问题时结果不理想。当问题的规模增大时，算法的计算时间随之 呈指数增加，会发生“组合爆炸”，给求解计算带来困难。另外，使用最优化算法 时，通常要加上一些脱离实际情况的假设，在一定程度上也导致了理论研究与实 际应用的脱节。 排序算法的研究经历了从有效最优化算法、精确求解算法到计算复杂性的研 究、启发式算法及其有效性的研究历程。进入8 0 年代，随着技术和管理对更高 层次的要求，过多的假设和对制造过程的简化在很大程度上制约着排序理论的研 究和实际应用的范围，于是开展了对更复杂、更接近于实际的排序目标函数、制 造环境及工艺约束条件的问题的研究。由此产生的近似启发式算法有： 1 优先分派规则。一个排序规则可以由多个优先级规则和( 或) 启发式规则组成。 优先级规贝, l j ( p r i o r i t yr u l e ) 按某种方法给每个待排序的工作指定一个数值，并 优先安排具有最小值的工作 4 2 1 。常用的规则有最早交货期( e a r l i e s td u e d a t e ， e d d ) 、最短加工时i 日q ( s h o r t e s tp r o c e s s i n gt i m e ，s p t ) 、最长加工时间( l a r g e s t p r o c e s s i n gt i m e ，l p t ) 、先入先出( f i r s ti nf i r s to u t ，f i f o ) 等，实际使用时可 以将若干个优先级规n 3 n 权组合，形成组合的优先级规则。启发式规则指经 验法则，是比优先级规则更深一层的一些规则，其优点是可以缩短寻优过程 4 3 】a 2 基于知识的方法。基于知识的排序方法利用专家系统自动产生排序或辅助人 去排序，它将传统的排序方法与基于知识的评价相结合，对设计适用于生产 实际的高效益、高柔性的系统具有启发意义 4 4 1 。在应用中，专家系统中知 识的获取和推理速度是两个瓶颈，专家系统有研制花费昂贵、知识的难于获 取和表达的缺点，将人工智能方法能与其他方法结合会得到更有效的排序。 3 神经网络方法。神经网络已被成功地应用于解决组合优化问题，用神经网络 的方法建立生产排序的模型关键在于分别用不同类型的单元网络表示不同 类型的约束条件，然后通过适当连接这些单元神经网络，得到资源约束和排 序约束的网络表示，进一步实现生产排序的建模 4 5 1 。在大规模、复杂排序 问题中，存在计算速度慢与结构参数难于确定的缺点，易陷入局部最小和全 局搜索能力弱。 4 模拟退火算法。模拟退火算法由m e t r o p o l i s 等人 4 6 1 提出，利用受控随机概 复旦大学硕士学位论文 率接受劣解，避免陷入局部最优，是一种串行全局优化算法，在运筹学的各 个领域有大量的研究。其收敛性要求初温应足够高，使解空间各状态能以几 乎相同的概率出现，模拟退火的弱点是搜索空间过于庞大和下降温度难于掌 握。 5 遗传算法。遗传算法是h o l l a n d 4 7 基于自然遗传进化的绝对模型提出的并行 搜索机制，算法简单，鲁棒性强，非常适合解决排序问题。对生产排序问题， 基因的选取一般为排序决策变量，通常采取二进制的编码方式，同时交叉算 子和编码表示对算法的收敛性会产生影响。应用中，为解决收敛速度慢的缺 点，许多学者尝试采取遗传算法和其他算法相结合的方式。此外，遗传算法 对初始种群很敏感，有采取其他启发式( 如优先排序规则) 产生初始种群的 改进方法，近年来，对基于遗传算法的混合优化策略方面的研究出现了一些 成果。 6 禁忌搜索算法。禁忌搜索是g l o v e 1 0 ，3 0 ，4 8 提出的模拟智能过程的一种具有 记忆功能的全局逐步优化算法，对变动的排序在其可行解的所有空间中进行 搜寻。通过设置禁忌表记忆近期搜索路径，避免陷入局部最优或重复过去的 搜索，并由此控制进一步的搜索方向，同时利用中、长期的存储机制迸行强 化和多样化搜索。 与精确最优化算法相比，近似启发式算法的明显优势在于：启发式算法相对 比较简单，计算效率高，能显著地节省计算开支；而且启发式算法灵活多变，在 考虑多种方案和不能用定量表示约束集合时，常能把它作为制定计划的工具。 但是，近似，启发式算法有明显不足之处，即有可能出现所产生的解比全局最 优解差很多的情况，而且差的程度总是不够明确。因此，合理的计算时间和所求 出的解的最优性就成为衡量启发式算法性能的标准。 2 2 误工最小化排序问题的文献综述 2 2 1 经典单机误工最小化排序问题 经典的最小化误工件数单机排序问题即1 | | q ： 人们对经典的最小化误工件数单机排序问题的研究理论和算法对最小化误 工的成组排序问题有着重要的启发，是研究这类问题的基础，因此有必要在此加 以介绍。 问题描述：设有n 个工件，以在一台机器上加工，其工时及工期分别 复旦大学硕士学位论文 为片，b ，只及碣破，吨对给定的排列万= ( 石( 1 ) ，万( 2 ) ，疗( n ) ) ，工件以( ，) 的完工 时间为q m ：窆只。j ) ，当g 。，以c ) 时，以m 称为误工工件，3 $ i e , u = 1 ；否则以， 称为按时工作并记u 。= 0 问题是求加工顺序疗，使误工工件数，( 。) ：宝u r 。为最小。 对于此问题j m i c h a e lm o o r e 1 5 在1 9 6 8 给出了经典的m o o r e 算法： 第一步：将工件按s p t ( s h o r t e s tp r o c e s s i n gt i m e ) 序排列，得到序列 ，其中最，并将其命名为当前序( c u r r e n ts e q u e n c e ) 。 第二步：找到当前序中第一个误工工件，并且转到第三步。如果当前序中 没有误工工件那么算法结束，在当前序后面将被剔出的工件按任意顺序排列即得 到了最优序。 第三步：对工件按照e d d 序排列，z 1 0 ，气。如果 中的所有工件都不误工，则将现在的整个序列定义为当前序，并且转到第二步， 否则将工件从整个序列 剔出，将剩下的序列最为当前序转到第二步。 基于以上算法，有很多人进行了扩展和优化，下面将介绍比较有名的 m o o r e h o d g s o n 1 6 算法。 首先将工件集j 的工件按e d d 序排列。分别用s 和s 表示无延误工件集和 延误工件集。 第一步：置s = 妒，s = ； 第二步：若d ，= m i n w ( 嘭) ，置s 仁s u b j 乍j l j + j ； 第三步：若，p j d f ，令k + 表示满足下述条件的工件：p 。= m a x m ( p j ) ( 加 工时间相同的工件取工期大者) ，置s 乍s 一 k 1 ，s 仁s - f 1 ； 第四步：若j = 痧，算法终止；否则转步骤2 。 邓俊强和林诒勋 1 3 1 出于多指标决策问题的需要，对经典排序问题1 | | u ， 即最小化误工工件数的单机排序问题确定出了一个单指标问题的全部最优解的 结构和并就最优解的唯一性问题进行了探讨。 对于1i l 彬q 问题的一般情况k a r p 2 4 1 已经证明此问题为n p - h a r d ，因此对 其似乎不存在多项式时间算法v i l l a r r e l 和b u f f i n 【2 5 】基于二个下界子程序对此 问题给出了一个分支定界算法，在他们的文章中还给出了一个可独立于任何分支 定界算法的优势准则，并在他们所给的算法中利用该优势准则以减少搜索点。排 序问题中的优势准则在减少需考虑排序数时十分有用，对极d , m 权误工工件数问 题的第一个