（管理科学与工程专业论文）基于启发式算法的单件车间作业排序研究.pdf

7 l 1 i i _ ， 中；i j 弩 一 墨 at h e s i si nm s t u d y b y l ij i n y a n s u p e r v i s o r ：a s s i s t a n t p r o f e s s o rz h a n gj i s h a n n o r t h e a s t e r nu n i v e r s i t y j u n e2 0 0 8 ；羹 f j 浮氏， 独创性声明 本人声明，所呈交的学位论文是在导师的指导下完成的。论文中取得 的研究成果除加以标注和致谢的地方外，不包含其他人己经发表或撰写过 的研究成果，也不包括本人为获得其他学位而使用过的材料。与我一同工 作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢 = 亡己 恳。 学位论文作者签名：辱锄 日期：和呸7 哆 学位论文版权使用授权书 本学位论文作者和指导教师完全了解东北大学有关保留、使用学位论 文的规定：即学校有权保留并向国家有关部门或机构送交论文的复印件和 磁盘，允许论文被查阅和借阅。本人同意东北大学可以将学位论文的全部 或部分内容编入有关数据库进行检索、交流。 作者和导师同意网上交流的时间为作者获得学位后： 半年口一年口一年半两年口 学位论文作者签名：苍镌 签字日期：厶0 5 7 ，牛 磅p 余栅巩伽 一 笤 期 签 日 币芋师字导签 | i 参一 v 囊。 ，0， ，1l 簟分v 东北大学硕士论文摘要 基于启发式算法的单件车间作业排序研究 摘要 随着市场竞争的日益剧烈，大多数制造企业的生产方式正向着多品种小批量方向发 展，因此面向单件小批量生产方式的单件车间作业排序问题已成为一个具有代表性的研 究问题。 本文在查阅大量相关文献的基础上，针对传统单件车间作业排序问题，分析原有模 型的局限性，对排序模型进行优化，建立以误工工件数最少为目标函数的数学模型，此 模型的建立解决了多个零件工序竞争一台设备时的工件排序问题和一个零件工序可在 多台设备上加工时的设备选择问题。为了求解模型，本文提出一种新的启发式算法，使 搜索在那些最有可能产生最优解或近似最优解的区域展开，缩短搜索时间，提高工作效 率。同时在此基础上兼顾同类机器各台负荷必尽可能均匀的原则，通过合理调整各类机 器的数量，提高机器利用率，实现均衡生产。最后，本文通过具体实例的仿真和比较验 证了此算法的可行性。 通过本文模型的建立与求解，为解决单件车间作业排序问题提供了一种可行的方 法，具体实例验证了算法的可行性，总的说来，本文对实际生产就有一定的指导意义。 关键词：单件车间，作业排序，启发式算法 v 0 0 _ s t u d yo ft h ej o bs h o ps e q u e n c i n g b a s e do nh e u r i s t i c sa l g o r i t h m a bs t r a c t t h ep r o d u c t i o nm o d eo fm o s tm a n u f a c t u r i n ge n t e r p r i s e si st u r n i n gt os m a l lb a t c ha l o n g w i t ht h ei n t e n s ec o m p e t i t i o no ft h em a r k e t ，s ot h ej o bs h o ps e q u e n c i n gp r o b l e mh a sb e c o m ea t y p i c a ls c h e d u l i n gp r o b l e m r e f e r et ot h en u m b e ro fd o c u m e n t s ，t h ep a p e ro p t i m i z et h ej o bs h o ps e q u e n c i n gm o d e l t h r o u g ha n a l y z i n gt h el i m i t i o no fo r i g i n a lm o d l e ，a n ds e tu pm a t h e m a t i c a lm o d e lw h i c h m i n i m i z et h en u m b e ro ft a r d yj o b s t h ea l g o r i t h mi su s e dt oc h o o s et h ep a r tw h e no p e r a t i o n s o fd i f f e r e n tp a r t sc o m p e t i n go n em a c h i n ea n dc h o o s et h em a c h i n ew h e na no p e r a t i o no fap a r t h a dm o r et h a no n eu s a b l em a c h i n e t h ep a p e rp u tf o r w a r da r la m e l i o r a t i o no ft h ec l a s s i c a lj o b s h o ps c h e d u l i n gp r o b l e mt oc o n s t r u c to n e n e wm e t h o do fh e u r i s t i ca l g o r i t h mt h a tc a nm a k e t h es e a r c hr e g i o nn e a rt h er e s u l t ，w h i c hc a ns h o r t e nt h es e a r c ht i m ea n di m p r o v ee f f i c i e n c yo f t h ew o r k o nt h es a m et i m e ，t h em e t h o dt a k e st h eb a l a n c eo ft h es a m ek i n do fm a c h i n e si n t o a c c o u n ta n da d j u s t st h eq u a n t i t yo ft h ee q u i p m e n t sw i t hr e a s o n t h a tm e t h o di m p r o v e st h e u t i l i z a t i o no fm a c h i n e a tl a s t ，a n dt h ea p p l i c a t i o no ft h ea l g o r i t h mt oap l a ni sa l s op r e s e n t e d a sa ne x a m p l et oi l l u s t r a t et h es a t i s f a c t o r yr e s u l t s t of i n das o l u t i o nt os e q u e n c i n go fj o bs h o pp r o b l e m ，t h ep a p e rp r o v i d e sav i a b l e m e t h o dt h r o u g ht h em e d e lc o n s t r u c t e da n ds o l v e d i naw o r d ，t h ep a p e ri si m p o r t a n tt ot h e p r a c t i c a lp r o d u c t i o n k e yw o r d s ：j o bs h o p ，s e q u e n c i n g , h e u r i s t i ca l g o r i t h m i i i - 0 10 东北大学硕士论文目录 目录 独创性声明i 摘要i i a b s t r a c t i i i 第1 章绪论l 1 1 研究背景1 1 1 1 生产计划是企业实现战略目标的保证l 1 1 2 生产作业计划是企业生产计划的具体执行计划2 1 1 3 排序问题是生产作业计划中的难点3 1 2 问题的提出5 1 3 研究目标与研究内容7 1 4 研究思路与研究方法8 1 5 论文结构8 第2 章作业排序文献综述11 2 1 文献来源及统计分析。1 1 2 2 排序问题的发展概况1 3 2 3 关于排序的相关问题1 5 2 3 1 排序问题的定义。1 5 2 3 2 排序问题的分类1 7 2 4 排序问题的研究方法1 9 2 4 1 数学规划方法。1 9 2 4 2 启发式搜索方法。2 0 2 4 3 系统仿真方法。2 0 2 4 4 人工智能方法2 0 2 4 5 计算智能方法。2 l 2 5 排序问题的研究趋势2 3 2 6 本章小结2 4 第3 章单件车间作业排序问题2 5 3 1 单件车间作业排序概述2 5 3 1 1 单件车间作业排序问题一般描述2 5 3 1 2 单件车间作业排序问题特点2 6 3 1 3 单件车间作业排序问题的数学模型2 7 3 2 单件车间作业排序问题研究方法2 8 3 2 1 启发式规则。2 8 目录 ：z 9 ：；：i ：；：i 3 4 3 4 ：；! ； ：；6 3 7 ：；8 3 9 ：；9 4 0 4 0 4 0 4 2 z 4 2 4 3 - ：4 4 4 5 4 5 4 5 4 5 4 8 4 8 4 9 5 4 ! ；! ； ! ；! ； ! ；5 ! ；! ； ! ；7 6 ：l 1 v j 东北大学硕士论文第1 章绪论 1 1 研究背景 第1 章绪论 1 1 1 生产计划是企业实现战略目标的保证 计划是指导企业未来行动的蓝图，它规定了企业未来的目标以及从现实通向目标的 道路。生产运作计划则从生产运作领域规定了企业在未来一定时间内的目标和任务，如 品种、质量、数量、进度等，指导企业的生产运作活动，以实现企业总体经营目标。生 产运作活动是企业的主体活动，在相当程度上决定或影响其他职能领域，如市场营销、 物资供应、设备维修、人力资源、财务成本部门的计划与活动，对企业的经营质量与发 展前景有十分重要的作用，是企业实现战略目标的保证。 通常企业的生产计划分为长期计划、中期计划、短期计划。 长期生产运作计划规定了企业在较长时间内，一般为三至五年甚至更长时间内企业 发展的目标、步骤、资源、重大项目与措施，主要包括产品或服务项目的发展方向、生 产与运作发展规划、技术发展水平及主要技术经济指标。由于计划期长，可能出现的不 确定因素较多，长期计划内容比较粗略简要，并需要在执行过程中不断调整以适应庆z j l - 环境的变化。 中期生产运作计划的时间跨度一般为一年或更长一些，它是长期计划在计划期内的 具体化，也是短期计划的依据，在计划体系中起着承上启下的作用。其主要任务是在正 确预测市场需求的基础上，充分利用现有资源和生产能力，有效地、均衡地组织生产， 以获取最佳的经济效益。中期生产运作计划的内容包括企业的年度生产目标，如品种、 质量、产量、产值、新产品、新项目开发，以及年度内按季、按月的进度。中期计划的 重点是如何有效利用企业资源去满足市场的需求。中期计划时间跨度比长期计划短，不 确定因素相应减少，其内容也不够详细，只是按产品的大类编制计划。 短期生产运作计划是具体落实中长期计划的执行计划，又称生产作业计划，时间跨 度在一年以内，如季计划、月计划、日计划等。短期计划的任务是根据用户的订单合理 安排生产活动的每个细节，具体规定企业在什么时间、什么地方生产，产品的品种、数 量、顺序，进度、以及与此有关的物料需求与供应、设备和人员的配备等，以充分发挥 生产能里去完成订货合同，满足市场需求。由于时间跨度短，短期计划任务明确，影响 成产的各种因素也比较清楚，其内容详细具体。 - 1 - 东北大学硕士论文第1 章绪论 1 1 2 生产作业计划是企业生产计划的具体执行计划 生产作业计划是企业生产计划的具体执行计划。这种具体化表现在将生产计划规定 的产品任务在规格、空间、时间等方面进行分解，即在产品方面具体规定到品种、质量、 数量；在作业单位方面规定到车间、工段、班组乃至设备，在时间上细化到月、旬、日、 时，以保证企业生产计划得到切实可行的落实。因此，生产作业计划的任务是按照产品 生产计划的时、量、期及产品的工业要求，将生产资源最适当地配置给各产品任务，形 成各作业单位在时间周期的进度日程安排。这样，既完成生产计划，又使资源得到充分 均衡利用。为此，生产作业计划的主要工作内容应是明确企业各级生产单位所拥有的生 产资源即生产能力、分配任务负荷、平衡负荷与生产能力、编制日历进度计划、监督检 查各种生产准备工作( 技术、供应) 以及生产作业控制调度。在编制生产作业计划过程 中的主要决策问题包括：确定不同产品的生产顺序；确定某一产品的生产批量以及确定 生产进度日程。相应的决策目标包括：计划完成率、生产周期、设备利用率、生产成本 脑 号手0 一个企业的生产作业计划的制定过程同企业所属生产类型密切相关。 ( 1 ) 大量流水作业生产的生产作业计划 大量生产的主要生产组织方式为流水生产，其基础是由设备、工作地和传送装置构 成的设施系统，即流水生产线。流水生产具有以下特点：专业化程度高，流水线固定生 产一种或几种制品，每个工作地固定完成一道或几道工序；工艺过程是封闭的，生产对 象在流水线上完成其全部或大部分工序；工作地按工艺过程的顺序排列，生产对象在工 作地间单向移动；生产过程分解为许多独立的可在相等的时间间隔内完成的工序，生产 对象按照统一的生产速度进行生产，具有明显的节奏性；各工作地之间有传送装置连接。 最典型的流水生产线是汽车装配生产线。流水生产线是为特定的产品和预定的生产大纲 所设计。生产作业计划的主要决策问题在流水生产线的设计阶段中就已经做出规定。因 此，大量流水生产的生产作业计划的关键在于合理地设计好流水线。这包括确定流水线 的生产节拍、给流水线上的各工作地分配负荷、确定产品的生产顺序等。 ( 2 ) 成批生产的生产作业计划 从生产作业计划的角度考虑，成批生产方式具有自己的特点： 首先，企业所生产的产品的品种较多，且多为系列化的定型产品。产品的结构与工 业有较好的相似性，因而可以组织成批生产。各品种的产量不大，在同一计划期内，有 多种产品在各个生产单位内成批轮番生产。 其次，各产品的工艺路线不尽相同，可有多种排序的工艺路线。加工设备既有专用 - 2 东北大学硕士论文第1 章绪论 设备又有通用设备。 再次，生产任务来自用户订货或依据市场预测，一般对交货期有较严格的要求，一 般有一定的成品、半成品和原材料库存。 最后，在同一时段内，存在生产任务在利用生产能力时发生冲突的显现，特别是关 键设备上。 基于以上特点，成批生产作业计划所要解决的主要问题是如何在时间上安排不同数 量的产品轮番生产。成批生产的期量标准有批量与生产间隔期、生产周期、生产提前期、 在制品定额等。 ( 3 ) 单件小批量生产的生产作业计划 在单件小批量生产条件下，企业所生产的产品的品种多，每个品种的产量很小，基 本上是按照用户的订货需要组织生产，产品的结构与工艺有较大的差异；生产稳定性和 专业化程度低。生产设备采用通用设备，按照工艺原则组织生产单位。每个工作中心承 担多种生产任务的加工。产品的生产过程间断时间、工艺路线和生产周期都较长。但是， 单件小批量生产具有生产灵活，对外部市场环境有较好的适应性等优点。 基于上述特点，单件小批量生产的生产作业计划要解决的主要问题是，如何控制好 产品的生产流程，使得整个生产环节达到均衡负荷，最大限度地缩短生产周期，按订货 要求的交货期完成生产任务。 1 1 3 排序问题是生产作业计划中的难点 在编制成批生产作业计划与单件小批生产作业计划过程中，由于生产多种产品，对 生产设备的需求会发生冲突。因此，需要解决各个生产层次中生产任务的加工顺序问题， 这里既包括哪个生产任务先投产，那个生产任务后投入，还包括在同一设备上不同工件 的加工顺序，这一过程称为作业顺序。作业计划与作业顺序是两个不同的概念。排序是 确定工件在设备上的加工顺序，而作业计划不尽包括确定工件的加工顺序，还包括确定 设备加工每个工件的开始时间和结束时间。其实，给出一个加工顺序并不十分困难，问 题的难点在于不同作业顺序的结果差别很大。因此，排序的目标是，如何在尽可能满足 各种约束条件的情况下，给出一个令人满意的排序方案。 影响生产作业排序的因素有很多，简单介绍如下【l 】： ( 1 ) 生产任务的到达方式 在实际生产过程中，尤其是在单件小批生产条件下，反映生产任务订单的到达方式 有两种：一种是成批到达( 称为静态到达) ；另一种是在一段时间段内按某种统计分布 规律到达( 称为动态到达) 。静态到达并不意味着用户们同时提出订单，只是计划人员 - 3 - 东北大学硕士论文第1 章绪论 将一段时间内的订单汇总，一起安排生产作业计划。而在动态到达情况下，生产任务随 到随时安排，这就要求对生产作业计划不断进行修改，反映这些追加的生产任务。 ( 2 ) 车间中的设备种类和数量 设备数量的多少明显地影响作业顺序的过程。如果只有一台设备，作业排序问题将 非常简单。但当设备数量及种类增多，各种生产任务将由多台设备的加工才能完成，则 问题将变的较为负责，很可能找不到有效的排序方法。 ( 3 ) 车间中的人员数量 在进行生产任务的排序时，不仅是将生产任务分配给设备，同时也是分配给相应设 备的操作人员。对于特定的生产操作人员数量少于设备数量的情况下，生产操作人员将 成为排序时必须考虑的关键资源。 ( 4 ) 生产任务在车间的流动模式 在单件小批生产条件下，生产任务在车间内的流动路线是多种多样的。如果所有流 动路线相同，称为流水车间。与流水车间相对应的另一个极端是流动路线均不一样，工 件是按照某种概率分布从一台设备流向满足加工需要的设备中的某一台设备，称为单件 车间或随机路线车间。在现实生产中，更多的是介于两者之间的混合式加工车间。 ( 5 ) 作业计划的评价标准 作业排序是编制生产作业计划的核心工作之一，其具体排序方法的选择与作业计划 的评价标准密切相关。 总流程时间最短 总流程时间是指一批工件从进入某一车间或工艺阶段开始，到这批工件加工完，全 部退出该车间或工艺阶段为止的全部完工时间。如果这批工件完全相同，则总流程时间 与这批工件的生产周期或加工周期相同；如果不同，则总流程时间与这批工件实际生产 周期或加工周期中最大的相同。 平均流程时间厅最短 平均流程时间是指这批工件实际生产周期或加工周期的平均值。 最大延迟厶嗽或最大误期最短 延迟是指工件的实际完成时间与预定的交货期之间的差额。这里既包括实际完成时 间比预定的交货期晚，即通常意义下的延误，也包括实际完成时间比预定的交货期早的 情况。误期是指通常意义下的延误。最大延迟k 与最大误期k 的关系为： = m a x o ，k ( 1 1 ) 平均延迟云或平均误期于最短 - 4 东北大学硕士论文 第1 章绪论 指延迟或误期的平均值最短。 平均在制品占用量最小 总调整时间最小 在加工一批不同工件时，每加工一个工件，设备需要调整一次，该批工件的调整时 间之和称为总调整时间。 除了上述标准之外，还有延期罚款最小、生产费用最小、总利润最大、设备利用率 最大等。由于实际生产过程中各种不确定因素的作用，使得实际标准具有不确定性，可 用具有平均值和偏差的统计分布来表示，但是这些标准彼此之间并不是独立的，例如， 使平均流程时间户最短意味着在制品占用量减少。 1 2 问题的提出 随着科学技术的飞速发展以及市场全球化步伐的加快，2 l 世纪的企业面临着新的挑 战和机遇。产品的生命周期的变短，迫使企业必须不断更新产品和发展品种。企业要想 在激烈的市场竞争中取胜，就必须以最快的速度开发出满足客户要求的新产品，并以最 短的时间将新产品推向市场，否则将难以生存和发展。与此同时，消费者的价值观也正 在发生结构性的变化，呈现出日趋主体化、个性化和多样化的发展。消费者不仅要求购 置高质量、低成本和高性能的产品，而且希望产品具有满足其感受的特性。这些变化使 以单品种、大批量为特点的大批量生产方式越来越不能适应时期的要求。因此面向订单 的以低成本、高质量、高效率以及满足交货期要求为特征的多品种中小批量生产成为离 散制造业广泛采取的制造方式。 据统计，我国机械制造业有9 5 属于多品种小批量生产类型。此类型生产有以下特 点( 2 】： ( 1 ) 产品品种的多样性 由于产品品种繁多，而每一品种产品生产的数量少，生产专业化程度较低。 ( 2 ) 生产工艺的复杂性 由于生产的产品多而且各不相同，使得加工工序繁多，加工的对象在车间内频繁地 由一个工作中心转换到另一个工作中心，形成复杂的工艺路线。 ( 3 ) 生产能力不平衡 由于市场需求的不确定性，导致生产设备能力的不足或过剩，只有通过采取各种措 施才能保持能力的平衡和生产的均衡。 ( 4 ) 编制生产计划的困难性 - 5 - 东北大学硕士论文 第1 章绪论 因为订货规格不一，以及经常会遇到客户定单发生改变的情况，或者增加临时的紧 急定单，这样会打乱原有的生产计划，造成产品设计和生产过程多变、复杂的特性。 ( 5 ) 生产管理的复杂性 由于具体的车间生产情况多变，时有出现设备故障、人员缺勤、工件返工等问题， 仅凭经验靠直觉办事难以实行有效的、规范的管理。 ( 6 ) 对工人的素质要求较高 在多品种小批量生产条件下，要求工人掌握多种操作技术，而且应具有一定的熟练 程度，以适应多品种和周期性生产变动的要求。 因为这些特点使得多品种小批量生产类型企业生产与管理工作效率低下，面临巨大 挑战。多品种小批量生产具有的上述特点，使得该类型的企业在生产计划管理方面存在 以下一些问题【3 】： ( 1 ) 生产计划与调度方法落后 以前的生产计划与调度完全依赖管理者的经验，编制的生产计划比较粗放。不仅工 作量大而且不够准确，不能保证均衡生产，并且生产发生变化时计划调整困难，相应速 度慢，不能满足快速响应的要求。近阶段，学者们及现场的管理者们也力图通过科学的 方法利用数学特别是运筹学的相关知识建立数学模型模拟生产过程，但建立的模型都基 于一定的假设前提，使得应用于具体实际还有很大差距。 ( 2 ) 生产数据反馈不及时、不准确甚至形成信息孤岛 由于生产计划的执行、零件的加工信息等都是由人工进行统计汇报，工作量大而且 很难及时反馈，缺乏动态更新，很难对生产进度实现有效地控制和管理。另外零件品种 繁多，很多零件属一次加工，基础信息如工艺等大多凭人工经验获得，存在一定误差。 在部分实现了信息化管理的企业中很多计算机应用还处在局部应用阶段，例如仅实现如 财务、库存、统计等的电算化，而大量的管理功能还处在手工管理状态，使企业的生产 经营管理信息成为部门或个人私有，不能实现信息共享。这种信息“私有”的状态，使各 部门的信息形成了一个个“信息孤岛”。在这种情况下，信息要经过复杂的传递路径和复 杂的审批手续，不但造成数据的冗余，而且由于缺乏统一维护，造成数据的不一致性， 影响计划的准确性。 ( 3 ) 车间在制品管理混乱 在多品种小批量生产类型的制造企业，由于自制零件数量多，批量没有规律性，生 产周期长，质量精度要求高，工艺复杂，传递过程中变化大，使得在制品日常管理工作 量巨大，而且人工管理经常出错，工作质量差。在制品管理特别是车间在制品管理往往 6 - 东北大学硕士论文第1 章绪论 成为管理的难题。 所以为了实现高效率、高柔性、高质量及低成本的生产，探索新的生产计划方法， 安排合理的作业排序，成为几十年来人们一直研究的课题。 正是由于多品种小批量生产的特性增大了作业排序的难度。本文在研究个工件在 m 台机器上的单件车间作业排序问题时想要求出模型的精确解非常困难，因此用现在科 学界普遍采用的启发式算法求出最优解或近似最优解。在使用启发式算法进行排序建模 时，需要考虑采用哪种启发搜索规则非常重要。这就需要参考众多的相关文献，在了解 了以往建模的不足之处后，对其进行改进，使其建立的模型更加符合生产实际。 1 3 研究目标与研究内容 针对上述提出的需要研究的问题，本文的研究目标如下： ( 1 ) 建立作业排序模型 结合多品种小批量生产的特点，建立排序模型，应用启发式搜索方法，弄清搜索机 理，建立搜索流程。加深对启发式搜索方法的理解与应用。 ( 2 ) 对已建立的模型进行改进 对以往建立的关于单件车间排序模型，并用启发式方法求解的问题进行研究，在大 量阅读相关文献的基础上找出其不足之处，对模型进行改进，使模型更能真是反映生产 实际、并通过实例分析验证本文提出的启发式方法的有效性。 ( 3 ) 给出计算机辅助算法逻辑结构图 在建立模型并求解的情况下，给出计算机辅助算法逻辑结构图，为实现计算机辅助 排序提供依据。 本文的主要研究内容如下： ( 1 ) 作业排序问题文献评述 对作业排序问题的发展及研究方法进行文献评述。 ( 2 ) 单件车间排序问题分析 针对单件车间生产复杂性，分析求解此类问题的理论与方法为后面章节的建模与改 进打下基础。 ( 3 ) 建模的主要策略与方法 建立生产作业排序模型，介绍应用启发式搜索方法的搜索策略与方法。 ( 4 ) 对模型进行改进 通过分析种零件( 各项任务的工艺流程不同) 需经m 类机器加工的复杂单件车间 - 7 - 及排序 推理分 针对本文所提出的启发式方法，结合某一机械加工车间的具体实际情况进行了应用 实例分析。 1 5 论文结构 本论文由六章构成，具体论文结构说明如下： 第一章，绪论。首先交代本文的研究背景以及选题意义，说明本文的研究目标、研 究内容、研究思路以及研究方法，并且给出本文的研究结构。 第二章，作业排序文献综述。分别就排序问题的定义、分类、发展及所采用的排序 方法进行文献评述。 - 8 东北大学硕士论文第1 章绪论 图1 1 本文研究思路 f i g 1 it h e r e s e a r c ht h i n k i n go ft h i st h e s i s 第三章，单件车间作业排序问题。分别从排序问题的一般描述、特点和数学模型三 个方面阐述单件车间作业排序问题，并详细介绍了启发式方法，包括启发式方法的定义、 基本策略、算法类型和优点等，为后面算法的实现打下基础。 第四章，模型建立及改进。建立使误工工件数最少的目标函数的作业排序模型，并 联系现场实际情况对模型的不足之处进行改进。 第五章，模型求解及应用实例分析。给出模型求解的具体启发式步骤，并应用到某 一具体生产实际情况中，验证算法的可行性。 9 第1 章绪论 的主要研究成果与结论、主要贡献、本文研 1 0 吨 ，j ，乒 东北大学硕士论文第2 章作业排序文献综述 第2 章作业排序文献综述 车间作业排序问题的研究始于2 0 世纪5 0 年代，是制造系统运筹技术、管理技术与 优化技术发展的核心问题之一。有关资料表明，制造过程和计算机中央处理器等7 5 的 时间消耗在非切屑过程中。有效的排序方法与优化技术的研究和应用，已成为先进制造 技术实践的基础和关键，对它的研究具有重要的理论和使用价值。经过众多学者和实践 工作者多年的研究，对于作业排序问题已经取得了很多成果，但作业排序问题的复杂性 特别是单件车间作业排序问题，仍然是生产作业计划问题中讨论的热点与难点。通过阅 读大量文献，本文将对作业排序问题的分类、建模方法等进行综述进而归纳出关于作业 排序问题的研究趋势。 2 1 文献来源及统计分析 本文以“生产作业计划”或“s c h e d u l i n g 作为检索词，检索时间是从1 9 9 9 年至0 2 0 0 8 年3 月，以e l s e v i e rs d o s 、a s m e 、l e x i s n e x i s 、w i l e yl n t e r s c i e l l c e 、w o r l ds c i n e t 电子期刊 数据库、中国学术期刊、中国优秀硕博士学位论文和超星数字图书全文数据库作为检索 源，进行了中英文文献检索。以“生产作业计划”为关键词进行查询，在中国学术期刊全 文数据库中共得中文文献l1 4 2 篇，其中核心期刊8 9 6 篇；中国优秀硕、博士学位论文全 文数据库中共得学位论文3 6 篇；超星数字图书数据库中共得书籍5 l 本。以“s c h e d u l i n g 为 关键词进行搜索，共得英文文献1 0 5 8 8 篇，其中e l s e v i e rs d o s 数据库英文期刊5 6 5 5 篇、 书籍2 7 5 本；a s m e 数据库3 1 5 5 篇；l e x i sn e x i s 数据库9 7 7 篇；w i l e yi m e r s d 黜数据库4 1 6 篇；w o r l ds c i n e t 电子期刊数据库11 0 篇。 在上述检索到有关生产作业计划的文献中，以“作业排序”为关键词进行二次搜索， 在中国学术期刊全文数据库中共得中文文献1 2 0 篇；中国优秀硕、博士学位论文全文数 据库中共得学位论文1 7 篇；超星数字图书全文数据库中共得书籍4 6 本。以“s e q u e n c i n g 为关键词进行二次搜索，共得到英文文献2 0 6 8 篇，其中e l s e v i e rs d o s 数据库英文期刊8 7 6 篇、书籍1 9 7 本；a s m e 数据库7 2 3 篇；l e x i s n e x i s 数据库1 5 2 篇；w i l e yi n t e r s c i e n c e 数据 库9 6 篇；w o r l ds c i n e t 电子期刊数据库2 4 篇。 具体文献的检索源、检索词及篇数如表2 1 所示。 本文所筛选的关于作业排序的文献，从时间分布来看：1 9 9 9 - 2 0 0 0 年2 5 篇( 英文2 1 篇，中文4 篇) ，2 0 0 0 2 0 0 1 年3 9 篇( 英文3 0 篇，中文9 篇) ，2 0 0 1 2 0 0 2 年5 1 篇( 英文3 7 篇，中 东北大学硕士论文笫2 章作业排序文献综述 文1 4 篇) ，2 0 0 2 2 0 0 3 年4 5 篇( 英文3 4 篇，中文1 1 篇) ，2 0 0 3 2 0 0 4 年6 8 篇( 英文4 8 篇，中文2 0 篇) ，2 0 0 4 2 0 0 5 年9 4 篇( 英文6 5 篇，中文2 9 篇) ，2 0 0 5 2 0 0 6 年1 0 5 篇( 英文7 5 篇，中文3 0 篇) ， 2 0 0 6 2 0 0 7 年1 0 0 篇( 英文7 4 篇，中文2 6 篇) ，2 0 0 7 2 0 0 8 年6 0 篇( 英文5 5 篇，中文5 篇) 。中英 文文献的年份分布如图2 1 所示。 表2 1 生产作业计划排序相关文献检索情况 ! 皇垒! ! 兰：! 堡垒婴塑堕! ! ! ! 壁2 1 呈! 璺塑也垫g ! 堕璺篁! ! ! 坐! 垫曼! 堡曼i ! 璺墅旦! ! 塑! ! ! 呈! ! 塑 检索源检索项检索词篇数 蔷二銮羹索 2 0 0 7 2 0 0 6 2 0 0 5 2 0 0 4 年份2 0 0 3 2 0 0 2 2 0 0 卜 2 0 0 0 1 9 9 9 - 一 目目ai女z日自#wm目日一 翰缴缀缀搦缓翰缀鳞兹磁缀豹缴缓缓搦翰缓一 缓黝缀缓缀缓缓黝 黝缓缓缓黼_ 1 2 犀网 l - 中文l 【j 东北大学硕士论文第2 章作业排序文献综述 在本文所筛选的关于作业排序的中、文献中，按处理机的类型、数量和环境对作业 排序问题进行分类，有单机问题、双机问题、f l o w - s h o p 作业排序问题、单件车间排序问 题等。按此类型划分，搜索相关文献，其中，单机问题1 0 9 篇，双机问题6 0 篇，f l o w - s h o p 作业排序问题9 6 篇，单件车间排序问题2 6 7 篇，其他类占t 5 5 篇。不同作业排序类型所 占比例情况如图2 2 所示。 囝单机问题 - 双机问题 口同顺序作业排序问题 口单件车间排序问题 _ 其它 图2 2 不同作业排序类型所占比例情况 f i g 2 2t h ep r o r a t i n go fa l lk i n d so fs c h e d u l i n g 从以上的统计分析可以看出，国内外关于生产作业计划是研究备受瞩目并呈上升趋 势，关于生产作业计划中的排序问题更是研究的热点与重点，其中单件车间排序问题因 为更符合生产作业的实际情况，且属于n p - h a r d 问题，因此越来越受到学者和在实际工 作中的专家们的重视，在此领域的研究将有着十分重要的现实意义。 2 2 排序问题的发展概况 排序问题产生的背景主要是机器制造，后来被广泛应用于计算机系统、运输调度、 生产管理等领域。从普通的生产部门的计划安排、人员调度，学校课程表的制定，到宇 宙飞船的复杂庞大的飞行计划，都要用到排序的理论和算法。 若有几件事放在眼前需要去做，人们便会比较轻重缓急排个工作顺序；倘若从事一 件较为复杂的工作，如建造一幢楼房，需要安排一些不同工种的工人来完成，有的挖地 基，有的扎钢筋、注混凝土、砌砖、装修等，这就需要给参与建造的人们安排一个顺序 13 - 东北大学硕士论文第2 章作业排序文献综述 ( 或时间表) 。过去处理这类问题，大多采用两种方式：一种是根据以往的经验根据实际 情况进行修改，另一种是事情并不复杂做些考虑即可。然而自从第二次世界大战以后， 各种大型企业逐渐兴起：规模庞大，结构复杂，计算不周即可能造成巨大的损失，依靠 拍脑袋已经不能解决问题；产品的更新加快，新产品的设计生产、销售等没有现成的资 料可以参考，此时各种新的组合优化问题便涌现出来，排序问题便是其中之一。 排序问题的一大特点是：模型繁多，适用于某一模型的算法，只要将模型的条件稍 加变化，该算法便不适用【4 1 。在1 9 5 4 年s m j o h n s o n 5 】对两台机器同顺序的排序问题提 出了一个简便而又巧妙的算法，于是，人们便将他的结果推广应用到三台或是更多台机 器上去，皆未成功。直到1 9 7 7 年，g a r e y 【6 】等人证明三台机器同顺序排序问题是一个 n p 完备问题。经过近半个世纪的努力，排序理论和应用已经发展成一门相当重要的科 学。一份题为美国国防部与数学科学研究的报告认为：2 0 世纪9 0 年代至2 1 世纪数 学发展的重点将从连续的对象转向离散的对象，并且组合最优化将有很大的发展。 我国学者，特别是数学工作者，常将作业计划( s c h e d u l i n g ) 称为排序问题。中科院的 越民义、韩继业于7 0 年代初开始研究f l o w s h o p 的问题，并取得了杰出的成就，他们提 出了可行线和可行和的概念 7 1 ，得到根据两个工件的工时来确定相邻的加工次序的判定 条件，这在推广j o h n s o n 条件的意义上是最终性的，他们于1 9 7 9 年给出了比s z w a r e 更 一般的消去准则和完工时间的下界表达式，并以此为基础他们设计出较优的算法【8 】。他 们的工作引起我国应用数学工作者的广泛兴趣，从而打开了我国研究与应用排序问题的 局面。1 9 8 0 年8 月，中国运筹学会在上海召开了第一届全国排序学术讨论会，标志着我 国排序理论研究和应用进入了新阶段。 杨承恩【9 1 、戴志勇【1 0 1 、常庆龙【1 1 】等也是较早开始研究排序问题，杨承恩还研究与排 序有关的旅行修理员问题【屹】。戴志勇【1 3 】在深入研究同顺序排序的结构和进行最劣情况分 析，并寻找在成组技术中的应用。常庆龙【l l , 1 4 l 研究工序之间有滞留的流水作业的排序问 题。杨承想【l5 】也研究工序间有停歇的两台机器流水作业问题。杨承想、周栩和彭昂【1 6 还提出同顺序流水作业的一种启发式算法咖权排序法，经过数百个实例计算，效果 较好。他们还进一步提出工件加工前后都存在停歇( 力日工前的准备时间和加工后的处理 时间) 的排序问题，并应用于群体网络计划中去【1 7 1 。张盛开和赵玉鹏 1 8 , 1 9 1 从国内实际出 发提出一种排序问题，给出一类易于应用的计算最优排序的方法。郝中军 2 0 垅1 研究一个 工件可同时在多台机器上加工的问题。吴云从和潘郁、杨建华【2 3 】开发用于中小批量多品 种多工序多机床网络计划和优化排序的“滚动网络计划管理及微机辅助计划管理系统”， 获得1 9 8 9 年江苏省企业管理现代化省级优秀成果一等奖。朱赋 2 4 - 2 7 起初研究流水作业， 1 4 东北大学硕士论文第2 章作业排序文献综述 以后还研究了异序作业问题。程祖伟【2 8 1 和肖耀球2 9 1 曾研究过随机排序。排序问题的应用， 受到越来越多的人的重视，例如，方沛辰、杨晓光和董加礼 s o l ，马俊和胡世熙【3 1 1 ，钱忠 信【3 2 】等在研究排序问题上都做出了自己的贡献。 1 9 9 0 年8 月中国运筹学会在上海召开第一届全国排序学术交流会，标志着我国排序 和时间表的研究和应用进入了新的阶段。来自全国1 6 个省市自治区的7 6 名代表在会上 交流报告5 4 篇论文，并就进一步开展学术交流，推广三参数分类法，修订英汉排序词 汇和关于排序的教学、教材进行讨论。经中国运筹学会的批准，会上成立排序论专业委 员会，挂靠在上海第二工业大学。 进入9 0 年代后，我国研究人员对排序问题的研究进一步深入。陈志龙和赵小平【3 3 j 对于当工件所有工序的加工时间均相等时的四个特殊问题给出了求解最优时间表的多 项式算法。曹宇和宋文忠【3 4 】研究了一类特殊的j o b s h o p 问题广义f l o w s h o p 问题， 提出了一种求解这类问题的启发式算法一逐机排序法。徐晖和王树割3 5 】基于预测控制 的观点，提出了间歇生产过程计算机在线生产调度算法p o m a ，较好地克服了随机干 扰，并显示出很强的鲁棒性。杨正瓴【3 6 】讨论了排序问题串行算法的复杂性，指出降低排 序问题算法时间复杂性的有效途径之一是对元素间的关系有较透彻的了解。黄德才【3 7 】 等人研究了并行加工设备组生产调度的一般模型及两个启发式算法。康一梅和郑应平【3 8 1 针对m i m d 并行机对一般的j o b s h o p 问题提