中小型企业生产调度

某中小企业车间生产调度问题研究

Research on Production Scheduling Problem of Workshop of the Small and

Medium-sized Enterprises

学 院：机械工程学院 专 业 班 级： 学 号： 学 生 姓 名： 指 导 教 师：

年 月

I

摘 要

生产调度在任何企业中都是重要的，肩负着企业的日常生产运转，起着组织、协调、检查、考核的职能。目前，制造业的竞争日益激烈，在企业的日常运作过程中，会经常遇到各种各样的复杂的调度问题，车间生产调度问题解决的好坏直接影响着企业的运作效率和最终客户满意程度。因此，调度问题已经成为运营管理领域的一大研究特点。对其进行深入的研究具有重要的理论意义和实际意义。

本文首先论述本文研究内容的目的和意义，介绍了生产调度问题在国内外的研究现状，分析了该领域中存在的问题及发展趋势。其次结合我国中小型企业的特点，研究了有关车间调度的基本理论，并总结了车间生产调度的优化方法和策略，分析和比较了各种生产调度算法的优缺点，对车间调度问题进行了描述，做出了生产调度问题的改善。在几种求解车间调度的方法中，着重介绍了启发式方法中的palmer算法和彼得罗夫-哈姆算法。

通过对沈阳亚中机械设备有限公司的车间调度问题进行分析和研究，运用palmer算法和彼得罗夫-哈姆算法，对现有的排产顺序进行改善，生产效率提高了28%，提高了企业的竞争力。并对这两种算法进行了比较与选优，来说明生产调度方法的采用必须依具体车间的生产情况来确定。

关键词：中小企业；生产调度；彼得罗夫-哈姆算法 ；帕姆算法

II

Abstract

Production scheduling is important in any enterprise, shouldering the day-to-day production operation of the enterprise, playing the organization, coordination, inspection, evaluation functions. With the increasingly fierce competition in the manufacturing sector, we inevitably encounter a variety of complex scheduling problem in the daily operation of the process, thus shop scheduling problem solving lends a direct impact on the operational efficiency of the enterprise and the ultimate customer satisfaction level, ultimately affecting the ability to respond to business-to-market and competitiveness. Therefore, the scheduling problem has become one of the major study characteristics of the operations management field. Its in-depth study has important theoretical and practical significance.

Based on the small and medium-sized enterprises in the workshop investigation, at first the purpose and meaning of this project are discussed, and the importance of shop production scheduling is presented, the trend of the domestic and overseas research of shop produce and the existent problems in this domain are analyzed. Secondly the basic theories about shop scheduling are studied, and the optimizing means and the strategy of shop production scheduling are summarized, then the interrelated problems of shop scheduling are described, and several heuristic methods to solve shop scheduling are summarized here, and emphatically introduced the heuristic method includes palmer algorithm and Petrov-Ham algorithm, and through the two algorithms for Shenyang ya zhong automatic control potential manufacturing workshop scheduling problem and research, finally to these two algorithms are compared with excellent production scheduling method, to illustrate the production workshop in accordance with specific to determine.

Through the analysis，we improve the job-shop scheduling problem by using the palmer and Petrov Hamm algorithm，enhancing the efficiency by 28%, which make the enterprise become stronger. By comparing these two algorithms, at the same time, we have not only understand them deeply, but realized choosing suited scheduling algorithm must depend on the job-shop environment.

Keywords：Small and medium-sized enterprises；Production scheduling; Petrov-Ham

algorithm; Palmer algorithm

III

目 录

摘 要 ................................................................................................................................... II Abstract ................................................................................................................................... III 第1章 绪论 .............................................................................................................................. 1

1.1 课题研究的目的和意义 ............................................................................................. 1

1.1.1 本课题研究的目的 .......................................................................................... 1 1.1.2 本课题研究的意义 .......................................................................................... 2 1.2 国内外现状和发展趋势 ............................................................................................. 3

1.2.1 国内外研究现状 .............................................................................................. 3 1.2.2生产调度问题研究的发展趋势 ....................................................................... 4 1.3 本课题的主要研究内容 ............................................................................................. 5 第2章 中小型企业车间生产调度的基本理论 ...................................................................... 6

2.1 车间调度的定义 ......................................................................................................... 6 2.2车间调度问题的概述 .................................................................................................. 7

2.2.1 车间生产调度问题的含义 .............................................................................. 7 2.2.2 车间生产调度的类型 ...................................................................................... 8 2.2.3 车间生产调度的特征 ...................................................................................... 9 2.3车间生产调度问题的研究策略 ................................................................................ 10 2.4中小企业车间生产调度问题研究 ............................................................................ 11

2.4.1中小企业的定义 ............................................................................................. 11 2.4.2 我国中小企业的特征 .................................................................................... 13 2.4.3中小企业生产调度的主要问题 ..................................................................... 14

第3章 车间生产的调度方法研究 ........................................................................................ 16

3.1 传统的优化理论与方法 ........................................................................................... 16 3.2 启发式方法 ............................................................................................................... 17 3.3基于知识的调度方法 ................................................................................................ 24 3.4 车间生产调度方法的比较及其评价 ....................................................................... 26 第4章 案例分析 .................................................................................................................... 28

4.1企业背景概述 ............................................................................................................ 28 4.2车间生产调度的管理结构 ........................................................................................ 28 4.3机械加工车间的现状分析 ........................................................................................ 29

IV

4.4生产调度排序改善的案例 ........................................................................................ 32

4.4.1梁板 ................................................................................................................. 32 4.4.2 基于palmer算法零件排序问题求解 ........................................................... 36 4.4.3 基于彼得罗夫-哈姆算法零件排序问题求解 ............................................... 37 4.5 总结 ........................................................................................................................... 40 第5章 结论 ............................................................................................................................ 42 参考文献 .................................................................................................................................. 43

V

***大学本科生毕业设计

第1章 绪论

调度问题来源于不同的领域，如柔性制造系统，生产计划，计算机设计，后勤及通讯等。生产调度，即对生产过程进行计划，作为一个关键模块，是整个先进生产制造系统实现管理技术、运筹技术、优化技术、自动化与计算机技术发展的核心。有效的调度方法及其优化的研究与应用，是实现先进制造和提高生产效益的基础和关键，可大大提高生产效益和资源利用率，进而增强企业的竞争能力。

生产调度问题是一个资源分配问题，只不过这里的资源是设备而己。其目的是使工件加工路径的组合优化，确定工件的加工路径和每一工序的加工开始时间，以确保所选定的生产目标最优，如总加工时间最短等.由于制造系统中每个零件的生产工艺不同，所需的加工设备、加工时间、要求的交货期和生产数量的不同，使得生产调度问题成为自动化制造系统研究中的一个难点和热点。车间生产调度在企业生产经营活动中占有十分重要的地位，生产调度系统也是CIMS(Computer Integrated Manufacturing Systems), ERP(Enterprise Resource Planning)等系统中的重要组成部分，因此受到学术界和工业界的广泛关注，对它的研究具有很高的理论意义和实际意义[1]。

1.1 课题研究的目的和意义

1.1.1 本课题研究的目的

调度决策水平的提高已经成为现代企业生产经营过程能否稳定高效运转的决定性因素之一，因此，对生产调度理论的研究、优化生产调度的算法研究及应用系统软件的开发，都受到学术界和企业界的深切关注。近年来，诸如并行加工、精益生产、准时制生产、异地制造、动态联盟等新模式的不断提出，为信息技术的应用和管理方法的提高指出了更多的新方向。这些新的生产管理模式的出现则要求运用现代生产方式相适应的先进生产管理方法及调度技术。因此，改进型生产管理模式对提高生产效率有很大助益。

有史以来 ，有限资源的合理配置和优化利用问题始终是人类社会所面临的最基本经济问题，这个问题贯穿于社会生活的各个方面。从一个国家、社会的

1

***大学本科生毕业设计

宏观经济运行到具体企业的微观经济活动，都要受资源条件的。对企业来说，能否对现有资源进行合理配置和充分利用将直接影响到产品的制造成本，进而成为影响企业效益的重要因素。企业资源的合理配置和优化利用很大程度上体现在车间一层的生产活动中，所以加强车间层的生产计划与控制一直在企业生产经营活动中占有十分重要的地位。

车间生产调度是制造系统生产管理的核心，生产管理任务顺利实施与完成，最终要靠合理的生产调度来保证[2]。车间生产调度研究的是如何合理地配置加工过程的各种资源，减少零件的加工准备、等待与传送时间，从而提高设备利用率与生产效率，降低生产成本。因此，及时准确的生产调度对生产系统的高效运行有着重要的影响，主要表现在生产调度可以保证生产计划的有效实施:高效低耗地使用生产资源;均衡生产，减少在制品的资金占用等。 1.1.2 本课题研究的意义

生产计划与调度环节是企业生产管理的核心，也是整个企业管理最烦琐和最难管理的环节。随着工业生产过程的日益复杂与规模的大型化，要求计算机系统不仅要完成直接面向过程的控制和优化，而且要在获取生产全部过程信息基础上，进行指挥调度和综合管理。生产调度的优化是先进制造技术和现代管理技术的核心技术。优化生产计划与调度成为增强企业竞争力、提高企业经济效益和社会效益的关键因素。因而研究制造行业大规模复杂生产过程的生产调度问题与方法对于提高企业的管理水平，增强企业的竞争力，促进整个行业的进步与发展具有十分重要的意义。

目前，国内的大部分企业主要依靠经验丰富的调度员手工安排调度计划。对于调度问题比较简单的情况下这种办法还是可行的，然而，在调度任务规模较大且动态多变的环境中，单纯的手工调度就显得低效甚至为力了，况且，对于企业来说，经验丰富的调度员本身就是一种稀缺资源。显然，充分利用目前己取得的理论研究成果，改善车间调度问题，帮助企业提高排产效率，对于我国的生产有着重要的现实意义。

2

***大学本科生毕业设计

1.2 国内外现状和发展趋势

