我国汽车高等职业教育需求与对策研究
VIP免费
第一章 绪论
第一章 绪论
1.1 课题背景
制造业是国民经济最重要的支柱产业。在工业化国家，约有四分之一的人口
从事制造业，约 70%～80%的物质财富来自制造业。制造业是我国国民经济的核心
和工业化的原动力，我国制造业工业总产值约占全国 GDP 的42.5%。伴随中国加
入WTO 和经济全球化，中国正在成为世界制造业的中心。中国的制造业企业面临
更加激烈的国际国内市场竞争
生产调度就是组织执行生产进度计划的工作。生产调度以生产进度计划为依
据，生产进度计划要通过生产调度来实现。生产调度的必要性是由工业企业生产
活动的性质决定的。现代工业企业，生产环节多，协作关系复杂，生产连续性强，
情况变化快，某一局部发生故障，或某一措施没有按期实现，往往会波及整个生
产系统的运行。因此，加强生产调度工作，对于及时了解、掌握生产进度，研究分
析影响生产的各种因素，根据不同情况采取相应对策，使差距缩小或恢复正常是
非常重要的。
生产控制系统中，及时准确的调度对于生产系统的高效运行有着重要影响，
这就对调度优化方法提出了更高的要求。车间生产调度是生产过程的重要环节。生
产调度的目的是使工件加工路径的组合优化，确定工件的加工路径和每一工序的
加工开始时间，以确保所选定的生产目标最优，如总加工时间最短等。有效的调
度方法和优化技术的研究和应用，改善生产调度方案，可以大大提高生产效益和
资源利用率，进而增强企业的竞争能力。由于生产加工多品种、小批量的趋势，调
度问题日益复杂。有的调度问题不仅要确定加工排序，还要在生产工艺约束条件
下确定最优加工批量，属多目标组合优化问题。随着调度规模的扩大，许多调度
问题均属 NP-hard 问题，至今没有可以精确求得最优解的多项式时间算法。探索实
用和有效的算法，仍是国际上关注的热点研究课题。
Flow-shop 生产调度问题，除少数小规模问题存在多项式时间求解算法外，
大部分属于 NP-hard 问题。这类问题描述相对容易，但是求解非常困难。调度优化
算法可区分为精确求解方法和近似求解方法。近似求解方法如构造法、启发式方
法、随机搜索方法等，由于可以快速找到满意解，在生产调度领域受到广泛的重
视和研究，而且各种混合式搜索方法在许多组合优化领域均得到广泛的应用。
1
Flow-shop 生产调度问题的演化博弈算法研究
精确求解方法一般有解析方法、穷举法、分支定界法等。此类方法对小规模调
度问题比较有效，但对大规模问题计算量和存储量难以满足。
构造性方法如 CDS 法、NEH 法等，是近似求解方法。此类方法可以快速建立
问题的解，但通常解的质量较差，而且对初始解的要求较高。现在一般都采用启
发式方法构造其初始解，以提高其搜索性能。
邻域搜索方法主要有进化计算（EC）、模拟退火算法（SA）、禁忌搜索
（TS）等。此类方法从若干解出发，对其邻域的不断搜索和当前解的体换来实现
优化。其中遗传算法（GA）的局部搜索能力较弱，SA 的退火时间较长，TS 的禁
忌表的构造相对困难，所以实际应用中经常把这些启发式方法结合起来使用。
人工智能方法如蚁群系统（AS）、神经网络（NN）、混沌搜索（CS）、免疫
算法（IA）等，也是常用到的一类启发式方法。此类方法利用人工智能的原理和
技术进行搜索，将优化过程转化为智能系统动态的演化过程，利用系统的动态演
化来实现优化。
随着人们认识的深入以及科学技术的发展，一些新兴的算法也越来越受到重
视，如 DNA 计算、量子计算等。这些算法随着科技的发展，其强大的搜索能力将
使很多现在非常困难的问题迎刃而解。
1.2 作业排序问题
1.2.1 作业排序问题的描述
周期性生产类型的生产组织形式是工艺专业化，车间往往就是生产过程中的某
个工艺阶段，每个零件在车间内要经过某几个工序的加工。因此车间的作业计划中
工件加工的排序问题是一个难点。其难处在于零件种类多，加工的工艺流程和加工
工时差别较大。一般采取重点管住关键零件和关键设备的方法。
排序问题一般可作如下描述：n种零件在有m台设备的车间内加工，每种零件加
工所需要的设备数可以是不同的，加工的顺序也可以不同，要求排出效果尽可能好
的工件加工次序。目前对这个问题的研究所取得的成果只能解决少数几种特殊条件
下的排序问题，其思路是先确定一个优化目标，再寻求解题模型。通常取一批加工
任务在车间内停留的时间最短为优化目标。
1.2.2 作业排序问题的分类
排序问题有不同的分类方法。就生产方式而言，调度问题可分为开环车间
（open shop）型和闭环车间（closed shop）型。开环调度问题，也称加工排序问题
它本质上只研究工件的加工顺序，即订单所要求的产品在所有机器上的加工顺序，
其中订单均来源于顾客，不考虑库存的设立。闭环调度问题除研究工件的加工顺序
2
第一章 绪论
外，还涉及各产品批量大小的设置，即在满足生产工艺约束条件下寻找一个调度策
略，使得所确定的生产批量和相应的加工顺序下的生产性能指标最优，其中顾客需
求的产品均由库存提供，生产任务一般只由产品存储策略来决定。
在生产作业排序中，还可进一步按机器、工件和目标函数的特征分类。按照机
器的种类和数量不同，可以分为单台机器的排序问题和多台机器的排序问题。对于
多台机器的排序问题，按工件加工的路线特征，可以分成单件车间（job-shop）排
序问题和流水车间（flow-shop）排序问题。工件的加工路线不同，是单件车间排
序问题的基本特征；而所有工件的加工路线完全相同，则是流水车间排序问题的基
本特征。
按工件到达车间的情况不同，可以分成静态排序问题和动态排序问题。当进行
排序时，所有工件都已到达，可以一次对他们进行排序，这是静态排序问题；若工
件是陆续到达，要随时安排它们的加工顺序，这是动态排序问题。
按目标函数的性质不同，也可划分不同的排序问题。例如，同是单台设备的排
序，目标是使平均流程时间最短和目标是使误期完工的工件数最少，实质上是两种
不同的排序问题。按目标函数的情况，还可以划分为单目标排序问题和多目标排序
问题。
由此可见，由机器、工件和目标函数的不同特征以及其它因素上的差别，构成
了多种多样的排序问题及相应的排序方法。
1.2.3 作业工件加工数据和特性
调度问题中，通常一个工件Ji包含ni个操作（operation）{Oi，1，…，Oi，ni}，每
个操作Oij的加工时间或需求为pij。若ni=1，则工件Ji仅包含一个操作Oi1，简记其加
工时间为pi。称工件Jj的第一个操作可执行的时刻为释放时间或准备时间（release
date），记为ri。记加工操作Oij的机器集为 ，Oij可以在 中任何
一台机器上加工。通常， 仅对应一台机器或者对应所有机器。前者称为专用机
器（dedicated machine），后者称为并行机（ parallel machine）。许多实际生产系
统中，各机器可装备相同或不同的工具，操作可以在任何一台装备合适工具的机器
上加工，这就是生产系统所谓的柔性，该调度通常称为多目的机器（multi-
purpose machines，MPM）调度。若Oij的加工过程同时占有 中所有机器，则称该
调度问题为多处理机任务调度（multi-processor task scheduling）。对于每一件
ji，记t时刻完成ji的加工费用函数为fi（t），记计划完成时间或交货期（due
date）为di，与之相关的权重（weight）为 。
若同一机器上既没有任意两个时间区间重叠，也没有分配给同一个工件的任意
两个时间区间重叠，并且满足调度问题的一些特殊工艺约束，则称一个调度为可行
（feasible）调度。进而，称使得调度准则或指标最优的可行调度为最优调度
（optimal）。
3
Flow-shop 生产调度问题的演化博弈算法研究
通常，工件加工特性可用六元组{ }来表示，其中
1用来表示加工方式，包括抢占式（preemption）或非抢占式（non-
preemption）。其中，抢占式加工中操作在加工过程中可以被打断，再在原机器或
别的机器上重新开始；非抢占式加工则一旦操作开始，直到加工完毕，不能被其他
加工打断。通常，记抢占式加工为 1=pmtn，而非抢占式加工则不再中出现
1。
2用来表示工件间的加工优先关系（precedence relation）。该优先关系可
以用非循环有向图G=（V，A）来表示，其中V={1，…，n}表示工件，（i，k）
A，当且仅当Ji必须在Jk开始加工之前完成。若G为任意非循环有向图，则记
2= p r e c。若G对 应 树（ t r e e），则 记 2= t r e e。若G对 应 链 （ c h a i n）,则 记
2=chain。若G对应的图具有系列-并行（series-parallel）特性，则记 2=sp-graph。
若调度问题不考虑工件加工的优先权，则中不出现 2。
3用来表示工件的准备加工时间。若ri，则记 3=ri；若所有ri=0，则
中不出现 3。
4表示加工时间或操作数量的限制。若4记作pi=1（或pij=1）,则每个工件
（或操作）有1次操作需求（如加工时间为1）。有时， 4也可为一些具有明显意
义的别的值，如pi{1,2},di=d。
5用来表示交货信息。5=di表示工件有交货期要求，否则 中不出现
5。
6用来表示批量信息，即工件是否成批联合进行加工。批量调度中，同批
的各工件的完成时间等于该批量的完成时间，假定各批量的加工设置时间相同且与
加工顺序无关。 6=p-batch或6=s-batch分别表示批量长度等于该批量中所有工件
的加工时间的最大值或加工时间之和。若不考虑批量调度，则中不出现 6。
4
第一章 绪论
1.2.4 作业加工环境
作业加工环境通常可用一个二参数串 =1 2来表示，其中1{o，P，Q，
R，PMPM，QMPM，G，X，O，J，F}，符号o表示空。若1=o，则=2。若
1{o，P，Q，R，PMPM，QMPM}，则每个工件仅包含一个操作。
若1=o，则每个工件必须在一个规定机器上加工。
若1{P，Q，R}，则表示并行机加工环境，每个工件可以在{M1，…，
Mm}中任一台机器上加工。其中 ， 1= P表 示 相 同 并行机 （ i d e n t i c a l p a r a ll e l
m a c h i n e s），即对任 意 机 器 Mj满 足 pi j
= p
i；1= Q表 示 均匀 并 行机 （ u n i f o r m
parallel machines）,即pij=pi/sj，sj为机器Mj的加工速度；1=R表示不相干的并行机
（unrelated parallel machines），即pij=pi/sij，sij为与工件相关的机器Mj的加工速度
若1=PMPM或QMPM，则表示加工环境对应具有相同或均匀速度的多目的机
器。
若1={G，X，O，J，F}，则表示多操作模型，即每个工件包含多个操作。同
时，所有机器是专用的，即ij只有一个元素，且各操作间存在优先顺序。该调度
称为一般（General shop）调度，记1=G。
另外，2表示机器数。若机器数给定且已知，则记 2为相应的数值；若机器
数给定但任意，则记 2=k；若机器数任意，则记 2=o。
1.3 Flow-shop车间调度问题
1.3.1 Flow-shop车间调度问题的描述
Flow-shop车间调度问题是具有特殊工件特性和加工环境的最典型和最重要的
调度问题，通常是特殊的开环调度问题。
Flow-shop车间调度问题研究技术约束条件相同的n个工件在m台机器上的加工
过程，Oij表示第i个工件在第j台机器上的操作，相应的操作时间pij为已知，事先给
定各工件在各机器上的加工次序（称为技术约束条件），要求确定与技术约束条件
相容的各机器上所有工件的加工次序，使加工性能指标达到最优。
在典型的Flow-shop车间调度问题中，除技术约束外，通常还假定以下条件：
1) 各工件经过其准备时间后即可开始加工；
2) 每一时刻每台机器只能加工一个工件，且每个工件只能被一台机器所加工
同时加工过程为不间断，整个加工过程中机器均有效；
3) 整个加工过程中，每个工件不能在同一台机器上加工多次；
4) 各工件必须按工艺路线以指定的次序在机器上加工；
5) 不考虑工件加工的优先权；
6) 操作允许等待，即前一个操作未完成，则后面的操作需要等待；
7) 所有机器处理的加工类型均不同；
8) 除非特殊说明，工件的加工时间事先给定，且在整个加工过程中保持不变
9) 除非特殊说明，工件加工时间内包含加工设置时间；
5
摘要：
展开>>
收起<<
第一章绪论第一章绪论1.1课题背景制造业是国民经济最重要的支柱产业。在工业化国家，约有四分之一的人口从事制造业，约70%～80%的物质财富来自制造业。制造业是我国国民经济的核心和工业化的原动力，我国制造业工业总产值约占全国GDP的42.5%。伴随中国加入WTO和经济全球化，中国正在成为世界制造业的中心。中国的制造业企业面临更加激烈的国际国内市场竞争生产调度就是组织执行生产进度计划的工作。生产调度以生产进度计划为依据，生产进度计划要通过生产调度来实现。生产调度的必要性是由工业企业生产活动的性质决定的。现代工业企业，生产环节多，协作关系复杂，生产连续性强，情况变化快，某一局部发生故障，或某一措施没...
相关推荐
-
跨境电商商业计划书模版VIP免费
2025-01-09 26 -
跨境电商方案范文VIP免费
2025-01-09 14 -
创业计划书VIP免费
2025-01-09 18 -
xx生鲜APP计划书VIP免费
2025-01-09 12 -
跨境电商创业园商业计划书(盈利模式)VIP免费
2025-01-09 8 -
跨境电商计划书VIP免费
2025-01-09 13 -
绿色食品电商平台项目计划书VIP免费
2025-01-09 22 -
农产品电子商务商业计划书VIP免费
2025-01-09 8 -
农村电商平台商业计划书VIP免费
2025-01-09 13 -
生鲜商城平台商业计划书VIP免费
2025-01-09 21
作者：陈辉
分类：高等教育资料
价格：15积分
属性：47 页
大小：1.01MB
格式：DOC
时间：2024-11-19
