机械机床毕业设计41带有交货期和加工时间可控的单机排序问题.doc
机械机床毕业设计41带有交货期和加工时间可控的单机排序问题
收藏
资源目录
压缩包内文档预览：(预览前20页/共45页)
编号：540417
类型：共享资源
大小：575.99KB
格式：ZIP
上传时间：2015-11-29
上传人：QQ28****1120
认证信息
个人认证
孙**（实名认证）
辽宁
IP属地：辽宁
6
积分
- 关 键 词：
-
机械毕业设计论文
- 资源描述：
-
机械机床毕业设计41带有交货期和加工时间可控的单机排序问题,机械毕业设计论文
- 内容简介：
-
本科毕业设计论文 题 目 带有交货期和加工时间可控的单机排序问题 专业名称 机械设计制造及其自动化 学生姓名 指导教师 毕业时间 nts 2 摘要 排序问题是一类重要的组合最优化问题。排序问题普遍应用于管理等学科领域，是组合最优化的一类重要问题 。调度的任务是根据生产目标和约束，为每个加工对象确定具体的加工路线、时间、机器和操作等。优良的调度策略对于提高生产系统的最优性、提高经济效益都有着极大的作用。但是由于资源约束和工艺约束的并存，迄今计算复杂性理论表明，多数调度问题属于 NP 一hard(Nondeterministiepolynomial 一 Hard，非确定性多项式 )难问题，目标解的搜索涉及解空间的组合爆炸。排序算法的竞争比分析是排序问题对算法风险的一种评估和保障，具有重要的理论意义和实用价值。 本文讨论了带有交货期和工件的加工时间可控的单 机排序问题本文首先根据最优排序的性质确定了最优资源的分配方法并将问题转化为指派问题通过构造多项式时间算法确定最优排序 #然后本文将学习效应与加工时间可控问题结合分别讨论了加工时间是线性资源函数和凸资源函数两种情况证明了该类问题是多项式时间可解的最后讨论了一种特殊情况学习因子是常数加工时间是凸资源函数给出了复杂性为 O(nlogn)的算法通过运行此算法确定最优资源分配量和工件的最优排序。 关键词：排序单台机器 ,交货期 ,指派加工时间可控 ,资源分配 . nts 3 ABSTARCT Scheduling problem is an improtan combinatorial opti-zation problem.Scheduling problem is widely applied impr-otant problems in combinatorial optimization.The schedul-ing of tasks according to production objectives and constr-aints,to detemine the specific processing route,time,mac-hine and operation eachobject processing. Good scheduling strategy has a great role in improve economic benefits.But due to the coexistence of resource constraints and technological constaints,so the computati-onal complexity theory shows that,most scheduling problr-m belongs to NP a hard(Nondeter ministiepolynomial Har-d,non deteministicpolynomial) problem target search rela-tes to the combinatorial explosion of the solution space.S-orting algorithm of the comprtitive ratio analysis is the so-ft of algorithm the risks of a assessment and security,has the important theory significance and practical value. This paper discusses the single machine scheduling p-roblem with controllable processing time of delivery and t-he workplece.According to the properties the optimal res-ource allocation method and the problem can be converte-d to assigment problem by construting a polynomial time ,Algorithm to detemine the optimal ordering and the learn-ing effect and problem with controllable processing times Respectively discusses the processing time is a linear res-ource functions and convex resource function in two case-sproved that this kind of problem is polynomial time solv-able finally discussed a special case study factor is consta-nt processing time is a convex resource function gives co-mplexity is O(nlog n)algorithm by running this algorithm .To detemine the optimal resource allocation optimal quan-tity and parts of the soft. Key words:the single machine scheduling,delivery p-eriod,controllable processing times,resource allocation. nts 4 摘 要 4 ABSTRACT .5 第一章 绪论 .8 1.1 课题研究的背景和意义 .8 1.2 课题研究 的目的意义和主要内容 .9 1.2.1 排序问题的简述 .9 1.2.2 排序问题的求解 .10 1.2.3 算法复杂性的简介 . .10 1.3 本章小结 .11 第二章 带有交货期和加工时间可控的单机排序问题 .12 2.1 单机排序 .12 2.1.1 符号说明 . .12 2.1.2 常用排序方法 . .13 2.2 带有交货期和加工时间可控的单机排序问题 .14 2.2.1 问题描述 .14 2.2.2 资源约束 .16 2.2.3 模型推广 .19 2.3 应用举例及计算结果 .23 2.4 本章小结 .25 第三章 仿真与分析 .25 3.1 车间调度仿真 .25 3.1.1 车间调度问题的描述 .25 3.1.2 车间调度问题的特点 .25 3.2仿真调度的原理和特点 .26 3.2.1 仿真调度的原理 .26 3.2.2 仿真调度的特点 .26 3.3 仿真的基本方法 .27 3.3.1 仿真的三种方法 .27 3.3.2 仿真在调度中的作用 .27 3.3.3 车间生产仿真调度业务流程 .28 3.4 实例仿真 .29 3.6 本章小结 .41 第四章 总结与展望 .42 nts 5 参 考 文 献 .44 毕业设计小结 .45 致 谢 . .46 nts 6 nts 7 第一章 绪论 1.1 课题研究的背景和意义 近年来带有可控加工时间的排序问题受到越来越多的关注。加工时间可控是指工件的实际加工时间是一个依赖资源量的函数。关于带有可控加工时间的单机排序问题最早是由 Viction 提出的。 Cheng 等研究了带有工期和可控加工时间的单机排序问题，分别讨论了在 2 种工期分派方法下极小化总 提前时间总延误时间和资源消耗的总费用问题。王方等讨论了具有学习效应的工期指派和可控加工时间的单机排序问题目标是确定工件最优的加工顺序 )最优工期和资源分配量对于 2 种不同资源消耗与 3 种不同的工期分派方法的每一种组合，均给出了多项式时间算法。 Chio 等研究了带有可控释放时间和可控加工时间的单机排序问题， Shabtay 和 Steiner 对于可控加工时间的排序问题做了详细的综述。 在交货期问题中若工件在交货期中完工则不产生惩罚费用若工件在交货期之前或之后完工则会产生提前或延误的费用。 Liman 等研究了带有公共交货期且交 货期的开始时间和大小都是待确定的单机排序问题郭玲等考虑了将加工时间可控与交货期结合在一起的模型讨论了带有公共交货期和可控加工时间的单机排序问题 $目标是极小化总完工时间、提前时间、延误时间、交货期的结束时间和资源分配的总费用证明了这个问题是多项式时间可解的。 Wan 研究了带有大小固定的交货期和可控加工时间的单机排序问题。 Mor 和 Mosheiov 讨论了每个工件都有一个待定的交货期且交货期大小相同带有维修活动的单机排序问题目标函数是极小化包括总提前、总延误、交货期的开始时间和交货期的大小的总费用。此外， Mosheiov 和 Sarig 对于带有交货期的排序问题也进行了深入研究。 本文考虑文献的排序模型将加工时间可控与每个工件均有一个待定交货期的问题结合构成一个新的模型给出了一些最优解的性质并将问题最终转化成指派问题证明了该类问题是多项式时间可解的。 1.2 课题研究的目的意义和主要内容 nts 8 排序又称调度 ,作为运筹学的一个分支 ,是一门应用性很强的学科 ,有着其深刻的实际背景和广泛的应用空间。在现代企业竞争中，准时生产已经成为一种重要的竞争策略。根据准时生产原则，工件的完工时间要尽量地靠近某一时刻（时间段）。如果工 件在该时刻（时间段内）完工，就不会产生惩罚；如果工件在该时刻（时间段）之前或之后完工，就会产生提前或者延误的惩罚，这就是工期问题（工期窗口问题）。同时为提高机器的生产效率，可以考虑在机器上执行维修。本文主要讨论的是带有交货期和加工时间可控的单机排序问题，问题如下： 首先，第一章介绍有关排序问题的预备知识、相关问题的研究现状。第二章中，主要讨论了带有交货期和工件的加工时间可控的单机排序问题。其中，工件的加工时间是其资源分配的线性非增函数，并且分配资源会产生费用，目标函数是极小化总完工时间、提前时间、延误时间、 工期窗口的结束时间以及资源分配的总费用。我们证明了该问题可以转化为指派问题，即该问题是多项式时间可解的。第三章讨论带有交货期和加工时间可控的单机排序问题的仿真。主要讨论使用软件进行单机排序问题仿真的结果。工件的实际加工时间是关于工件的开工时间、工件的位置以及资源分配的函数。目标给出了最优排序的一些性质及最优资源分配的求解方法、多项式算法，证明了这些问题在多项式时间内可以求得最优解。最后，对本文的主要结果进行总结，并提出将来的研究方向。 只有一台处理机作业的排序问题我们称之为单处理机 (singleprOCessor)排序问题，又称单机排序间题，否则称为多处理机问题。在多处理机排序问题中 ， 如 果 所 有 的 处 理 机 都 具 有 相 同 的 功 能 ， 称 它 们 为 平 行 机(parallelproCessors)。平行机按处理的速度又可以分为三种类型：同型机(identicalprocessor) 、 同 类 机 (uniformproeessors) 和 不 相 关 机(unrelatedproeessors)。 在下面文章中主要涉及的是单机排序问题。 1.2.1 排序问题的简述 排序 (scheduling)问题是一类重要的组合优化问题，它产生的背景主要是机器制造，后 来在管理科学、计算机控制、硬件设计、生产调度和工程技术等nts 9 很多领域应用非常广泛。排序问题可描述为利用一些处理机 (processor)、机器 (maehine)或资源 (resouree)最优的完成一批给定的任务 (task)或工件(job)。最优的完成指的是使目标函数达到最小，而目标函数通常是对工件加工时间的长短、机器的利用率等的描述。现实生活中的许多问题都可以纳入这种模型之中。在理论上，排序问题又与算法设计和计算复杂性的理论密切相关，引起了国内外许多专家学者的关注，得以迅速发展。 排序问题基本上是由处理机的数量、 种类与环境，以及任务或作业的性质和目标函数所组成。对于排序问题的分类 ,目前国际上通用的分类方法是Graham 等人首先使用的三参数表示法：、，这里表示机器情况 ,即机器的数量，类型和环境。表示工件的情况，即工件的特征，加工要求和限制，对加工的影响等约束条件。表示目标函数。 1.2.2 排序问题的求解 排序间题是一类重要的组合最优化问题，因为排序问题中所涉及的机器、工件都是有限的，绝大多数的排序问题是从有限个可行解中找出一个最优解，使得目标函数达到极小。在排序问题中我们称可行解为可行排序，称最优解 称最优排序。 对于问题的每一个实例，其可行解的个数是有限的，因而我们可以用枚举的方法求得最优解。然而一般情况下这种方法是没有现实意义的，因为有时问题可行解的数目非常巨大，尽管我们用最先进的计算机，所花费的时间也是不能接受的。 1.2.3 算法复杂性的简介 在算法复杂性理论中，“问题”指对一类问题总的描述。“例子”是一个给定了一组数据的具体问题。对于某个问题，如果存在一个算法可以解决该问题的任何一个例子，则我们把这个问题称为可计算的。衡量一个算法的好坏，我们主要看占用储存的大小和所用时间的多少。前者称为空间 复杂性，后者称为计算复杂性，在组合最优化中，算法复杂性指的是算法的时间复杂性 。 1.3 本章小结 nts 10 排序问题是组合最优化学科的重要组成部分之一。一个医院门诊 ,大家是按照时间先来后到排序 ,还是按照病情轻重缓急排序 ;一个大型工程 ,各种机械设备是按照机器运行成本排序 ,还是按进度需要排序 ;一个工件加工车间 ,工件加工是按照资源利用率排序 ,还是按照完工期限排序 ,这些都要涉及排序问题 。它是工业生产和日常生活。虽然排序学科的研究在 20 世纪 50 年代开始形成的 ,但是在近 60 年来得到了广泛而深入的研究 ,现在已成为运筹学中柑当有活力 的一支。 作为一类重要的组合优化问题 ,排序问题得到了越来越广泛的关注与研究 ,并且得到了重要的成果与应用。单机排序问题是最简单的一类排序问题 ,同时也是最重要的排序问题之一。单机排序问题大量存在于现实生活中 ,有着广泛的实际背景 ,而且比较容易求解 ,能够为更复杂的排序问题提供指导。 排序问题普遍应用于生产管理、运输调度、计算机系统等领域，引起许多专家学者的广泛关注，并以实际生产活动为基础进行理论研究。经典排序问题的首篇文章是 1954 年 Johnson发表的一篇重要论文。虽然我国对于排序问题的研究起步比较晚，始于上 世纪六十年代，但是从上世纪九十年代起国内的学者们对排序问题的研究已呈现出新兴景象，排序问题的研究成果亦如雨后春笋。 排序问题是组合最优化这门学科的一个重要组成部分，有着重要理论意义和广泛实际背景。排序问题产生的背景最初是机械制造，后来被生产管理、计算机系统和运输调度等领域广泛应用。如今生产计划调度，信息处理，公用事业管理等许多方面都要用到排序的理论和方法，同时排序问题与理论计算机科学、离散数学等学科都存在着紧密的联系。 由于本人的水平有限，加之时间比较仓促，文中肯定会有很多错误和不妥之处，恳请各位老师批评指 正。 nts 11 第二章 带有交货期和加工时间可控的单机排序问题 2.1 单机排序 排序问题，又称为调度问题，其产生的背景是机器制造。概括地说，单机排序是利用一台机器，在执行某些任务时，在某些限制条件下 (如工件的到达时间、完工截止时间、优先约束、资源约束、机器对加工时间的影响等 )，寻找最优加工方式使某个或某些目标函数达到最优。目标函数通常是对加工时间的长短、处理机的利用率等的描述。它是“投入最少，产出最优”的一种系统优化过程。由于排序问题最早是在机器制造领域中提出来的，因而排序问题各要素的描述沿用了 机器制造中的术语。机器 (machine)、工件 (job)和目标函数 (objective function)是各种排序问题的三要素。 现给出单机排序的一般描述。设有 n 个工件 J1， J2， Jn， 工件 Jj的 权为 uj，工件 Jj的工期为 dj。若工件 Jj排在第 r 个位置加工，则其加工时间为Jr Jp p r， j=1， 2， n。其中 pJ 为工件 Jj 的正常计算共时间，其单机排序问题可记为 1 ( )J r Jp p r f c。 2.1.1 符号说明 由于排序问题中机器的数量和类型，工件的准备时间、加工位置、完工要求、资源数量等情况错综复杂，因此为简化问题描述和方便各位老师批评，对本文常用符号作如下说明： J1， J2， Jn表示 n个待加工的工件； pj（或 pjr）（ processing time）表示 Jj（排在第 r 个位置上）的实际加工时间； jp表示工件 Jj的正常加工时间； uj表示分配给 Jj的资源量； ju 表示分配给工件 Jj的资源量上界， 0 jjuup ； wj表示工件 Jj的权重； Cj（ completion time）表示工件 Jj的完工时间； dj(due time)表示工件 Jj 的工期，如果 djCj 表示工件提前完成，如果dj0， xj0。 由前面的讨论容易得到以下结果。 1） 目标函数可表示为 ()()()11()()jannj kj j jjjjpjZ b xx（ 8） 2)最优资源分配。将（ 8）式看成是关于 xj的函数，对其求导并令导数为零。则可以求出最优资源分配 ()1* 11( ) ( )()( ) ( )jkaj kkjjjkx p jb (9) 其中 j由 (3)式决定。 将（ 9）式代入（ 8）式中可以得出 ()111 1 1 1( ) ( )()1( ) ( ) ( )jkk nakk k k kjjjjZ k k b p j j （ 10） 2） 最优排序。问题 2可以转 化为指派问题，即（ 6）式。其中 111 1 1 111( ) ( ) ( )jkk nnakk k k ki j i jiijk k b p j j （ 11） 3)多项式时间算法。问题 2可以通过算法 1 求得最优排序，不同的是步骤 2中的 ij由（ 11）式决定，步骤 4中的最优分配资源由（ 9）式决定，步骤 5中的最优加工时间由 ( ) ( )jaj kjrjprpxx求得，计算复杂性为 O（ n3）。其证明过程同定理 1。 接下来讨论 aj=a， j=1， 2， n这一特殊情况。 nts 21 由（ 10）式可以得到 111()1()k nkkjjjZ k k （ 12） 其中 1( ) ( ) ()() kkjj jbp （ 13） 1 1()ak kjj j （ 14） 引理 112 将（ 12）式中最小的 j匹配给最大的 （ j） 值，第二小的 j值匹配给第二大的 j值，如此进行下去，得到的排序是最优排序。 算法 2 步骤 1 置 *( 1 )()1kjjqp ， *( 2 ) ()1ljjqp ，其中()nk ， ()nl ； 步骤 2 对每一个目标函数，通过（ 13）、（ 14）式计算， j， j， j=1， 2， n； 步骤 3 按照引理 1的方法对工件进行排序，定义最优排序为 *=（ J（ 1） ， J（ 2） ， J（ 3） ， J（ n） ）； 步骤 4 通过（ 9）式计算最优资源分配； 步骤 5 通过式子 ( ) ( )aj kjrjprpxx计算最优加工时间； 步骤 6 置交货期的最优长度为()1ljjkDp 。 定理 2 算法 2求得排序问题 1 ( ) ( )aj kjrjprpxxnts 22 ( 1 )( ) ( ) ( ) ( ) ( ) ( )1()nj j j j j jjE T d D b x 的最优排序，计算复杂性是 O（ nlog n）。 证明 由以上讨论可知，算法 2的主要计算在于步骤 2，由于步骤 2的计算复杂性为 O（ nlog n），因此算法 2的计算复杂性为 O（ nlog n）。 证毕 2 3 应用实例及计算结果 例 1 机械加工 一个机械加工车间要加工一批机器零件，每一个零件都具有相同的工序，即按相同的顺序在几个不同的机床上加工，但每个零件 在每个机床上的加工时间可能不同。如何安排加工顺序才能以最短的时间加工完所有的零件？这是一个流水作业排序间题。 例 2 进程排序 在计算机多道程序操作系统中，并行执行多个进程：在宏观上同时执行多个进程，在微观上在任何时刻 CPU 只能执行一个进程。进程的到达时间是不同的，怎样排序这些进程才能使 CPU 的利用率最高或进程的平均周转时间最短？这也是一个排序间题。 例 3 机场排序 在一个飞机场，有几十个登机门，每天有几百架飞机降落和起飞。登机门的种类和大小是不同的，班机的机型和大小也是不同的。一些登机门安放在能容纳大型飞机 的地方，小登机门只能容纳小型飞机。飞机按时刻表降落和起飞 ,由于天气和机场的其它原因，时刻表也有很大的随机性。当飞机占有登机门时，到达的旅客下飞机，出发的旅客上飞机，飞机要接受诸如加油、维护和装卸行李等服务。如果飞机在下一个机场不能按时降落，此时为了节省燃料，飞机不能起飞，登机时间推迟，飞机需要占有一个登机门而其它的飞机不能使用。机场的排序人员需要制订一个可行的方案，把登机门分配给降落的飞机，使机场的利用率最高或晚点起飞的飞机最少，这也是一排序问题。在这里飞机被看成是被加工的工件，登机门当作机器，机场的规定是 约束条件。 nts 23 这里，由于本科期间的专业限制，本文举例侧重于机械加工。 设 n=5,工件的正常加工时间向量为 p =(11,9,15,7,12)工件的正压缩率向量为 a =(0.5,0.7,0.4,0.3,0.9)。资源分配的上界向量为 u =（ 20， 12，25， 21， 13），工件的退化因 子 =0.2，退化率 =0.1。单位资源的费用向量b=（ 6， 11， 8， 5， 9）。工件的提前时间，延误时间和工期的单位费用分别为 1=1， 2=4， 3=2。维修的基本时间和退化率分别为 t0=10， =1。 解：为计算准确和方便，考虑 Cij 保留两位小数， Wr 保留三位小数。首先，当 i=0（ 0），根据在 CON 型工期指派问题中，最优工期和某个工件的完工时间一致，若最优工期 d*=Ck，则 2312()nk ，计算 k*=2，因此， d*=C2 。然后，利用 11nnj j j jjjZ U w p b u 求得向量 w =（ 10， 11， 12， 8， 4），利用 11 ()nnj j j j jjjjZ U W p b W a u 和,( ) ,r j r jjjrr j r j j j r rjW p b W acW p b W a u b W a p分别求得向量 w =（ 15.037， 16.523， 17.042， 11.248， 5.519）， C1j=（ 135.04， 136.52， 137.04， 124.12， 60.71）， C2j=（ 135.33， 141.91， 142.23， 101.56， 49.67）， C3j= (225.56, 247.85， 255.63， 169.26， 82.79)， C4j=（ 105.26， 115.66， 121.66， 66.78， 38.63）， C5j=（ 121.51， 121.96， 122.11， 120.39， 66.23）。 利用 Matlab软件解指派问题求得最优排序为 *0 4 1 5 2 3 ( , , , , )J J J J J nts 24 且指派问题的最优值为 *0 548.24f ，利用 2312()nk 求得0U =100，最优值 *0Z =648.24。对于 i=1， 2， 3， 4 的情况的计算与此相同（如图） 。 图 2-1 从表中可知， * * * * * *4 0 1 2 3 4m i n , , , , Z Z Z Z Z Z，因此最优维修位置是 i*=4，最优排序是 * 4 5 2 3 1 ( , , , , )J J J J J 。 2.4 本章小结 本文讨论的是工件的加工时间是资源分配的线性函数的单机排序问题及与位置相关的加工时间可控问题。给出了最优排序的一些性质，及最优资源分配的求解方法、多项式算法，证明了这些问题在多项式时间内可以求得最优解。 第三章 课题仿真 由于本人在本科期间的专业限制 ,所以本文把排序问题延伸至车间调度问题上 ,再进行仿真。 3.1 车间调度仿真 车间资源的有限性制约着能否有效利用车间现有资源完成任务 ,以最快的速度响应市场需求 ,促使制造型企业能否赢得市场竞争。调度任务是根据生产目标和约束，为每个加工对象确定具体的加工路线、时间、机器和操作等。优良的调度策略对于提高生产系统的最优性、提高经济效益都有着极大的作用。 3.1.1 车间调度问题的描述 车间生产调度问题是调度问题的一个子集。可以描述为 :个工件在台nts 25 机器上加工 ,一个工件分为道工序 ,每道工序可以在若干 台机器上加工。典型的生产调度问题涉及一个要完成的任务集 ,其中每一个任务包含一组需要执行的作业序列 (工序 ),这些作业序列需要占用系统的机器、工具等资源 ,并且必须按照一定的工艺顺序执行 ;一个资源集合 ,包括人员、设备、工具和材料等 ,每台设备可以完成一种或多种作业 ,不同设备能完成的作业集可能相同也可能不同 ;一个约束条件集 ,如任务的优先级、工序的先后关系、每个作业要求完成的时间、资源的能力等 ;一个性能指标集 ,用以规定生产过程中需要优化的目标 ,如生产周期、在制品量、订单交货期、资源利用率和生产成本等。调度的目标就是要为 作业集中的作业合理分配资源 ,合理安排每个作业的加工次序 ,使约束条件被满足 ,同时使部分或全部生产性能指标得到优化。 3.1.2 车间调度问题的特点 在实际的制造企业车间生产环境中，更普遍的调度类型应当是具有 Job-shop 调度和动态调度属性的混合类型，车间调度问题主要具有以下几个特点。 1)复杂性 :由于生产车间中工件、机器、缓存及搬运系统之间相互影响、相互作用，每个作业又要考虑它的加工时间、操作顺序和交货期等，因而相当复杂。同时计算量极大，是典型的非多项式 (Nonpolynomial， NP)难题。 2)动态随机性 :在实际的生产调度系统中存在很多随机的和不确定的因素，环境是不断变化的，在运行过程中会遇到多种随机干扰，而且生产系统中常出现一些突发偶然事件，动态随机性大。 3)多目标性 :实际的计划调度往往是多目标的，并且这些目标间可能发生冲突。这种多目标性导致调度的复杂性和计算量急剧增加。 4)多约束性 :生产车间中资源的数量、缓存的数量、工件的加工时间和加工顺序都是约束。此外还有一些人为的约束，如要求各设备上的负荷平衡等等。 3.2 仿真调度的原理和特 点 3.2.1 仿真调的德原理 制造系统的 调度问题是在制造资源、加工工艺等约束条件下 ,寻求一组控nts 26 制和决策变量，使得某个目标达到或接近最优。优化理论方法用一组等式或不等式表示这种约束关系，通过推导和计算确定使目标函数最优的决策变量值，具有很好的优化效果。但是当调度问题比较复杂时，数学模型可能非常复杂，计算量大，也可能出现无解的现象。 仿真调度的基本原理是，建立仿真调度模型，在仿真调度决策规则的引导下，在模型上试探性地经历整个加工过程，记录该过程中系统的状态变化，统计、处理并产生调度方案和性能数据。因此仿真调度方法实际上是一种实验性和试探性的方法，不会 出现无解的现象。 3.2.2 仿真调度的特点 离散事件系统建模和仿真的关键是对导致系统状态发生变化的事件的定义和处理。在仿真调度问题中，通常把工序 (或操作 )的启动事件和结束事件看作两类最基本的事件。在工序启动函数中实现对资源的竞争和申请，在结束函数中实现资源的释放和再分配。由于存在竞争，一个工序可能在多次启动尝试后，才能真正开始。当一个工序开始时调度其结束事件 ;当一个工序结束时调度下一个工序的开始事件 ;在处理这些事件中实现仿真时钟的推进，直到所有订单的所有工序加工完毕。 由于仿真中对资源的竞争和分配始终满足 资源的容量约束，工序启动后对结束事件的安排满足加工时间约束，工序结束后对下一个工序的安排满足工艺顺序约束，因此仿真产生的调度方案是调度问题的可行解。 由于采用事件调度和进程交互等仿真建模方法，只处理那些导致系统状态发生改变的有限个事件，而且仿真步长是可变的，因此能够有效地减少仿真的计算量，提高调度速度。在仿真运行过程中，全面收集和记录系统状态变化数据，使仿真具有很强的调度能力，具体表现在以下几个方面。 1)根据这些数据生成针对设备、操作、库存和物料系统的详细调度方案等，调度能够用符合企业惯例和控制需要的形式 表达。 2)能够给出完整的性能统计数据，有利于对调度进行综合评价和选择。 3)当出现紧急订单、原材料迟到、设备故障等情况时，原来的调度不再适用，需要重新调度，而该时刻系统状态完整地保存着，可以作为系统状态的初始值。 nts 27 3.3 仿真的基本方法 3.3.1 仿真的三种方法 离散事件系统仿真中仿真进程的推进方法是十分重要的。应用任何一种方法都应考虑如何选择下一事件， 以便执行相应的程序模块来修改系统状态，进行各种统计计算。根据处理的方法不同， 可将离散事件仿真分成三类。 ( 1) 事件调度法 : 这种方法有一个时间控 制程序。从事件表中选择具有最早发生时间的事件，并将仿真钟修改到该事件发生的时间，再调用与该事件相对应的处理模块，该事件处理完后返回时间控制程序。 ( 2) 活动扫描法 : 在这类仿真中，系统由部件组成，而部件包含着活动，活动是否发生取决于规定的事件是否满足，因而有一个专门模块来确定激活条件。若条件满足，则激活相应部件的活动模块。 ( 3) 进程交互法 : 这种仿真方法的特点是采用两张事件表， 即当前事件表与将来事件表。它首先按一定分布产生到达实体并置于将来事件表中，实体进入排队等待；然后对当前事件表进行活动扫描 ，判断各种条件是否满足；再将满足条件的活动进行处理，仿真钟推进到服务结束并将该实体从系统中清除；最后把将来事件表中是当前事件的实体移到当前事件表中。 3.3.2 仿真在调度中的作用 仿真方法在调度中的作用表现在三个方面： (1) 调度方案的验证、评价和选择。这是仿真在调度方面最早的应用。制造系统的调度问题具有 NP-hard 特性，为了减少计算量， 基于优化方法的调度通常要对实际系统进行较多的简化，这就需要对模型的正确性和调度的合理性进行检验。 (2) 确定控制及决策规则。生产过程是复杂过程，经常面临决策和选择 ，比如，当多个工序竞争同一设备时，如何选择工序；当多台设备都可以进行某个工序时，如何选择设备：当工件的工序可以互换时，如何确定下一道工序，针对不同的决策和选择，采用不同的规则及组合，会得到不同的生产效果。采用仿真方法作为辅助工具，对特定的系统和问题建立仿真模型，规则作nts 28 为变量，通过仿真、分析和比较，确定有利于调度目标的控制和决策规则。 (3) 仿真直接用于调度。这是最近几年仿真技术的最新的应用。对于生产调度方法的五个特征，离散事件仿真技术都能够满足， 具有直接用于调度的潜力。 3.3.3 车间生产仿真调 度业务流程 仿真调度的流程如图所示。 图 3-1 (1) 通过调度接口从 AMS 数据库中获取所需的零件信息，包括零件加工路线、工艺顺序及工序时间等 ; (2) 控制层中获取有关 AMS 的车间状态信息 ; (3) 将上述零件信息和车间状态信息发送给 CTPN 仿真器 ; (4) 运行 CTPN 仿真程序，根据给定的调度准则从分派规则库中选择适当的分派规则来解决 CTPN 中的冲突，并根据仿真结果选择最佳的规则或规则组合 ; (5) 将上述最佳的规则或规则组合 发送给调度方案生成器以生成最终的调度结果 ; (6) 将调度结果通过调度接口发送到控制层。上述步骤是调度机的正常工作过程 , 当 AMS 系统发生扰动时 ( 如设备故障、急件加入等 ) , 调度机必须具有再调度的能力。再调度的工作流程如下 : nts 29 1) 控制层基于 CTPN 的分派器中获得当前的 CTPN 标记信息 ; 2) 上述标记信息发送给 CTPN 仿真器 ,并作为 CTPN 仿真器的初始状态 ; 3) 重新运行 CTPN 仿真程序 ,并将再调度结果发送给控制层的分派器。 3.4 仿真举例 以下是一个仿真调度问题的实例。 仿真所用软件 :Lekin(flexible job-shop scheduling system) 首先设置为单一机器，工件数为 5个工件，分别为 J001,J002,J00 3,J004,J005。 J001:Release date 为 15,Processing Time 为 10,Due date 为30,Status为 A,Weight 为 20。 J002:Release date 为 1, Processing Time 为 20, Due date 为 25, Status为 A,Weight 为 30。 J003:Release date 为 0, Processing Time 为 30, Due date 为 30, Status为 A,Weight 为 40。 J004:Release date 为 2, Processing Time 为 4, Due date 为 8, Status为 A,Weight 为 5。 J005: Release date 为 1, Processing Time 为 30, Due date 为 45, Status为 A,Weight 为 60。 以上为本次仿真各个工件的数据。 图 3-2 在 Scheduling 中进行排序。在 Rule 中包含了 8 种排序类型，分别为，nts 30 1.ATCS,2.EDD,3.MS,4.FCFS,5.LPT,6.SPT,7.WSPT,8.CR. 1.在 ATCS（航空排序系统）情况下排序为 J005 J001 J002 J003J004。 Gantt Chart 图为： 图 3-3 Objective Chart图为： 图 3-4 Sepuence图为： nts 31 图 3-5 在 Gantt Chart图中工件名称有阴影的工件为 Late Jobs。 2.在 EDD（最后交货日期）情况下排序为 J004 J002 J001 J003 J005。Gantt Chart图为： 图 3-6 Objective Chart图为： 图 3-7 Sepuence图为： nts 32 图 3-8 在 Gantt Chart 图中工件名称有阴影的工件为 Late Jobs。
- 温馨提示:
1: 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
2: 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
3.本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
人人文库网所有资源均是用户自行上传分享，仅供网友学习交流，未经上传用户书面授权，请勿作他用。
|
2:不支持迅雷下载,请使用浏览器下载
3:不支持QQ浏览器下载,请用其他浏览器
4:下载后的文档和图纸-无水印
5:文档经过压缩，下载后原文更清晰
|
川公网安备: 51019002004831号