1.2.1 国内外研究现状

随着科学技术的快速发展，尤其是网络技术、通讯技术、计算机技术等现代科技以及相关基础行业的技术进步，使传统意义上的时间和空间距离日益被拉近缩短，市场趋向全球一体化，市场竞争转型为异地、跨区域、甚至竞争等，激烈的市场竞争使产品的更新代换日趋频繁、种类越来越复杂，因而要求制造系统既能有效地进行多品种、小批量的生产，又有较高的自动化程度和生产效率，以适应多变的市场环境和客户需求。这就意味着相关企业在具有较高生产率、较好质量保障能力的同时，也要具有快速的响应市场变化和需求增长的能力，努力使制造单元具有刚性生产线的效率和工作车间的柔性，才能使企业适应激烈的市场竞争。为了加强和改善生产管理模式，提高加工单元(包括加工车间)的柔性及响应市场需求速度，在许多企业中生产调度(尤其是具体到车间调度)当前仍然采用本地化、单机实现模式，乃至人工方式进行。

早在1954年，Johnson就对两台机床的Flow Shop型调度问题进行了研究，并提出了一个简便而又相当巧妙的算法。他的研究成果引起了学术界的浓厚兴趣。于是，学术界试图将他的结果推广到三台或是更多的机器上去，但是都没有成功。直到1977年，才有研究证明三台以上机床的Flow Shop调度问题是一个NP完备问题。由于车间调度在调度问题中具有代表性，很多领域的学者都可以把各自领域的组合优化问题抽象为车间调度问题。因此，众多学者就车间调度问题展开了深入广泛的研究。

国外对车间管理系统的研究主要着重于对FMS的应用研究，因为一些制造企业，如飞机或汽车制造公司，资金力量和科技力量较为雄厚，它们直接进行了有关FMS的研究与开发，并且取得了较为明显的效果‘例如美国底特律市郊的鲁奇工厂是汽车制造的传统中心之一，这家工厂一直是福特公司的总裁兼首席执行官、亨利的曾孙比尔·福特的商业理念的实践场所。但现在它似乎发生着戏剧性的变化：比尔·福特已经斥资20亿元改造该公司慢慢老化的这个制造中心，他正设法建立精简灵活的生产线，并使其能够成为现代汽车的生产发展方向。

3

***大学本科生毕业设计

日本的本田公司在灵活生产的道路上可能走得最远，不仅本田公司所有的汽车工厂都能生产几种车型的汽车，而且现在各个分厂还能迅速实现装配不同车型的转换。在底特律一家工厂要4到6周才能改变生产的汽车车型，重装自动机械装置和其它工具。而本田公司现在能一夜间完成这一项工作，它只需要简单地更换控制自动机械装置的有关软件。虽然，这是多方面因素的综合结果，例如全球供应链等因素，但如果本田公司没有采用灵活多变的FMS，就不可能有如此快的响应速度[3]。

在对车间调度问题进行的研究中，有许多方法在各种各样的有关决策的期刊中被报道，它们在不同程度上都获得了成功。这些方法无一例外地吸收了近35年来的一系列先进技术。这些技术包括数学规划(mathematical programming),专家系统(expertsy stems)、神经网络(neuralne tworks)、遗传算法(genetical gorithms)和模糊逻辑(fuzzy logic)等。不同学科的交叉，带来了车间调度领域众多的新兴理论和新方法。

国内对车间管理软件的研究起步较晚，目前虽然大部分工厂都在实施ERP软件系统，由于技术上的制约，它们仍然没有找到好的车间作业调度方法，基本上是靠调度人员的经验进行车间作业分配和调度。随着遗传算法在作业调度方面的应用，我国“八五”期间也有一些高校和研究机构，例如清华大学、上海交通大学、西安交通大学、北京机械工业自动化研究所等进行此类问题的研究，并已开发出相应的计算机辅助生产调度与管理系统，逐步从理论研究阶段走向应用阶段.随着各种特殊调度问题的攻克和新方法、新设备的出现，车间调度研究正在向动态、敏捷、多资源、智能化的方向发展[4]。 1.2.2生产调度问题研究的发展趋势

虽然对车间调度领域的研究已有几十年的历史，但至今尚未形成一套系统的方法与理论，并且多数研究忽略了很多重要的因素，建模时对真实环境进行了大量的简化，离应用尚有不小的差距。车间制造系统的建模与描述是研究调度问题的出发点，由于制造过程的复杂性，且纯仿真模型、数学规划、控制论、图与网络的建模方法各有优缺点，所以目前尚难建立一个很有效的模型。且现行的研究大多只关心工件的调度问题，而对其他资源分配问题像刀具、物料储运系统的研究不多[5]。因此，未来的进一步研究，我们可以从生产调度的有关

4

***大学本科生毕业设计

模型中得到启示(如异地生产调度问题的深入研究)；此外一般来讲，调度方法的搜索效率和搜索效果是相互矛盾、相互制约的，通常根据实际情况，需要在两者之间做出折衷的选择。

总之，对车问调度领域这一具有NP hard特性的研究，随着应用数学理论的进一步发展，必然朝着集成化、多目标化、动态实用化、高度次优化方向深入进行。

1.3 本课题的主要研究内容

车间生产调度问题是企业生产运作管理中最复杂、最棘手的问题。从理论上讲，人们经过长期的实践摸索出了许许多多的生产调度方法，而本论文的研究不可能也不必要穷尽一切理论，课题研究的主要内容是生产调度问题的描述方法，流水线车间调度基本理论和调度方法，并针对我国中小型企业车间生产调度管理的实际情况，摸索如何应用先进实用的生产调度方法去解决企业长期存在的一些问题。

本文总体上是按照如下的线索逐步进行的：绪论，车间生产调度的基本理论，车间生产调度的研究方法与评价，应用案例分析，全文总结。

第一章为绪论，为全文的纲领，介绍了课题的研究背景、研究目的和研究意义。

第二章是对车间生产调度理论知识的研究介绍，由浅入深，由基础的知识概念入手，循序渐进到中小企业的生产调度问题，最后具体到提出生产调度的问题描述相关问题，包括生产调度的分类、特点、研究策略。

第三章主要内容是基于车间生产调度问题的研究方法，包括数学规划法、启发式方法、计算智能调度方法。主要研究启发式方法中的彼得罗夫-哈姆算法和palmer算法。并通过调度方法的比较和评价来说明调度方法的相对权重。

第四章是对沈阳亚中机械设备有限公司运用车间调度方法来对该企业的零件加工进行改善，并应用彼得罗夫-哈姆算法和palmer算法来验证算法的可行性，同时对这两种算法进行选优，并对该企业车间调度状况进行分析，提出相应意见。

5

***大学本科生毕业设计

第2章 中小型企业车间生产调度的基本理论

2.1 车间调度的定义

车间调度就是根据加工对象的加工需求，运用不同的调度决策规则，规划系统的加工事件，并根据优化结果形成最佳的生产加工顺序，同时实现设备集和任务集的合理最优化结合[6]，如图2-1所示。

设备集 图2-1生产调度问题的传统定义

实际生产调度问题虽然不能简单地归结为上述的排序问题，但是都是以这一问题作为基础的。与经典调度理论中的生产调度问题相关的基本概念主要有：

1)加工任务

加工任务通常是一组n个等待调度以便进行加工的工件或者原材料。在其他相关文献中叫法不一，有的称作要加工的工件，有的称作要生产的产品，我们在本文中统称为加工任务。

2)机器

机器指的是执行加工任务的一组生产设备或生产单元，各台机器都有自己的生产能力约束。

3)工序

工序指的是某个工件或者产品的工艺路线，也就是加工任务在一组机器上的执行顺序。

4)时间参数

策略、优化算法 任务、设备对序列 加工任务集 约束集 6

***大学本科生毕业设计

与加工任务和机器有关的各种时间参数，如加工任务的准备时间、等待时间、计划完工时间、实际完工时间、拖期时间、交货时间、在某个机器上的加工时间以及机器的空闲时间等。

5)性能指标

生产调度方案要达到的性能指标，如完工时间目标(最大流程时间、平均流程时间、最大完工时间、平均完工时间等)、交货期目标、成本目标和机器利用率目标等。

6)控制参数

与物料供应和投入有关的各种参数，如物料供应的约束、物料投入生产的时间、地点、速度和数量等。 7)调度规则

调度规则指的是一组控制生产过程的规则，主要有生产时序控制规则(各种优先规则)、中间存储利用率调节规则和生产代价调节规则等。

8)调度算法

调度算法的目的就是要综合考虑调度问题所提出的一些具体要求，用数学的语言来表达这些要求，在给定时间参数和调度规则条件下，确定各种控制参数，使得一种或多种性能指标最优[7]。

2.2车间调度问题的概述

车间调度问题一般可以描述为:n个工件在m台机器上加工，一个工件分为k道工序，每道工序可以在若干台机器上加工;每一台机器在每个时刻只能加工某个工件的某道工序，且只能在上道工序加工完成后才能开始下一道工序的加工。前者称为占用约束，后者称为顺序约束。 2.2.1 车间生产调度问题的含义

车间生产调度就是对一个可用的加工机床集在时间上进行加工任务的分配，以满足一个性能指标集[8]。典型的车间生产调度问题包括一个要完成的作业集，每项作业由一个作业集组成。各操作的完成需要占用机床或其它资源，并且必须按一个可行的工艺次序进行加工;每台机床可加工零件的若干操作，并且在不同机床能加工的操作集可以不同。在约束条件下，调度的目标是将作业合

7

***大学本科生毕业设计

理地安排到各机床，并合理安排作业的加工次序和加工开始时间，同时优化一些性能指标。在实际车间生产调度中，一般需要考虑两个方面的调度问题，一是生产作业的调度，二是生产资源的分配。目前大部分研究集中在生产作业调度上，没有考虑资源分配，而将资源作为约束处理。

厂级编制的车间作业计划，给出了各种零件、部件的投入产出进度安排，但还不是车间的执行计划。车间还要对各项任务的作业顺序合理安排，分派各班组、各工作地的任务，以便在完成计划任务的前提下，缩短生产周期，均衡设备负荷，提高操作人员的工作效率，取得良好的经济效益.生产作业的这种细节安排是车间生产调度控制的重要一环，它建立了计划与生产控制间的直接联系，是厂级各车间生产管理人员所必须研究的一个更重要的课题。 2.2.2 车间生产调度的类型

生产调度主要是在生产作业计划的基础上确定生产任务的加工顺序以及各种制造资源的实时动态调度[9]。确定生产任务的加工顺序为作业排序问题，它有不同的分类方法：

1)生产来源

根据需求产生的来源将车间可分为开环车间和闭环车间。 2)加工系统的复杂度

根据加工系统的复杂度可以将其分为单台处理机、多台并行机、车间作业调度(Job Shop)和流水车间调度(Flow Shop)。

单台处理机调度(Single Shop):在这种车间中，每个零件只能有一道工序。单机调度问题是最简单的形式，在这种情况下，要求每个加工任务都要在一台机器上执行一次，为此存在任务的优化排队问题。

多台并行机调度:井行机调度问题与单机调度问题有些相似，不同的是每个加工任务可以在任意一台机器上加工一次，它比单机调度问题的优化问题更为突出。

车间作业调度(Job Shop):这是最一般的调度类型，并不作业操作的加工设备，并允许一个加工任务具有不同的加工路径，在这种车间中，机床设备的布局可以是任意的，因此零件的加工路径也是任意的，并且各零件的工序内容和数量也是任意的。

8

***大学本科生毕业设计

流水车间调度(Flow Shop):这种调度问题假设每个加工任务都要在所有工序中的机器上加工一次，并有一致的加工操作和加工顺序;在这种车间中，每个零件都有相同的加工路径。这样，机床设备的布局如同流水线一样，零件依一次从流水线的一端流进，最后从另一端流出。

3)性能指标

根据性能指标可以分为基于调度费用和调度性能的指标。 4)生产环境

根据生产环境的特点将调度问题分为确定性调度和随机性调度。 5)加工特征

加工任务或被加工工件的特征主要表述为加工任务或者被加工工件是否有优先制约、以及其他各种类型的约束条件、任意释放期或等释放期、任意加工时间或单位加工时间、加工任务是否需要拆分和组合等。根据这一点可以把生产调度问题分为静态调度问题和动态调度问题两大类。

静态车间调度(Static Scheduling):静态调度是指所有待安排加工的加工任务或工件均处于待加工状态，进行一次调度之后，各个加工任务或工件的加工顺序就被确定，在以后的加工过程中就不再改变。车间的调度不考虑零件在加工过程中出现的意外情况，如机床突然损坏、零件的交货期提前、有更紧迫的零件要求被加工等等。

动态车间调度(Dynamic Scheduilng):动态调度是指加工任务或工件依次进入待加工状态，各个加工任务或工件不断进入系统接受加工，同时完成加工的加工任务或工件又不断离开，还要考虑加工环境中不断出现的不可预测的动态扰动，如操作的超时和设备的损坏等，因此动态调度要根据系统中加工任务或工件、设备等的状况，不断地进行调度。

6)是否有序

根据调度是否有序可以讲价共分为有序加工和无序加工。 2.2.3 车间生产调度的特征

1)复杂性

一是生产因素的多样与复杂，车间中工件、机器、缓存和搬运系统之间相互影响、相互作用。每个工件又要考虑它的加工时间、安装时间和操作顺序等

9

***大学本科生毕业设计

因素，因而相当复杂;二是调度问题是在等式或不等式约束下求指标的优化，在计算量上往往是NP完全问题，随着问题规模的增大，其计算量急剧增加，使得一些常规的方法为力，对于这一点已经被证明。所以调度问题往往没有精确的解，通常是在解答过程中寻求其最优解[10]。

2)随机性

车间调度中有很多随机和不确定因素，如工件到达时间的不确定性，实际工件的加工时间也有一定的随机性。而且生产系统中常有突发偶然事件，如机器出故障、作业交货期的改变、急件插入和人员误操作等不可预见因素，生产调度需要根据生产情况做出动态调整。

3)约束性

车间调度问题中资源的数量、缓存的容量、工件到期时间以及工件的操作顺序等都是约束。此外还有一些人为的因素，如要求各机器上的负荷要平衡等。

4)多目标

车间生产调度往往是多目标的，可分为基于作业交货期的目标、基于作业完成时间的目标和基于生产成本的目标，而且这些目标之间往往是有冲突的。

2.3车间生产调度问题的研究策略

调度策略是车间调度高层次的决策部分，由于调度问题的复杂性，因而在实际的研究过程中逐渐形成了不同的调度策略支持，大致可分为以下几种。

1)并行或分布策略。适应不同车间控制结构与调度问题复杂性的实际需要，不少学者提出并行或分布策略来解决调度问题。

2)分解与成组策略。利用分解生产计划或GT的调度策略可以大大降低问题的计算复杂性和规模，求得调度问题的较优解，同时优化系统的一些性能指标，GT和制造岛的应用实践便是一个明显的例证。

3)人机协同策略。调度问题的性质、现有研究方法的缺陷以及人类独特的思维能力决定了人机协同策略的生命力。大量的研究成果表明：人机协同交互的策略可以减少系统的搜索空间，可在有限时间、背景知识条件下解决困难的问题。

4)实时或动态重调度策略。车间制造过程的随机性、不确定性需要不断地进行重调度，以处理突发的事件。基于目前的研究，对于动态调度的具体策略有：

10

***大学本科生毕业设计

周期调度，连续调度，事件驱动调度，周期与事件驱动混合调度，周期与连续调度混合的策略等。

5)生产计划与调度集成策略。生产计划、调度的集成研究具有全局优化的特征，也符合先进制造模式的思想。

6)多目标权衡决策。实际调度问题是多目标的，且这些目标往往相互冲突。对于此类多目标优化问题，常用数学规划中的约束法、评价函数法、分层序列法(AHP)、功效函数法等。

2.4中小企业车间生产调度问题研究

2.4.1中小企业的定义

不同国家、不同经济发展的阶段、不同行业对其界定的标准不尽相同，且随着经济的发展而动态变化。各国一般从质和量两个方面对中小企业进行定义，质的指标主要包括企业的组织形式、融资方式及所处行业地位等，量的指标则主要包括雇员人数、实收资本、资产总值等。量的指标较质的指标更为直观，数据选取容易，大多数国家都以量的标准进行划分，如美国国会2001年出台的《美国小企业法》对中小企业的界定标准为雇员人数不超过500人，英国、欧盟等在采取量的指标的同时，也以质的指标作为辅助[11]。

根据第九届全国人民代表大会常务委员会第二十八次会议于2002年6月29日通过的《中华人民共和国中小企业促进法》的精神，工业和信息化部、国家统计局、国家发展和改革委员会 财政部于2011年6月18日发布了《中小企业划型标准规定》，对主要行业的中小企业的标准作出了明确的界定。该标准是根据企业职工人数、销售额、资产总额等指标，结合行业特点制定的。按照《通知》的规定，不同行业的中小企业应该按照以下标准认定：

1)工业。从业人员1000人以下或营业收入40000万元以下的为中小微型企业。其中，从业人员300人及以上，且营业收入2000万元及以上的为中型企业；从业人员20人及以上，且营业收入300万元及以上的为小型企业；从业人员20人以下或营业收入300万元以下的为微型企业。

2)农、林、牧、渔业。营业收入20000万元以下的为中小微型企业。其中，营业收入500万元及以上的为中型企业，营业收入50万元及以上的为小型企业，

11

***大学本科生毕业设计

营业收入50万元以下的为微型企业。

3)建筑业。营业收入80000万元以下或资产总额80000万元以下的为中小微型企业。其中，营业收入6000万元及以上，且资产总额5000万元及以上的为中型企业；营业收入300万元及以上，且资产总额300万元及以上的为小型企业；营业收入300万元以下或资产总额300万元以下的为微型企业。

4)批发业。从业人员200人以下或营业收入40000万元以下的为中小微型企业。其中，从业人员20人及以上，且营业收入5000万元及以上的为中型企业；从业人员5人及以上，且营业收入1000万元及以上的为小型企业；从业人员5人以下或营业收入1000万元以下的为微型企业。

5)零售业。从业人员300人以下或营业收入20000万元以下的为中小微型企业。其中，从业人员50人及以上，且营业收入500万元及以上的为中型企业；从业人员10人及以上，且营业收入100万元及以上的为小型企业；从业人员10人以下或营业收入100万元以下的为微型企业。

6)交通运输业。从业人员1000人以下或营业收入30000万元以下的为中小微型企业。其中，从业人员300人及以上，且营业收入3000万元及以上的为中型企业；从业人员20人及以上，且营业收入200万元及以上的为小型企业；从业人员20人以下或营业收入200万元以下的为微型企业。

7)仓储业。从业人员200人以下或营业收入30000万元以下的为中小微型企业。其中，从业人员100人及以上，且营业收入1000万元及以上的为中型企业；从业人员20人及以上，且营业收入100万元及以上的为小型企业；从业人员20人以下或营业收入100万元以下的为微型企业。

8)邮政业。从业人员1000人以下或营业收入30000万元以下的为中小微型企业。其中，从业人员300人及以上，且营业收入2000万元及以上的为中型企业；从业人员20人及以上，且营业收入100万元及以上的为小型企业；从业人员20人以下或营业收入100万元以下的为微型企业。

9)住宿业。从业人员300人以下或营业收入10000万元以下的为中小微型企业。其中，从业人员100人及以上，且营业收入2000万元及以上的为中型企业；从业人员10人及以上，且营业收入100万元及以上的为小型企业；从业人员10人以下或营业收入100万元以下的为微型企业。

10)餐饮业。从业人员300人以下或营业收入10000万元以下的为中小微型

12

***大学本科生毕业设计

企业。其中，从业人员100人及以上，且营业收入2000万元及以上的为中型企业；从业人员10人及以上，且营业收入100万元及以上的为小型企业；从业人员10人以下或营业收入100万元以下的为微型企业。

11)信息传输业。从业人员2000人以下或营业收入100000万元以下的为中小微型企业。其中，从业人员100人及以上，且营业收入1000万元及以上的为中型企业；从业人员10人及以上，且营业收入100万元及以上的为小型企业；从业人员10人以下或营业收入100万元以下的为微型企业。

12)软件和信息技术服务业。从业人员300人以下或营业收入10000万元以下的为中小微型企业。其中，从业人员100人及以上，且营业收入1000万元及以上的为中型企业；从业人员10人及以上，且营业收入50万元及以上的为小型企业；从业人员10人以下或营业收入50万元以下的为微型企业。

13)房地产开发经营。营业收入200000万元以下或资产总额10000万元以下的为中小微型企业。其中，营业收入1000万元及以上，且资产总额5000万元及以上的为中型企业；营业收入100万元及以上，且资产总额2000万元及以上的为小型企业；营业收入100万元以下或资产总额2000万元以下的为微型企业。 14)物业管理。从业人员1000人以下或营业收入5000万元以下的为中小微型企业。其中，从业人员300人及以上，且营业收入1000万元及以上的为中型企业；从业人员100人及以上，且营业收入500万元及以上的为小型企业；从业人员100人以下或营业收入500万元以下的为微型企业。

15)租赁和商务服务业。从业人员300人以下或资产总额120000万元以下的为中小微型企业。其中，从业人员100人及以上，且资产总额8000万元及以上的为中型企业；从业人员10人及以上，且资产总额100万元及以上的为小型企业；从业人员10人以下或资产总额100万元以下的为微型企业。

16)其他未列明行业。从业人员300人以下的为中小微型企业。其中，从业人员100人及以上的为中型企业；从业人员10人及以上的为小型企业；从业人员10人以下的为微型企业。 2.4.2 我国中小企业的特征

1)企业组织结构层次简单

中小企业的组织结构层次非常少，部门分划的也不是很细，一般主要的管

13

***大学本科生毕业设计

理都是由一个人到两个人来进行，只有当这个决策者通过检查之后才能进行生产，这样就降低了企业的生产效率。

2)企业特殊的生产运作模式

随着现代社会生产分工的细化, 相当大部分的中小企业都作为大型企业的辅助性制造商。这就决定了中小企业对大企业的依存关系, 而这种相互依存的关系又会影响中小企业内部和外部供应链网络的设计。在主要的客户级和企业级都需要搜寻清晰的供应链指令, 这将迫使中小企业的项目管理目标失去性, 需要根据大企业的生产变化进行适应性调整或重新安排, 所以中小企业中的采购、生产、销售等运作特征同那些大企业相比有着明显的不同。

3)企业内部管理人员职责模糊

在中小企业中, 各部门之间在职责上没有清晰的界线。企业管理人员职责的模糊性, 究其原因在于中小企业的规模小、组织结构简单。一般说来, 企业的规模越大,其要求企业的组织结构就越复杂, 部门之间分工就越明确;而中小企业规模小, 对应地其组织结构就显得简单, 组织的正规化程度低, 从而部门之间的分工就模糊。

4)企业实际生产与计划预测的偏离较大

实际生产与计划的偏离非常显著, 主要有两种表现形式: 实际生产的成品和生产的数量。随着产品生命周期的缩短, 大型企业不断地改进新的产品形式甚至向市场上频繁推出全新产品。中小企业通常都是第三方辅助性制造商,它们的成品生产很大程度上依赖于那些大企业要卖些什么产品。因此, 对于中小企业来说, 每年的计划和预测只能作为企业生产和销售的一个粗略指导方针, 而根本不能作为企业的实际生产计划[12]。 2.4.3中小企业生产调度的主要问题

1)由于中小企业资金的不足，照成车间设备的先进程度不够，同时设备的定期维修做的不够好。车间设备的工作环境也不尽人意。

2)由于没有建立基本的生产管理信息系统，因此生产信息零乱而分散。通常情况下，许多信息对指挥下一个生产周期、下一天、甚至下一个小时的生产都很重要。在手工处理方式下要靠调度对纸质资料逐个查询，现场查问或测试、手工记录并统计汇总，不仅工作量大，而且速度较慢，难以提高工作效率，且

14

***大学本科生毕业设计

很难实现加工车间与其他职能部门的信息。

3)车间作业调度上，一般是根据经验来安排零件的加工，由于设备数量少且分布较分散，因而极易造成设备负荷的不均衡与增加设备的空闲时间，同时，由于人为因素对生产影响较大，增加了生产的随机性。导致不可预见的问题随时都可能发生。

4)对零件的加工工时与设备利用情况无法进行定量分析，造成编制生产计划与进行生产调度决策的依据不足。导致对产品不能均衡成产。

5)对许多与生产有关的数据由于受工作量未予记录，或记录不完整、不规范，难以追查某些由于管理失误而引起的责任事故。即便已记录的数据在统计汇总中也难免发生错误，这些都难以满足现代企业管理中用数字说话，实现科学管理的要求。

6)调度工作缺乏预见性和预防性。在生产过程中，经常会遇到一些突发性问题，这要求调度人员及时调整作业计划；同时，调度工作要以防为主，必须避免被动地抓缺件、堵漏洞的消极做法，而这些不借助于计算机，单独依靠人工管理是难以实现的。

15

***大学本科生毕业设计

第3章 车间生产的调度方法研究

调度问题的研究方法经过五十多年的发展，经历了由简单到复杂，从一元到多元的过程。从中也诞生了许多算法，一般的调度问题都是对于具体生产环境中的复杂的、多目标、动态的调度问题的一种抽象和简化，因而对一个调度算法可以通过其如何表述这些复杂性进行分类。而能否适应千差万别的实际生产环境，能否取得令人满意的优化效果，就成为了评估这一个调度算法的主要标准。有关调度问题的研究方法最初集中在数学规划、系统仿真和简单的规则上，这些方法不是调度结果不理想就是难以解决复杂的实际调度问题。随着各种新的相关学科与优化技术的建立和发展，在调度领域出现了许多新的优化方法，这些方法对解决车间调度问题具有重要意义[13]。

本文大体介绍了整数规划法，启发式方法，计算智能调度方法，这些方法己经成为调度方法的主流。本文着重介绍了启发式算法，并通过与其他算法的比较来说明启发式算法的优缺点。

3.1 传统的优化理论与方法

1)整数规划法：通过对车间调度问题建立一个整数规划模型，采用基于枚举思想的分支定界法、割平面法和0-1整数规划法进行求解[14]。 这类方法虽然从理论上能求得最优解，但由于其计算复杂性， 不能获得实际应用。

2)多目标优化法：多目标优化方法是同时考虑不同目标的共同作用。对于给定的多个目标按各自的重要程度，分别乘以不同的权系数，然后相加得到目标函数，再对此目标函数在多目标的约束集合上求最优解，也可以选择一个优化目标作为主要目标，而将其他目标作为约束处理，转化为一个新约束条件下，求主要的单目标最优化问题。多目标优化能体现不同目标的重要程度，但它通常只能寻找满足约束条件的满意解[15]。

3)动态规划法：由于车间生产过程的动态性，系统运行中任何约束条件的改变，都可能使原先求得的最优解失效。利用动态规划法，将车间生产调度过程按时间划分为若干个相互联系的阶段，列出各阶段决策过程的函数方程，并利用动态规划的最优化原理进行求解，使整个过程的总效果达到最优。动态规

16

***大学本科生毕业设计

划将求解问题分解成多阶段进行，使复杂问题简化，递推求解过程中可以利用实际应验，提高求解效率。但是动态变量必须满足无后效性，使动态变量不仅依赖状态转移规律，还依赖于允许决策集合和指标函数结构，从而降低了它的通用性[16]。

3.2 启发式方法

启发式方法因易于实现、计算复杂程度低等原因，能够用于动态实时调度系统中，一直受到人们的关注，并进行了广泛的研究。

1)优先调度规则:

优先规则是按时间进程逐次为每台设备安排一个加工对象时，按照某种规则，从候选的等待作业中选取优先级最高的作业安排加工的方法。优先规则可根据不同的优化目标制定，不受零件数、工序数与工艺路线的，因此应用也比较广泛。常见的简单规则与组合优先规则分别见表3-1与表3-2：

表3-1常见的简单优先级规则

序号 1 2 3 4 5 6 7 8 9 10 11 12 13 14

规则名称 EDD FCFS LCFS JP LWKR MWKR FOPNR MOPNR SPT LPT SLACK NINR WINQ RANDOM

含义 交货期最早 先进先出 后进先出 工件优先值 剩余加工量最小 剩余加工量最大 剩余工序数最少 剩余工序数最多 加工时间最短 加工时间最长 最小松弛量

下工序等待作业数最少 下工序等待作业加工量最小 随机

17

***大学本科生毕业设计

其中零件松弛量-交货期-当前时刻-剩余加工时间，当零件松弛量为负时，表明其不能按期交货。

优先权规则是设定每一零件、设备的优先等级，优先响应优先级高的申请对象[17]。启发式规则，如Look Ahead规则主要研究当用简单规则选择作用时，所选作业在处理过程中对另一作业的影响。可能受影响的作业是到达队列等待服务的作业。 Look Ahead 规则允许在某一加工设备空闲时间插入一个加工时间不大于某值的零件加工，其动态性较好。

SPT是应用最广泛的一种调度规则，它对所有基于零件完工时间的指标都有较好的效果，如平均生产周期、平均延迟时间、设备负荷率等。旨在降低车间在制品占用量为目标的作业排序一般都用SPT。其缺点是对公序时间长的作业，越长越往后排，容易造成加工量大的作业产生延误，而加工量大的作业往往是生产中的关键零件，因而对生产计划的完成产生加大影响。LPT与SPT相反，优先考虑加工时间长的零件，但又显著地增加了零件在生产中的平均等待时间，及增大了生产中在制品占用量。

MWKR是考虑剩余加工量大的作业容易延迟固优先安排。对于要成套地投入装配的零件，可以有效地缩短零件组的总生产周期。LWKR则是使加工进度快的零件加速完成。

MOPNR是优先安排剩余工序数最多的作业，与MWKR相似，目标是缩短零件组的生产周期。所不同的是他考虑了工序间转移和等待时间，这部分时间往往比加工时间长得多。MOPNR与MWKR相似，其目标也是减少车间内的在制品量。

SLACK是促使计划能按期完工的一种重要的优先级规则。由于考虑到交货期与当前时间的关系，在于交货期有关的方面表现出优越性，如平均延迟、满足交货期的零件比例等。

FIFO对减少零件平均通过时间是较优的，常用于flow-shop型的加工车间。 NINR、WINQ与前述的规则不同，它考虑的不仅是当前等待作业集合的状况，而且要预测下工序等待作业集合中零件的状况。原则上是不选取那些在下工序因等待集合中作业拥挤而受阻的作业，而是优先选取能顺利投入加工的作业。其目标是加快生产进度，缩短零件的平均生产周期。

在多数情况下，使用符合规则比使用简单规则会取得更好的效果。如以SPT

18

***大学本科生毕业设计

为第一规则，再以固定间隔检查队列，用FCFS使等待过久的零件出队加工，会使作业完成时间与提前/延迟指标都达到理想效果。

表3-2常见的组合优先级规则

序号 1 2 3 4

以上这些优先调度规则的简单性掩饰了排序工作的复杂性。实际上要将数以百计的工件在数以百计的工作地(机器)上的加工顺序决定下来，是一件非常复杂的工作，需要有大量的信息和熟练的排序技巧。对于每一个准备排序的工件，调度人员都需要两大类信息:有关加工要求和现在的状况。加工要求信息包括预定的完工期、工艺路线、标准的作业交换时间、加工时间、各工序的预计等待时间、各工序的可替代设备以及各工序所需的原材料和零件等等。现状信息包括工件的现在位置(在某台设备前排队等待或正在被加工)，现在完成了多少工序(如果已开始加工)，在每一工序的实际到达时间和离去时间，实际加工时间和作业交换时间，各工序所产生的废品(它可以用来估计重新加工量)以及其它的有关信息。优先顺序规则就是利用这些信息的一部分来为每个工作地决定工件的加工顺序，其余的信息可以用来估计工件按照其加工路线到达下一个工作地的时间、当最初计划使用的机器正在工作时是否可使用替代机器以及是否需要物料搬运设备等等。这些信息的大部分在一天中是随时改变的，所以，用手工获取这些信息几乎是不可能的或效率极低的。从这个意义上来说，计算机是用来进行有效的、优化的作业排序的重要工具[18]。

2)随机抽样法

规则名称 SPT^TOT SPT/TOT SLACK/FOPNR SLACK/LWKR

含义

最短加工时间与总加工时间的乘积最大 最短加工时间与总加工时间之比最大

松弛时间与剩余工序数之比最大

松弛时间与剩余加工量之比最大

19

***大学本科生毕业设计

用穷举法和分支定界法，考虑了全部能动作业顺序。而采用优先调度规则方法，实际上只选择了一种作业顺序。随机抽样法是介于两者之间的一种方法，他从全部能动的作业排序集中抽样，他从全部能动的作业排序集中抽样，得出多个排序方案，经过比较，从中选优。随机抽样法实际上是对一个问题多次运用Random法则，从而获得多个排序方案，他不一定能得到最优解，但计算量比穷举法或分支定界法小，又比优先调度规则法只取一个样的方法所得的结果要好。其效果与样本大小有关，样本越多，获得较好解的可能性越大，但花费时间也越多。

3) palmer算法

1965年，D.S.Palmer提出了基于工件的加工时间按斜度顺序指标(slope orderindex)排列工件的启发式算法，称之为palmer法[19]。其基本思想是给每个工件赋以优先权数。按机器的顺序，加工时间趋于增加的工件得到较大的优先数。工件的斜度指标可按下式计算:

i[k(m1)/2]tikk1mk1,2..n. . . （3-1）

式中：m为机器数；tik为工件i在Mk上的加工时间。按照各工件不增的顺序排列工件，可得出令人满意的顺序。即构造如下工件加工顺序：

ii...i

12nPalmer算法的优点是具有构造调度解的快速性，而且计算量也特别小，可以快速的获得一个近似解，十分实用。因而常能由缺乏高级训练的实践者来实现;不需要很多的计算时间，这意味着能显著地节省开支。palmer算法是很灵活的，在考虑许多方案和不能用定量表示约束集合时，常能把它作为制订计划的工具。

但是palmer算法也有其不足之处。palmer算法的明显不足是害怕所产生的解比全局最优解差得多，调度质量不是特别理想。当机器数量多的时候，这种算法求出的解的最优性就受到了，不如其他的调度算法精确，而且差的程度总是不太清楚。因此合理的计算时间以及所求出的解的最优性就成为衡量

20

***大学本科生毕业设计

palmer算法性能的标准。要在计算时间和求解最优性这两方面都达到较高的要求是非常困难的，因此对于palmer算法的设计来说，与其说是一门科学，不如说是某种经验或技巧。该算法适用于机器数量m>2的中小企业的调度问题求解。

4)彼得罗夫—哈姆算法

彼得罗夫—哈姆算法是从约翰逊算法演变而来的，它研究的是一组零件在生产单元中不同机床加工时的作业排序问题和若干零件组之间的排序问题[20]。

(1)确定一个零件组内各零件的排产顺序

彼得罗夫—哈姆算法的原理如下:设某一零件组在某个生产单元加工，零件组内有零件n种，生产单元有设备m台。每种零件在每台设备上的一批加工时间为与tij,从而得到时间矩阵，如表3-1所示。

表3-3 n种零件和m台设备构成的时间矩阵

t1 t2 … tn

hk1M1 t1,1 t2,1 tn,1 … M2 t1,2 t2,2 tn,2

… … … … … …

Mn t1,n t2,n tn,n … 彼得罗夫运用约翰逊算法原理，将m台机床分为两部分：(M1、M2……Mh)与(MH、MH+1……Mn)。相当于将(M1、M2……Mh)看成一台为M的机床，把后面的(MH、MH+1……Mn)看成一台为M′的机床。这样便将m台机床转化为M与M′两台机床。相对地，表3-3的时间矩阵也划分为两个部分，如表3-4,3-5所示。

第i种零件在机床M、M′上的一批加工时间总和分别为：

Titi,k i1,2..n. . . (3-2)

TikHtmi,k

i1,2..n. . . (3-3)

21

***大学本科生毕业设计

当机床数m为偶数时，h=m/2，H=m/2+1；当m为奇数时，h=H=(m+1)

表3-4 将m台机床划分为两机床M与M′的时间矩阵（1） t1 t2 M M1 t1,1 t2,1 M2 t1,2 t2,2 „ „ „ Mh t1,h t2,h … tn

tn,1 MH t1 t2 t1,H t2,1 … hk1…tn,2 …„ tn,h … T1t1,k (3-4)

T2t2,k (3-5)

k1hT1T (3-6) T2...TnTntn,k (3-7)

k1h表3-5 将m台机床划分为两机床M与M′的时间矩阵（2）

Mˊ MH+1 t1,H+1 t2,2 „ „ „ Mm t1,m t2,h … tn tn,H … tn,H+1 … …„ tn,m … 22

***大学本科生毕业设计

hT1kHt1,k (3-8)

T2t2,kkHh

(3-9)

T1TT2 (3-10)

...Tn Tntn (3-11) ,kkHh彼得罗夫—哈姆算法确定零件的加工顺序时，利用如表3-5所示的两个列向量T和T′，它定义了两条规则：

规则1：如果T′-T列向量中所有元素(Ti′-Ti)皆为非负数，则加工顺序按T列向量中的Ti数值从小到大的递增顺序排列；反之，加工顺序按T′列向量中的Ti′数值从大到小的递减顺序排列。

规则2：直接按T′-T中(Ti′-Ti)的数值从大到小的递减顺序排列。

根据以上两条规则，可得出两种排产方案，通过计算并对比两个方案的总流程时间，选择总流程时间较小者作为采用方案。

(2)确定零件组之间的排产顺序

在一个成组加工单元中，往往存在若干个零件组等待加工，确定零件组之间的排产顺序与确定一个零件组内各零件的排产顺序方法基本相同。只是还需考虑两个因素：一是从一个零件组转到另外一零件组时的组间调整时间；二是将“零件组”看成是确定组内零件排产顺序时的一种“零件”。

总之，以一组或多组零件加工完成时间最短为优化目标，应用基于成组技术的彼得罗夫—哈姆算法，实现方便，排产结果比较理想。但是，该方法只适用于零件在每道工序只有唯一一台机床或已事先选定一台机床加工的情况。而在实际生产过程中，同一道工序往往有多台加工能力相近的机床可供选择(称为

23

***大学本科生毕业设计

平行加工)，它们加工同一零件的工时可能相同，也可能不同。此时，首先要研究的是对加工能力相同或相似的机床加工作业的分配；其次是确定零件按工序在机床上的排产顺序。其目标是使零件加工完成时间最短，且均衡各机床的负荷，以实现均衡生产。

3.3基于知识的调度方法

基于知识的调度方法是用人工智能与专家系统自动产生调度或辅助调度，称为智能调度[21]。它克服数学规划与仿真方法的不足，能根据系统当前状态和给定的优化目标，对知识库进行有效的启发式搜索和并行模糊推理机制，避开了繁琐的计算，并选择最优的调度策略，为在线决策提供支持。

1)神经网络方法。神经网络已被成功地应用于解决组合优化问题，用神经网络的方法建立生产调度的模型关键在于分别用不同类型的单元网络表示不同类型的约束条件。然后通过适当连接这些单元神经网络，得到资源约束和排序约束的网络表示，进一步实现生产调度的建模。在大规模、复杂调度问题中，存在计算速度慢与结构参数难于确定的缺点，易陷入局部最小和全局搜索能力弱。王万良在2002年提出了基于神经网络的作业车间生产调度的新方法，给出了作业车间生产调度问题(JSP)的约束条件及其换位矩阵表示。提出了新的包括所有约束条件的计算能量函数表达式。得到相应的作业车间调度问题的Hopfield神经网络结构与权值解析表达式，并提出相应的Hopfield神经网络作业车间调度方法。

2)模拟退火算法。模拟退火算法由Metropolis等人提出。利用受控随机概率接受劣解，避免陷入局部最优，是一种串行全局优化算法。在运筹学的各个领域有大量的研究。其收敛性要求初温应足够高。使解空间各状态能以几乎相同的概率出现，模拟退火的弱点是搜索空间过于庞大和下降温度难于掌握。赵良辉2006年结合车间调度问题的特点阐述了模拟退火算法在解决车间调度问题上的应用，提出了基于模拟退火算法的车间调度问题模型。并以Matlab为工具进行了仿真实验。

模拟退火法适合求解大规模优化问题，当优化问题有很多局部极值又很难求出时，模拟退火法尤其有效。模拟退火法的核心思想类似于金属的退火方法，以往处理问题的方式都是从初始点开始，沿下降的方向前进，走得越远越好，

24

***大学本科生毕业设计

以期求得问题的最优解。但是，正如金属的冷却过程，所有缓慢冷却的系统都可以自然达到最低能量状态，而如果某种液体金属被迅速冷却，那么它只能达到具有较高能量的非结晶状态。传统的求解方式往往只能求得局部极小值点，而不能达到全局最优。模拟退火法每次使参数T(类似于温度)下降一个幅度，对解进行一定次数的调整，如果某次调整使目标函数E(类似于能量)下降，则接受它，反之，则以概率exp(-△E/T)接受。

3)遗传算法简称GA(Genetic Algorithm)，它是一种新的并行优化搜索方法。它是一种模仿生物群体进化过程的一种优化算法，给定一组初始解作为一个群体，通过选择、交叉和变异等遗传操作来搜索最优解。最早是由Bagley J.D在1967年提出的。李国富(1998)用遗传算法对车间调度零件排序问题进行优化搜索，并在算法中引进了一些新的思想，以有利于降低种群的规模，提高计算速度，改善优化结果。

美国Holland教授1975年提出的遗传算法(Genetic Algorithm)是一类通过模拟生物界自然选择和遗传机制的随机搜索算法。遗传算法对求解问题本身一无所知，它所需要的仅是对算法所产生的每个染色体进行评价，并根据适应性进行选择，使适应性好的染色体比适应性差的染色体有更多的繁殖机会，经过反复迭代，直到达到某种形式的收敛。

遗传算法尤其适用于处理传统搜索方法难以解决的复杂的非线性问题，可广泛用于组合优化、机器学习和规划设计等领域。已经有一些研究人员把遗传算法应用到生产调度问题中，使用遗传算法求解生产调度问题的主要工作有：生产问题到遗传编码的转换、字符串操作符的选择和搜索空间的约束描述等。

典型研究和应用有：Starkweather等人在一个啤酒厂中应用遗传算法解决了多目标调度问题，这些目标包括工厂中平均存货时间的最小化和客户订单平均等待时间的最小化等；刘民等人用遗传算法解决并行多机调度问题；张纪会等人用遗传算法进行生产动态调度知识获取，并用实例说明了其可行性；Amancio等人用遗传算法来解决流程工业中能量和生产的调度优化问题等等。

遗传算法已经成为一种比较通用的优化算法，主要原因是其编码技术和遗传操作比较简单，优化不受性条件的约束[22]。但是遗传算法也有其明显的不足之处：对于大规模的组合优化问题，搜索空间大，搜索时间较长；往往会

25

***大学本科生毕业设计

出现早熟收敛的情况；对初始种群很敏感，初始种群选择不好会影响解的质量和算法效率。为了进一步改进遗传算法，人们主要从两方面入手：一是对遗传算法本身进行改进；二是与其他算法结合，取长补短。

4)禁忌搜索算法。禁忌搜索是Glove提出的模拟智能过程的一种具有记忆功能的全局逐步优化算法，对变动的排序在其可行解的所有空间中进行搜寻。通过设置禁忌表记忆近期搜索路径。避免陷入局部最优或重复过去的搜索。并由此控制进一步的搜索方向。同时利用中、长期的存储机制进行强化和多样化搜索。

黄志在2006年描述了一种解决作业车间调度最短完工时间问题的有效的启发式算法。该算法基于禁忌搜索技术。为了得到更好的结果。还将倒转技术引入到算法中。从对一组问题基准实例的实验计算结果看，该算法在合理的计算时间内对多个实例得到比2004年提出的ISSB算法更好的结果。

3.4 车间生产调度方法的比较及其评价

1)车间调度方法的比较

对于调度问题中的各种方法来说，在一定时期、一定情况下都有各自的优点。都有解决某一类问题的优越性，但随着发展的需要，对优化方法要求也越来越高，下面对各种方法进行比较分析，通过表3-6的形式来展现各自的特点。

2)典型车间调度方法的评价

数学规划方法的优点在于求解精确[23]。目标直指最优解，在面对简单问题的时候，可以找到适合问题的最优解。但是，当问题的规模增大时。算法的计算时间随之呈指数增加会发生“组合爆炸”，给求解计算带来困难。另外，使用数学规划方法时，通常要加上一些脱离实际情况的假设。在一定程度上也导致了理论研究与实际应用的脱节。

与数学规划方法相比，启发式算法的明显优势在于：启发式算法相对比较简单，计算效率高，能显著地节省计算开支；而且启发式算法灵活多变[24]。在考虑多种方案和不能用定量表示约束集合时，常能把它作为制定计划的工具。但是，启发式算法有明显不足之处。即有可能出现所产生的解比全局最优解差很多的情况，而且差的程度总是不够明确。因此，合理的计算时间和所求出的解的最优性就成为衡量启发式算法性能的标准。

26

***大学本科生毕业设计

相对于数学规划方法和启发式方法，计算智能调度方法也逐渐被人们所使用起来。它弥补了上面两种调度方法的缺点和不足，结合了现在先进科学技术，成为了解决现在车间调度问题的主流调度方法，也逐渐被越来越多的人们所使用[25]。

表3-6 车间调度方法的比较

方法名称 法

优点 解

缺点

适用性

数学规划求解精确，能找到最优计算时间过长且占适合规模较小

用内存量随变量的的简单问题 增加成指数倍增长，会发生“组合爆炸”

彼得罗夫-实现方便，排产结果理算法计算相对复杂 适合调度问题哈姆算法 法 规则 的方法 方法

度快 调整 较容易

难于获取和表达 参数难以确定

想

确

中的排产问题

解的最优度不够精样本小的调度

问题

模超大的问题 柔性强的车间 束较复杂但规模不大的问题

模拟退火串行全局优化算法，避搜索空间过于庞大适用于问题的算法 遗传算法 算法

免陷入局部最优 算法简单 逐步优化算法

和下降温度难于掌改进 握 收敛速度慢 全局最优

适合复杂问题 的问题

禁忌搜索具有记忆功能的全局搜索结果无法保证适合规模庞大综上所述，车间作业调度问题中的各种算法各有利弊，在不同情况下可以有针对性的选择。

Palmer算求解快速，方便实用

优先调度操作简单易行，求解速解的质量难以保证 适合复杂，规基于知识人机互动，能够及时的研制花费昂贵，知识适合制造系统神经网络对于资源约束的表达计算速度慢与结构适用于资源约

27

***大学本科生毕业设计

第4章 案例分析

4.1企业背景概述

沈阳亚中机械设备有限公司是一家集设计、制造、调试为一体的高新技术企业，主要从事各类液压系统及液压缸的设计制造、安装指导及售后调试等。公司已通过了ISO9000质量管理体系认证。公司拥有一批高水平、高素质的工程技术及管理人员。丰富的设计经验、可靠的产品性能、先进的管理理念及完善的售后队伍是公司屹立于行业前列的根本保证，是用户信得过的供应商。公司产品主要包括为堆取料机、磨机、辊压机、篦冷机、破碎机、推焦机、拦焦机、剪切机、卸船机等设备配套的液压系统、液压缸。产品已广泛应用于建材、电力、化工、重工、钢铁等行业，产品遍及全国10多个省，并已出口至越南、菲律宾、土耳其等国家。

4.2车间生产调度的管理结构

1)主要职能部门间的相互关系

与生产直接相关的部门主要有生产计划科、供应科、质管办、办公室与生产车间。它们之间的关系如图4-1。

生产计划 外购 加工工艺

办公室 生产车间 检验 图4-1车间调度与管理部门间的管理结构

物料 质管办 生产计划科 供应科 28

***大学本科生毕业设计

2)车间生产调度系统层次结构

车间生产调度系统主要由生产作业计划、静态调度、动态调度三个层次构成，前者是后者的基础，其层次结构关系如图4-2。

零件交货期 资源负荷平衡

订货单 零件工时定额 单元生产能力 图4-2 车间生产调度系统层次结构图

成组技术 零件工艺 调整状态 生产环境 动态调度 调整指令 静态调度 提高设备利用率 生产作业计划 设备调整时间最小 4.3机械加工车间的现状分析

沈阳亚中机械设备有限公司的机械加工车间分为三个生产车间。一车间存放大量的铣床车床等，主要是对零件胚胎

进行钻镗孔和铣外形。二车间存放

车床，镗床，钻床，刨床，插床，磨床，并有四分之一的装配场地，主要是对零件进行刨平面，磨平面，钻孔，插键槽孔等。三车间为气焊车间，主要是对零件气焊外形。

29

***大学本科生毕业设计

北门铣床X62W铣床X62W铣床X62W铣床X62W通道铣床X62W平面磨床M7310铣床X62W摇臂钻床Z3080摇臂钻床Z3080摇臂钻床Z3080摇臂钻床Z3080摇臂钻床Z3080铣床X52K铣床X52K铣床X52K铣床X52K西门通道通道东门铣床X52K铣床X52K铣床X52K铣床X52K通道车床C630车床C630插齿机Y54插齿机Y54立式研磨机M4250镗床T68立式研磨机M4250镗床T68龙门铣X2010C铣床X54铣床X54铣床X54南门

图4-3 一车间分布图

30

***大学本科生毕业设计

北门车床C6140车床C6140车床C6140车床C6140通道车床C6140车床C6140车床C6140车床C6140车床C6140车床C6140龙门刨床B20120插床B5020牛头刨床B665牛头刨床B665摇臂钻床Z3080摇臂钻床Z3080西门通道通道东门车床C630摇臂钻床Z3042车床C630摇臂钻床Z3042通道划线区立钻Z5135镗床T10A立钻Z5135镗床T10A南门装配区图4-4 二车间分布图

但从两个车间的设备总体分布来看，由于设备的购买时间的不同和一些客观因素(如资金、生产状况)的制约，机加分厂的车间设备既没有按生产工艺分布，也没有按加工对象分布，因此存在一些不合理的地方，造成生产物料流程的混乱和生产不均衡。如四柱液压机的上、中、下梁板加工，由于只是按照客户订单的先后和组装需求来决定梁板的生产顺序，生产周期不仅不固定，而且

31

***大学本科生毕业设计

周期很长，平均在4~5天，因此有必要做出改善。

4.4生产调度排序改善的案例

介绍了关于公司生产车间的情况，而本节则主要对车间零件梁板的生产顺序问题进行讨论和研究，探寻对其生产顺序的改善方案，并对palmer算法和彼得罗夫-哈姆算法进行比较和选优。 4.4.1梁板

1)梁板的介绍

三梁四柱液压机（图4-5）的机身由上横梁、滑块、工作台用四根立柱相连，通过螺母紧固，组成一封闭式刚性框架，滑块与主缸活塞杆连接，以立柱为导向，作上下移动。中梁板（滑块下表面）和下梁板（工作台上表面）开有T 型槽，供安装模具用。

图4-5 三梁四柱液压机

32

***大学本科生毕业设计

公司车间生产的梁板有两种型号，分别为120t,200t。每种型号又分为上、中、下三种梁板。它们的结构相似，均有五个孔，只是不同梁板中的孔的尺寸不同；另外主要区别在于中梁板和下梁板分别有T型槽，上梁板则没有；上梁板和中梁板的孔需要攻螺丝/螺纹，而下梁板的孔则不需要，图4-6为上梁板的零件图：

46036070Φ170Φ5104603604-Φ72

图4-6 上梁板零件图

33

***大学本科生毕业设计

2)梁板的加工路线

上、中、下梁板的工艺路线如图4-7所示

上梁板 中梁板

粗车（留余量3mm） 下梁板

粗车（留余量

粗车（留余量3mm） 3mm） 铣周边及倒角 铣周边及倒角 铣周边及倒角 划线 划线 划线 钻粗孔 钻粗孔 钻粗孔 铣T型槽 铣T型槽 精刨（表面粗糙度6.3ūm） 精刨（表面粗糙度6.3ūm） 精刨（表面粗糙度6.3ūm） 镗孔 镗孔 镗孔

钻（攻螺纹） 钻（配做螺孔） 图4-7梁板工艺流程图

根据图4-7所示，四柱液压机的上、中、下梁板加工工艺区别在于，中梁板和下梁板需要铣T型槽，上梁板则不用；上梁板和中梁板需要攻螺纹、螺丝，二下梁板则不用。故将它们的加工工艺加以总结，得到梁板加工族的加工工艺，如图4-8所示。

34

***大学本科生毕业设计

粗车（留余 ） 量3mm 铣周边及倒角 划线 钻粗孔 铣T型槽 精刨（两面，表面粗糙度6.3ūm） 镗孔

攻螺纹/螺孔 图4-8梁板族加工族工艺流程图

工艺是将多种零件按其工艺的相似性分类以形成零件族，把同一零件族中的零件分散的小批量汇集成较大的成组生产量，从而使小批量能获得接近于大批生产的经济效果。

由此可以直观地看到，三梁四柱液压机的上、中、下梁板的工艺流程是非常相似的，可以成组地将这些零件作为一个零件加工族来安排生产，以简化物料与信息流程，提高生产效率。

3)梁板的加工工时

梁板的加工共需7~8道工序，对120t和200t的 上、中、下梁板三种规格型号的梁板零件进行加工，有关数据如表4-1所示：

35

***大学本科生毕业设计

表4-1单选机床加工工时数据表 工时:小时

工种 工时 车 铣 周边及侧角 5.0 8.0 9.0 6.0 7.0 10.0 划 钻 粗钻 孔 1.0 1.0 1.0 2.0 1.0 4.0 1.0 2.0 1.0 3.0 1.0 4.5 铣 床 —— 6.0 4.0 —— 7.0 5.0 5.0 6.5 8.0 7.0 7.0 9.0 刨 镗 镗孔 孔 4.5 3.5 4.5 5.0 4.0 5.0 钻 攻螺纹/螺孔 1.5 2.5 —— 2.0 3.0 —— 粗车 双面铣 线 T槽铣精刨 T型槽 两面 工件 120t上梁板 3.5 120t中梁板 4.0 120t下梁板 4.5 200t上梁板 4.0 200t中梁板 4.5 200t下梁板 5.0

4.4.2 基于palmer算法零件排序问题求解

应用palmer算法对梁板的加工工序进行计算,计算过程如下： 工件的斜度指标为:

8i[k(81)/2]tik k1,2......8 （4-1）

k113.5t112.5t121.5t130.5t140.5t151.5t162.5t173.5t186.7523.5t112.5t121.5t130.5t140.5t151.5t162.5t173.5t183.7533.5t112.5t121.5t130.5t140.5t151.5t162.5t173.5t181343.5t112.5t121.5t130.5t140.5t151.5t162.5t173.5t1811 53.5t112.5t121.5t130.5t140.5t151.5t162.5t173.5t181.7563.5t112.5t121.5t130.5t140.5t151.5t162.5t173.5t187.75按μi不增的顺序排列工件，得到加工顺序:200t上梁板，200t中梁板，120t中梁板，120t上梁板，200t下梁板，120t下梁板。按此顺序生产时，总流程时间为Tmin=69h

36

***大学本科生毕业设计

表4-2 总流程时间Tmin计算过程表 单位:小时

200t上梁板 200t中梁板 120t中梁板 120t上梁板 200t下梁板 120t下梁板

4.4.3 基于彼得罗夫-哈姆算法零件排序问题求解

运用彼得罗夫—哈姆算法求解,首先，将8台机床划为M与M′两种，如表4-3所示：

表4-3 将8台机床划分为两机床的时间矩阵（1） 单位：小时

120t上梁板 120t中梁板 120t下梁板 200t上梁板 200t中梁板 200t下梁板

车 3.5 4.0 4.5 4.0 4.5 5.0

铣 7 7 7 6.0 7.0 10.0

划 1 1 1 1.0 1.0 1.0

钻 1 2 2 2.0 3.0 4.5

车 0 4 4 8.5 8.5 12.5 12.5 16 16 21 21 25.5

铣 4 6 8.5 15.5 15.5 23.5 23.5 28.5 28.5 38.5 38.5 50.5

划 6 7 15.5 16.5 23.5 24.5 28.5 29.5 38.5 39.5 50.5 51.5

钻 7 9 16.5 19.5 24.5 26.5 29.5 30.5 39.5 44 51.5 55.5

44 45 55.5 59.5 19.5 26.5 26.5 32.5 —— 铣 ——

刨 9 16 26.5 33.5 33.5 40 40 45 45 54 59.5 67.5

镗 16 21 33.5 37.5 40 43.5 45 49.5 54 59 67.5 73

—— 钻 21 23 37.5 40.5 43.5 46 49.5 51 ——

开 结 开 结 开 结 开 结 开 结 开 结 开 结 开 结 37

***大学本科生毕业设计

T1=12.5 T2=14 T3=14.5 T4=13 T5=15.5 T6=20.5

12.51414.5T13 15.520.5 表4-3 将8台机床划分为两机床的时间矩阵（2） 单位：小时

120t上梁板 120t中梁板 120t下梁板 200t上梁板 200t中梁板 200t下梁板

T1′=12 T2′=18.5 T3′=15.5 T4′ =14 T5′=21 T6′ =19

铣 —— 6.0 4.0 —— 7.0 5.0

刨 6.0 6.5 7.0 7.0 7.0 9.0

镗 4.5 3.5 4.5 5.0 4.0 5.0

钻 1.5 2.5 —— 2.0 3.0 ——

1218.515.5T'

142119 38

***大学本科生毕业设计

12.5120.51418.54.514.515.51TT'

1314115.5215.520.5191.5

按规则1:因为T′-T列向量中所有元素出现负数，所以加工顺序按T列向量中的T′数值从大到小排列，即加工顺序为200t中梁板、200t下梁板、120t中梁板、120t下梁板、200t上梁板、120t上梁板

按规则2:直接按(Ti′-Ti)数值由大到小排列，即加工顺序为200t下梁板、120t上梁板、120t下梁板、200t上梁板、120t中梁板、200t中梁板。

1) 200t中梁板、200t下梁板、120t中梁板、120t下梁板、200t上梁板、120t上梁板排序时，总流程时间为Tmin=73.5h

表4-4 总流程时间Tmin计算过程表 单位：小时

200t中梁板 200t下梁板 120t中梁板 120t下梁板 200t上梁板 120t上梁板

车 0 4.5 4.5 9.5 9.5 13.5 13.5 18 18 22 22 25.5

铣 4.5 11.5 11.5 21.5 21.5 29.5 29.5 38.5 38.5 44.5 44.5 49.5

划 11.5 12.5 21.5 22.5 29.5 30.5 38.5 39.5 44.5 45.5 49.5 50.5

钻 12.5 15.5 22.5 27 30.5 32.5 39.5 43.5 45.5 47.5 50.5 51.5

—— 铣 15.5 22.5 27 32 32.5 38.5 43.5 47.5 ——

刨 22.5 29.5 32 41 41 47.5 47.5 55.5 55.5 62.5 62.5 67.5

镗 29.5 33.5 41 46 47.5 51 55.5 60 62.5 67.5 67.5 72

67.5 69.5 72 73.5 51 53.5 —— 钻 33.5 36.5 ——

开 结 开 结 开 结 开 结 开 结 开 结 开 结 开 结 39

***大学本科生毕业设计

2) 按200t下梁板、120t上梁板、120t下梁板、200t上梁板、120t中梁板、200t中梁板排序时，总流程时间Tmin=72h。

表4-5 总流程时间Tmin计算过程表 单位：小时

200t下梁板 120t上梁板 120t下梁板 200t上梁板 120t中梁板 200t中梁板

车 0 5 5 8.5 8.5 13 13 17 17 21 21 25.5

铣 5 15 15 20 20 29 29 35 35 43 43 50

划 15 16 20 21 29 30 35 36 43 44 50 51

钻 16 20.5 21 22 30 34 36 38 44 46 51 54

所以应选取1200t下梁板、120t上梁板、120t下梁板、200t上梁板、120t中梁板、200t中梁板加工顺序

46 52 54 61 34 38 —— 铣 20.5 25.5 ——

刨 25.5 34.5 34.5 39.5 39.5 47.5 47.5 54.5 54.5 61 61 68

镗 34.5 39.5 39.5 44 47.5 52 54.5 59.5 61 .5 68 72

59.5 61.5 .5 67 —— 44 45.5 —— 钻 ——

开 结 开 结 开 结 开 结 开 结 开 结 开 结 开 结 4.5 总结

1)改善效果

通过对四柱液压机的梁板生产顺序的分析，利用palmer算法和彼得罗夫-哈姆算法，得到最后的梁板排产顺序的排产方案，即生产周期由原来的100h,改进为现在的72h,效率提高了28%，效果明显。

2)方案的对比

通过上述对梁板的加工顺序的确定，让我们了解到了palmer算法和彼得罗夫-哈姆算法在求解车间生产调度中的排序问题的优缺点。Palmer算法求解简

40

***大学本科生毕业设计

单，方便实用，计算速度快，适合对解的精确度要求不高的车间调度问题求解。彼得罗夫-哈姆算法实现方便，排产结果比较理想。但是，该方法只适用于零件在每道工序只有唯一一台机床或已事先选定一台机床加工的情况。而在实际生产过程中，同一道工序往往有多台加工能力相近的机床可供选择(称为平行加工)，它们加工同一零件的工时可能相同，也可能不同。此时，首先要研究的是对加工能力相同或相似的机床加工作业的分配；其次是确定零件按工序在机床上的排产顺序。其目标是使零件加工完成时间最短，且均衡各机床的负荷，以实现均衡生产。

3)方案的选优

上述Palmer法和彼得罗夫—哈姆算法均属于启发式算法，各种算法所得到的结果有时不一定是最优，而只是近优，但在大多数情况下是最优的或接近于最优。Palmer算法的优点是求解相对简单，但通常仅得到唯一的排序方案，排序结果的准确性较差。而彼得罗夫—哈姆算法兼具palmer算法的优点，只须计算有限个方案的总流程时间，便可迅速找出入选方案，可以说彼得罗夫-哈姆算法是palmer算法的升级，因此具有很大的应用价值和研究价值。由palmer所求出的总流程时间为73h，由彼得罗夫-哈姆算法所求的总流程时间为72h。依照总流程时间最短原则，本文认为彼得罗夫-哈姆算法更适合运用在沈阳亚中机械设备有限公司的车间调度问题上。

本文研究了以彼得罗夫—哈姆算法为优化算法的车间调度问题的新型方案，使生产调度问题顺利解决，简化了生产计划的冗余管理，实现了车间对各项任务的作业顺序合理安排。在完成计划任务的前提下，减少了零件的加工时间，并提高了生产效率。

41

***大学本科生毕业设计

第5章 结论

车间生产调度是企业生产的重要环节，它对企业生产管理与控制系统有着重要的影响。本论文在仔细研究车间生产调度与管理的理论和方法的基础上，结合具体的中小型制造企业(沈阳亚中机械设备有限公司)的车间现状，探讨如何应用先进实用的生产调度方法解决企业长期存在的实际问题。

本文通过研究车间生产调度分类和特点，在车间生产调度的研究策略的基础上，分析了车间生产调度的具体实际问题。归纳了车间生产调度的几种重要的研究方法，包括数学规划方法、启发式方法和计算智能调度方法，重点研究了启发式方法中的palmer算法和彼得罗夫-哈姆算法。通过对车间调度各种方法的比较与评价，说明车间调度方法的利弊。

通过分析沈阳亚中机械设备有限公司的加工车间存在的一些基本问题，包括车间设备布置情况，机加工性能和车间调度与管理的关系，运用palmer算法和彼得罗夫-哈姆算法解决该车间梁板的加工顺序，使加工效率提高了28%,进而对palmer算法和彼得罗夫-哈姆算法的比较评价，说明生产调度方法必须依具体车间的生产情况确定。

研究如何应用合理的调度方法，来解决车间调度问题，是每个企业所必须分析和研究的课题。而本论文研究的只是典型零件的生产作业排序问题，对于所有机械加工零件的作业排序问题，往往考虑的因素会更多。随着社会的发展和科技的进步，人们的研究将会更加深入，越来越多的适合企业的调度方法被人们使用，这些调度方法对提高企业的生产效率、降低生产成本和保证交货期等起到真正的作用。

42

***大学本科生毕业设计

参考文献

[1] Farhoodi F A.Knowledge-based approach to dynamic job-shop scheduling [M].

International Journal of Computer Integrated Manufacturing1990, 3(2): 84-95.

[2] 王万良，昊启迪，徐新黎．基于Hopfield神经网络的作业车间生产调度方法[J]．自

动化学报, 2002, 28(5)：838-844．

[3] 赵良辉,邓飞其.用于作业车间调度的模拟退火算法[J].制造业自动化,2006,

28(3):10-23.

[4] H.A.J.Crauwels, C.N.Potts, L.N.Van Wassenhove. Local search heuristics for

single-machine scheduling with batching to minimize the number of late jobs[M]. European Journal of Operational Research, 1996(90): 200-213.

[5] 黄志,黄文奇.一种基于禁忌搜索的作业车间调度算法[M].计算机工程与应用,

2006(3):12-14.

[6] D.Ouelhadj, S.Petmvic,P.I.Cowling and A.Meisels.Inter-agent cooperation and

communication for agent-based robust dy-namic scheduling in steel production[J]. Advanced Engineering Informatics, 2004(18):161-172.

[7] 威廉J.史蒂文森著.张群,张杰等译.生产与运营管理[M].北京:机械工业出版社,

2000.

[8] Miller R E,Thatcher J W. Complexity of Computer Computations[M]. New York: Plenum

Press, 1972.

[9] Nilsson N.J. Problem—solving Methods in Artificial Intelligence[M]. New York: Mc

Graw—Hill. 1971.

[10][法]Lucas Pun.集成化离散生产控制[M].熊光塄等译.北京:清化大学出版社, 1997. [11] 邓子琼,李小宁等. 柔性制造系统建模及仿真[M]. 北京: 国防工业出版社, 1993. [12] 姜思杰.基于GA和TS的最小平衡算法及其在FMS中的应用:[D].哈尔滨:哈尔滨工

业大学,1998.

[13] 严洪森.柔性制造系统建模,调度,控制和仿真的研究及应用:[D].哈尔滨:哈尔滨工

业大学,1992.

[14] 吴启迪等.柔性翩造自动化的原理与实践[J].北京:清华大学出版社,1997.

43

***大学本科生毕业设计

[15] 刘飞等.动态联盟公司异地生产计划调度与控制系统研究[M].机械工业自动化,

1998,(6):l-5.

[16] 顾幸生.不确定性奈件下的生产调度[J].华东理工大学学报,2000,26(5): 441-446. [17] 连志刚.粒子群优化算法及其在生产调度中的应用[D].华东理工大学博士学位论

文,2007.

[18] 李培根,张洁.敏捷化智能制造系统的重构与控制[M].北京:机械工业出版社, 2003. [19] 王万良,吴启迪,宋毅.求解作业车间调度问题的改进自适应遗传算法[J].系统工程

理论与实践,2004(2):58-62.

[20] 王磊,黄文奇.求解工件车间调度问题的一种新的邻域搜索算法[J].计算机学报,

2005,28(5):809-816.

[21] 刘飞等.动态联盟公司异地生产计划调度与控制系统研究[J].机械工业自动化,

1998,(6):l-5.

[22] 姜思杰,马玉林一种新的FMS优化调度算法[M].控制与决策.1999,14(1):1-4. [23] 顾擎明,宋文中.基于成组技术的一种柔性调度方法[M].控制与决策.1999,14(1):

1-4.

[24] 阳林,昊黎明,郑汉卿.FMS生产作业调度控制系统[M].机械制造.1998(3):11-14. [25] 李上进,周云飞,周艳红.车间作业计划的全局动态调度算法[J].华中理工大学报.

1998,20(8):20-22.

[26] 陈荣秋.排序的理论与方法[M].武汉:华中理工大学出版社,1988.

44