机械毕业设计992具有学习效应的总完工时间流水线排序问题与仿真.docx
机械毕业设计992具有学习效应的总完工时间流水线排序问题与仿真
收藏
资源目录
压缩包内文档预览：(预览前20页/共34页)
编号：554262
类型：共享资源
大小：449.78KB
格式：ZIP
上传时间：2015-12-04
上传人：QQ28****1120
认证信息
个人认证
孙**（实名认证）
辽宁
IP属地：辽宁
6
积分
- 关 键 词：
-
机械毕业设计论文
- 资源描述：
-
机械毕业设计992具有学习效应的总完工时间流水线排序问题与仿真,机械毕业设计论文
- 内容简介：
-
I 本科毕业设计论文 题 目 具有学习效应的总完工时间流水线排序问题与仿真 专业名称 机械设计制造及其自动化 学生姓名 指导教师 毕业时间 二一四年 七月 nts I 摘 要 排序问题的一大特点是 :模型繁多，适用于某一模型的算法，只要将模型的条件稍加变化，该算法即不适用 . 包括如何对各个部件进行分隔、布线和布局的问题” .排序论是国际上发展最迅速、研究最活跃、成果最丰硕、前景最诱人的学科领域之一特别引人注目的是 :随着现代工业的发展，经典的排序模式已被突破，新的模式层出不穷，吸引了越来越多的理论工作者和实际工作者、可控排序、多目标排序、成组分批排序、同时加工排序、准时排序和窗时排序、资源受限排序、不同时开工排序、随机排序、模糊排序、应用排序等，就是其中发展最为迅速的一些新方向 . 在我国，对排序问题的研究较晚，虽然早在 20 世纪 50 年代末，就有人注意到这一问题一问题的研究，并开始作一 些宣传普及的工作 ;但由于众所周知的原因，对这，直至 70 年代中才开始，到 80 年代，对算法感兴趣的人越来越多 。现 研究工件具有学习效应的 单 台机器流水作业排序问题 与仿真 。工件的学习效应指工件的加工时间为所排位置的指数函数。目标函数为极小化总完工时间。给出该问题的数学规划模型。同时对大规模问题给出 3 个启发式算法 ,并给出 计算结果。 ， 关键词 ： 排序 ，流水作业，学习效应， 总完工时间 nts II ABSTRACT Scheduling problem is a major feature: the model range, the algorithm applies to a model, just a little change in the conditions of the model, the algorithm does not apply. Including the issue of how to separate the various components, wiring and layout. Sort theory is one of the worlds most rapid development, research the most active, the most fruitful achievements, the most attractive prospects disciplines are particularly striking: With the development of modern industry, the classic sort mode has been a breakthrough, new pattern emerging, attracting a growing number of theorists and practitioners, controlled sorting, multi-objective sort, group scheduling, while processing sort, sort, and when the time window of sorting, resource-constrained sort, is not the same start sorting, random order, fuzzy sort, sorting applications, is one of the fastest growing number of new directions. In China, the problem of sorting study late, although in the late 1950s, it was noted that a study of this issue of the problem and begin to make some outreach work.However, due to reasons known to all, this, until the mid-1970s began, to the 1980s, to more and more people interested in the algorithm. In this paper we consider single machine flowshop scheduling problem with a learning effect.The learning effect of a job is assumed to be an exponent function of its position.The objective is to find a sequence that minimizes the total completion time. A mathematical programming model is developed for the problem and three heuristic algorithms are proposed for solving the problem with large scale. Compuational results show that the proposed heuristic algorithms are effective in solving the problem with large scale. KEYWORDS: scheduling， flow shop， learning effect， the total completion timents西北工业大学明德学院本科毕业设计论文 - 3 - 目 录 第一章 绪论 . 5 1.1 流水作业排序问题 . 5 1.2.1 排序问题的分类 . 9 1.3 排序问题的求解 . 9 1.3.1 可行排序和最优排序 . 9 第二章 具有学习效应的总完工时间流水线排序 . 12 2.1 问题描述 . 12 2.2 预备知识 . 12 2.2.1 学习效应的概念 . 12 2.3 单机排序问题 . 14 2.3.1 加权总完工时间问题 . 14 2.4 数学规划模型 . 15 2.5 启发式算法 . 16 2.5.1 启发式算法 1 . 16 2.5.2 启发式算法 2 . 17 2.5.3 启发式算法 3 . 17 2.6 数值试验 . 17 2.6.1 基本假设 . 17 2.6.2 数据模拟 . 18 第三章 流水线作业排序模型仿真 . 20 3.1 仿真软件介绍 . 20 3.2 Liken 仿真软件算法介绍 . 20 3.2.1 EDD 算法规则 . 20 3.2.2 加权最短作业时间法则（ WSPT） . 20 3.2.3 SPT 算法规则 . 20 3.3 仿真 . 22 3.3.1 仿真前提条件 . 22 3.3.2 仿真计算 . 22 nts西北工业大学明德学院本科毕业设计论文 - 4 - 第四章 仿真分析与算法优化 . 27 4.1 车间作业排序问题仿真优化系统的构建思想、方法与框架 . 27 4.2 算法优化 . 27 第四章 总结与展望 . 29 5.1 论文总结 . 29 5.2 后续与展望 . 30 致 谢 . 31 参考文献 . 32 毕业设计小结 . 33 nts西北工业大学明德学院本科毕业设计论文 5 第一章 绪 论 1.1 流水作业排序问题 1.1.l 引例 排序 (scheduling)问题产生的背景主要是机器制造，后来被广泛应用于计算机系统、运输调度、生产管理等领域 .从普通的生产部门的计划安排、人员调度，学校课程表的制订，到宇宙飞船的复杂庞大的飞行计划，都要用到排序的理论和算法 。 在给出排序问题的一般定义之前，我们先看几个排序在实际领域中应用的例子 。 例 1.1 机械加工 一个机械加工车间要加工一批机器零件，每一个零件都具有相同的工序， 即按相同的顺序在几个不同的机床上加工，但每个零件在每个机床上的加工时间可能不同 .如何安排加工顺序才能以最短的时间加工完所有的零件 ，这是一个流水线排序问题 。 例 1.2 进程调度 在计算机多道程序操作系统中，并发执行多个进程，在宏观上同时执行多个进程，在微观上在任何时刻 CPU 只能执行一个进程 。 进程的到达时间是不同的，怎样调度这些进程才能使 CPU 的利用率最高或进程的平均周转时间最短 ?这也是一个排序问题 。 另外，每个进程的到达时间和执行时间事先是不知道的，但随机到达时间和执行时间的分布、它们的数学期望、方差等是已知的，这时的目标是极小化平均周转时间的数学期望 。 排序问题中出现了随机变量称作随机排序问题 。 例 1.3 机场调度 在一个飞机场，有几十个登机门，每天有几百架飞机降落和起飞 。 登机门的种类和大小是不同的，而班机的机型和大小也是不同的，一些登机门安放在能容纳大型飞机的地方，小登机门只能容纳小型飞机 。 飞机按时刻表降落和起飞，由于天气和机场的其他原因，时刻表也有很大的随机性 。 当飞机占有登机门时，到达的旅客下飞机，出发的旅客上飞机，飞机要接受诸如加油、维护和装卸行李等nts西北工业大学明德学院本科毕业设计论文 6 服务。如果飞机在下一个机场不能按时降落，此时为了节省燃料，飞机不能起飞，登机时间推迟，飞机需要占有一个登机门，而其他的飞机不能使用 。 机场的调度人员需要制订一个可行的 方案，把登机门分配给降落的飞机，使机场的利用率最高或晚点起飞的飞机最少，这也是一个排序间题，在这里飞机被看成是被处理的任务，登机门当作处理机，机场的规定是约束条件 。 1.2 排序问题的定义 排序 (scheduling)问题是一类重要的组合最优化问题，它是利用一些处理机(processor)、机器 (machine)或资源 ( resource )，最优地完成一批给定的任务(task)或作业 (yob)。在执行这些任务或作业时需要满足某些限制条件，如任务的到达时间、完工的限定时间、任务的加工顺序、资源对加工时间的影 响等 .最优的完成指的是使目标函数达到最小，而目标函数通常是对加工时间的长短、处理机的利用率的描述 。 在排序问题中，处理机的数量和种类，任务或作业的顺序、到达时间、完工限制，资源的种类和性能等情况是错综复杂的，很难用精确的数学描述给出一般的排序定义 。 在本书中，我们用如下方式来描述排序问题 : 给定 n 个任务的任务集 T = T1,T2, , Tn m个处理机的处理机集 P =P1,P2, , Pm 和 s 种资源的资源集 R =R1,R2, , Rs 排序问题指的是在一定条件下，为了完成各项任务，把沙中的处理机和 (如果有 )中的资源分配给了中的任务，使目标函数达到最优 。 排序问题基本上是由处理机的数量、种类与环境，以及任务或作业的性质和目标函数所组成 。 处理机只有一个处理机的排序问题称为单 (处理 )机 (single processor, single machine)排序问题，否则称为多 (处理 )机排序问题 。 在多处理机排序问题中，如果所有的处理机都具有相同的功能，称它们为同类机或平行机 (parallel processors)。同类机按处理的速度又分为三种类型 :如果所有的处理机都具有相nts西北工业大学明德学院本科毕业设计论文 7 同的速度，称之为同速机 (identical processors );如果处理机的速度不同，但每个处理机的速度都是常数，不依赖被加工的任务，称它们为恒速机 (uniform processors);如果处理机的速度依赖被加工的任务，它们被称为变速机(unrelated processors)。 多处理机的另一种情况是多类型机 (dedicated processors)。 多类型机指的是 m 个处理机具有不同的功能。在多处理机环境中，被加工的任务需要在不同的处理机上加工 .在这种情况下，把任务 (task )称为作业 (job)。 设有作业集 J=J1,J2, , Jn 每个作业 Jj,有 nj， 道工序 (operation) T1j， T2j， ， Tnj.工序指的是作业在某处理机上被加工的这部分任务 。 如果每个作业需要在每个处理机上加工，即 nj=m ,j二 1， 2， n.而且每个作业的工序也相同，即在处理机上加工的顺序相同，把这种多类机的环境称为同顺序作业或流水作业 (flow shop)。 如果每个作业需要在每个处理机上加工，每个作业有自己的加工顺序，称之为异顺序作业 (job shop)。 如果每个作业需要在每个处理机上加工，每个作业可按任意顺序加工，把它称为自由顺序作业或开放作业 (open shop ) 。 在多处理机中，还有一种更复杂的情况，这就是柔性流水作业 (flexible flow shop)，它是流水作业和平行机的推广 。 在柔性流水作业中，有，类处理机，第 J 类有 sj个平行机，每个作业有 s道工序，每道工序需要在每类平行机中的一个处理机上加工，且每个作业的加工顺序相同 。 为方便起见，以后我们把同顺序作业、异顺序作业、开放作业、柔性流水作 业通称为车间作业 。 处理机的各种类型和环境总结如下 : 单处理机 同速机 同类机（平行机） 恒速机 自由顺序作业（开放作业） 柔性流水作业 nts西北工业大学明德学院本科毕业设计论文 8 任务和作业排序问题中的约束条件，主要指的是任务或作业的性质以及它们在加工过程中的要求和限制 。 下边的数据描述了任务的一些性质 (1)加工时间向量 任务的加工时间向量是 Pj=(p1j,p2j, , pnj) 其中 Pj是任务 Tj 在处理机 Pi，上所需要的加工时间，对同速机有 Pij=Pj，i=1,2， ， m，对恒速机有 Pij,=Pj /bi， i=1,2， ,m。 其中 Pj 是标准的加工时间 (一般是速度最慢的处理机的加工时间 )， bi是处理机 Pi的速度因子，在车间作业的排序问题中，作业 Jj的加工时间向量是 Pj=(p1j,p2j, , pnj) 其中 pij,是工序 Tj。在对应的处理机上的加工时间 。 (2)到达时间 到达时间 ( arrival time)或准备时间 (ready time) rj是任务 Tj已经准备好可以被加工的时间如果所有的任务的准备时间相同，取 rj=0 ;j=1,2, ,n。 (3)工期和截止期限 工期 (due date) dj表示对任务 Tj限定的完工时间 .如果不按期完工，应受到一定的惩罚 。 绝对不准许延误的工期称为截止期限 (deadline) 。 (4)优先因子 优先因子玛是一个权，它表示任务 Tj相对于其他任务的重要程度 .为了叙述方便起见，我们假设以上参数 Pi， rj， dj和 wj都是整数 .实际上这等价于它们可以是任意的有理数 。 我们经常用向量和矩阵的列给出这些数据 。 例如用 r=(r1,r2, , rn) d=(d1,d2, , dn) w=(w1,w2, ,wn) 分别表示 n 个任务的到达时间、工期和优先因子 。 用 nts西北工业大学明德学院本科毕业设计论文 9 p11 p1n pm1 pmn 的第 i行 (pi1,pi2, ,pin)表示 n个任务在第 i个处理机上的加工时间 。 任务被加 工时 的一个 重要约 束是可 中断 (preemptive)或不 可中断(nonpreemptive).如果排序问题中，每一个任务在加工时的任一时刻都可暂停加工，加工该任务的处理机可去加工任何其他任务，以后可在任何时刻在任意处理机上重新继续加工，这种排序问题称之为可中断排序 .任何任务都不允许中断的排序问题称为不可中断排序 。 加工任务时的另一个重要限制是任务之间的优先约束 (precedence constraints)。任务之间的优先约束是任务集 上的一个偏序关系 。 味着必须加工完 Ti才能开始加工 Tj。 如果任务集 T 中至少有两个任务受到优先约束的限制，集 T 的任务称为相关的 (dependent)，否则称为无关的 (indepent)。 1.2.1 排序问题的分类 在排序问题中，如果所有的数据在进行决策之前都是己知的，排序问题称为确定性排序 (deterministic scheduling)问题 。 如果有的数据，例如加工时间、准备时间和工期等，在做决策时是未知的，它们是一些随机变量，但它们的分布是己知的，这样的排序问题称为随机排序 (stochastic scheduling)问题 。 无论是确定性排序还是随机排序，我们都假设 : (1)任务或作业和处理机都是有限的 。 (2)在任一时刻，任何处理机只能加工一个任务或一道工序 。 (3)极小化单一目标函数，在随机排序中，极小化目标函数的数学期望 。 处理机、任务或作业和目标函数三要素组成了排序问题 。 处理机的数量、类型和环境有近十种情况，任务或作业和资源的约束条件更是错综复杂，再加上度量不同指标的目标函数，形成了种类繁多的排序类型 。 我们用 Graham 等人首先使用的三元组来描述排序问题的类型，这样能大大简化排序问题的表示 。 1.3 排序问题的求解 1.3.1 可行排序和最优排序 排序问题是一类组合最优化问题 .由于排序问题中的处理机、任务或作业都是有限的，绝大部分排序问题是从有限个可行解中找出一个最优解，使目标函数nts西北工业大学明德学院本科毕业设计论文 10 达到极小 。 在排序问题中，把可行解称为可行排序 (feasible schedule)，最优解称为最优排序 (optimal schedule)。 在排序问题中，一个可行排序是一个顺序 (sequence)或排列 (permutalion)，按照这个顺序，在给定的处理机上加工所有的任务或作业 。 例 1.1 给定排序问题 1|rj| Cj，其中 n=4, P=(3， 2， 5， i)， r=(0， 1， 0， 0) p1, p3, p4, p2是一个可行排序，对应的总加工时间是 31, p4, p2, p1, p3是一个最优排序，最优总加工时间是 21。 符号说明 Tj 第 J个任务 T 一一任务集 Jj 第 j个作业 J 一一作业集 Rj 第 J种资源 R 一一资源集 pj 任务 Tj的加工时间 P n个任务的加工时间向量 Pj 任务 Tj的随机加工时间 pij 任务 Tj在处理机 Pi上的加工时间 Pij 任务 Tj在处理机 Pi上的随机加工时间 rj 任务 Tj或作业 Jj的到达时间 r n个任务的到达时间向量 dj 任务 Tj或作业 Jj的工期或截止期限 d - n 个任务的工期向量 wj 任务 Tj的优先因子 (权 ) W n个任务的优先因子向量 Cj 任务 Tj或作业 Jj的完工时间 Cmax 时间表长 nts西北工业大学明德学院本科毕业设计论文 11 Lj 任务 Tj或作业 Jj的延误时间 Dj 任务 Tj或作业 Jj的误工时间 Uj 对任务 Tj或作业 Jj误工的单位惩罚 Pm m 个同速机 nts西北工业大学明德学院本科毕业设计论文 12 第二章 具有学习效应的总完工时间流水线排序 2.1 问题描述 具有学习效应的流水作业排序问题的一般描述如下 :设有 n 个工件J1, J2, , Jn依次在机器 M1上加工。工件 Jj在 2台 机器 M1和 M2上 加工 ,在每个机器上的加工顺序相同 ,工件 Jj在机器 Mi的工序记为 Oi,j,工序 Oi,j的正常加工时间为 pij。设工序 Oi,j排在第 r 个位置的实际加工时间为 pjr。 pjr=pj r1 （ 2 1） 式中 :i=1,2, ,m; r,j=1,2, ,n; 为学习因子 ,且 0( WjCj) 与 是最优排序矛盾 .定理证毕。 2.4 数学规划模型 下面给出问题 F2|pijr=pij r| Cj的数学规划模型。 目标函数 : minCrnr=1约束条件 : Zjrnj=1= 1, r= 1,2,n (22) Zjrnr=1= 1, j= 1,2,n （ 2 3） pir = Zjrrr=1pij r （ 2 4） i=1,2; r=1,2， ， n Sr Sr1 p1r, r 1,2, ,n （ 2 5） Cr Cr1 Xr + p2r， r 1,2, ,n (2 6) Xr = Sr +p1r + Yr Cr1 (2 7) r 1,2, ,n； C0 S0 0 式中 :j 为工件数 ,j=1,2, ,n;i为机器数， i=1,2； pir为在机器 i上 排在第r个位置工件的实际加工时间 ,i=1,2； r=1,2, ,n; Xr 为在第二台机器上第 r 个工件的开始时间与第 r-1个工件的完工时间之间的空闲时间， r=1,2， ， n； Yr为nts西北工业大学明德学院本科毕业设计论文 16 第 1 台机器上第 r 个工件的完工时间 和它在第 2 台机器上的 开始时间之差r=1,2， ， n； Sr 为第 1台机器上第 r 个工件的开始时间 ,r=1,2, ,n。约束 (2)说明在第 r 个位置只有一个工件 ;约束 (3)说明每个工件只排在一个位置 ; 约束(4)表示第 r 个工件在 机器上的实际加工时间 ; 约束 (5、 6、 7)分别表示第 r个工件的开始 时间、完工时间 与空闲时间约束。 所有的变量都是大于等于 0 且 Zjr只能等于 1 或 0。 决策变量 ： 1 如果工件 Jj排在第 r 个位置 Zjr= 0 否则 j,r=1,2,n 式 (1)中的 pijr与式 (4)中的 pir表达的意思不同 ,式 (1)中的 pijr表示在机器 Mi上的工件 Jj排在第 r 个位置的实际加工时间 ;而式 (4)中的 pir表达的是在机器 Mi上排在第 r 个位置的实际加工时间。 2.5 启发式算法 前面已把求 F2|pijr=pij r| Cj的最优解问题转化为求解相应的数学规划模型 ,数学规划问题通过数学软件 Lingo或 Lindo进行计算 ,得到最优解 ,但是 ,数学规划模型只能解决小规模问题 ,大规模问题运行的时间过长 ,很难求到最优解。 引理 1 对于问题 1 |pijr=pij r| Cj,SPT(把工件按 pj非减顺序排列 )规则产生最优排序。 受单机排序问题的启发 (引理 1),可以给出把工件按照在第 1 台机器上的加工时间的 SPT 规则排序 或把工件按照在第 1和第 2 台机器上的加工时间和的 SPT规则排序作为启发式算法。为了进一步改进启发式算法 ,可以用交换工件位 置 的方 法 ,得到改进解。下面给出这 3个算法的详细步骤 : 2.5.1 启发式算法 1 (1)把工件按 p1j (p1j表示工件在第 1 台机器上的加工时间 )非减 (SPT 规则 )顺序排列 ,即把工件按 p11 p12 p1n排列得到的排序 ; (2)设由步骤 (1)得到的排序为 0 ; (3)置 k=1; nts西北工业大学明德学院本科毕业设计论文 17 (4)置 i=k+1; (5)通过交换第 k和第 i个工件得到新的排序 1。如果排序 1的目标函数值小于排序 0的目标函数值 ,则用 1代替 0; (6)如果 i n,则置 i=i+1,转 (5); (7)如果 k n-1,则置 k=k+1,转 (4);否则 ,停止。 2.5.2 启发式算法 2 (1)把工件按 p2j (p2j表示工件在第 2 台机器上的加工时间 )非减 (SPT 规则 )顺序排列 ,即 p21 p22 p2n排列得到的排序 ; (2)设由步骤 (1)得到的排序为 0; (3)置 k=1; (4)置 i=k+1; (5)通过交换第 k和第 i个工件得到新的排序 1。如果排序 1的目标函数值小于排序 0的目标函数值 ,则用 1代替 0; (6)如果 i n,则置 i=i+1,转 (5); (7)如果 k n-1,则置 k=k+1,转 (4);否则 ,停止。 2.5.3 启发式算法 3 (1)把工件按 p1j+p2j非减 (SPT 规则 )顺序规列 ,即 p11+p21 p12+p22 p1n+p2n排列得到的排序 ; (2)设由步骤 (1)得到的排序为 0; (3)置 k=1; (4)置 i=k+1; (5)通过交换第 k和第 i个工件得到新的排序 1。如果排序 1的目标函数值小于排序 0的目标函数值 ,则用 1代替 0; (6)如果 in,则置 i=i+1,转 (5); (7)如果 kn-1,则置 k=k+1,转 (4),否则 ,停止。 2.6 数值试验 2.6.1 基本假设 （ 1）工件数为 5个，机器数为 2 台 nts西北工业大学明德学院本科毕业设计论文 18 （ 2）假设第 1 台机器上第 r个工件的完工时间 和它在第 2台机器上的 开始时间之差皆为 5min，即 Yr = 5。 （ 3）假设 5 个 不同 工件在第一台机器 每一个批次的 实际加工时间 p11p15分别 为 4,6,7,5， 9。在第二台机器实际加工时间 p21p25分别 为 7,11,10,9,6。 另外，每种工件各有 5个批次。 （ 4）假设学习因子 =0.9 （ 5） 假设 第二台机器上第 r个工件的开始时间与第 r-1 个工件的完工时间之间的空闲时间 为 0， 即 Sr = Sr1 + p1r。 2.6.2 数据模拟 对于问题 F2|pijr=pij r| Cj，令 Cj 表示得到的最优解 ,令 ASPT1表示按启发式算法 1 得到的排序 , Cj (ASPT1)表示用启发式算法 1 得到的总完工时间。令 ASPT2表示按启发式算法 2得到的排序 , Cj (ASPT2)表示用启发式算法 2的总完工时间。令 ASPT1+2表示按启发式算法 3得到的排序 , Cj(ASPT1+2)表示用启发式算法 3排序得到的总完工时间。 由以上假设我们可以得到 |pijr=pij r1| Cj 代入数据后可知： 目标函数： Cr5r=1= C1 +C2 +C3 + C4 +C5 根据 2.4 数学规划模型我们可得出： Sr = Sr1 + p1r pij r1 = p1j r1 = 4， 40.91,4 0.92， ， 4 0.94 即第一种工件的 五 个批次的完工时间分别为 4,3.6,3.24,2.92,2.62min。那么第一种工件 五个批次 的总完工时间为 18.74min。即 p11 = 16.38。 以此类推可知， p12 = 6 +6 0.91 +6 0.92 + 6 0.94 = 24.56min p13 = 7 +7 0.91 + 7 0.92 + + 70.94 = 28.67min p14 = 5+5 0.91 +5 0.92 + 5 0.94 = 20.48min p15 = 9 +9 0.9 +9 0.92 +9 0.94 = 36.85min nts西北工业大学明德学院本科毕业设计论文 19 p21 = 28.67min， p22 = 48.65， p23 = 40.94min， p24= 36.85min， p25 = 24.56min S1 = 16.38， S2 = 40.94， S3 = 69.61， S4 = 90.09， S5 = 126.94 X1 = S1 +p11 + Y1 C0 = 37.76 X2 = 4.07， X3 = 15.87， X4 = 28.65， X5 = 16.3 Cr = Cr1 +Xr + p2r， r 1,2, ,5 C1 = C0 + X1 + p21 = 66.43 C2 = C1 +X2 +p22 = 119.15 C3 = C2 + X3 +p23 = 144.22 C4 = C3 + X4 +p24 = 152.42 C5 = C4 + X5 +p25 = 193.28 则目标函数 Cr5r=1= C1 +C2 + C3 + C4 +C5 = 675.5 nts西北工业大学明德学院本科毕业设计论文 20 第三章 流水线作业排序模型仿真 3.1 仿真软件介绍 Lekin 一款很好的生产运作管理研究与教学软件，可以快速建立单机，流水，柔性流水车间，作业车间等模型。包含许多调度算法和启发式算法。 3.2 Liken 仿真软件算法介绍 3.2.1 EDD 算法规则 最早交期法则（ EDD）： 最大延误时间最小化。交期越早者排越前面。 1955年 Jackson 提出 EDD（ Early Due Date）派工法则其应用在最小化最大延误时间和最大延迟时间，但是此法会有增加延迟工作数目和增加平均延迟时间的倾向。 3.2.2 加权最短作业时间法则（ WSPT） 最小化平均加权流程时间。将作业时间除以权重所得之值越小者排越前面 。 当工作附有重要性的属性时，排序人员可给予个别的权重权重值越大表示重要性越大。 WSPT 法则即是将作业时间除以权重所得的值越小者表示越重要的工作，而它将排至顺序的第一位，以此类推。加权平均流程时间的计算方法为： 3.2.3 SPT 算法规则 最短作业时间法则 (SPT) ： 最小化平均流程时间 。 job 作业时间越小者排越前面，亦可以使平均延误时间，平均等候时间 最小化。 最短作业时间法则 最小化平均流程时间 当 n 个作业要排至单一机台上时，利用 SPT (Shortest Process Time) 法则排序可使得平均流程时间最小化，也就是 t1 t2 tn。 范例 3.1 给予一组工作集如下表所示 ，目标为最小化平均流程时间 nts西北工业大学明德学院本科毕业设计论文 21 表 3.1 工作 i 作业时间 ti 1 4 2 8 3 7 4 3 5 10 6 12 7 6 8 5 依 SPT 派工法则排序，顺序为 4-1-8-7-3-2-5-6。其流程时间计算如下表 表 3.2 工作 i 流程時間 ti 4 3 1 3+4 8 3+4+5 7 3+4+5+6 3 3+4+5+6+7 2 3+4+5+6+7+8 5 3+4+5+6+7+8+10 6 3+4+5+6+7+8+10+12 所以平均流程时间为 = 18(83)+(74)+ (65)+(56) +(47)+ (38)+(210)+ (112)= 24.5 由以上可知工作流程时间的计算方式为 = 1nnt1 +(n 1)t2 + +2tn1 + tn nts西北工业大学明德学院本科毕业设计论文 22 除了最小化平均流程时间 以外，在 单机排序问题 中 SPT 法则亦可以最小化平均延误时间 、最小化平均等候 时间。 3.3 仿真 3.3.1 仿真前提条件 （ 1）工件数为 5个，机器数为 2 台 （ 2）假设 5 个不同工件在第一台机器每一个批次的实际加工时间 p11p15分别为 4,6,7,5， 9。在第二台机器实际加工时间 p21p25分别为 7,11,10,9,6。另外，每种工件各有 5个批次。 （ 3）假设学习因子 =0.9 （ 4）假设第 1 台机器上第 r个工件的完工时间 和它在第 2台机器上的 开始时间之差皆为 5min，即 Yr = 5。 （ 5）假设 5个作业的优先级都为 1。 3.3.2 仿真计算 利用车间排序软件 Lekin，设置参数如下图： （ 1） 如图 3.1 与图 3.2，进入 lekin 软件后，点击如图中的 Flow。并设置两台机器，五个作业 ，点击 OK。 图 3.1 图 3.2 （ 2）图 3.3 与图 3.4 为对机器 M1和 M2进行参数设置。 nts西北工业大学明德学院本科毕业设计论文 23 图 3.3 图 3.4 （ 3）图 3.5 与图 3.6 为对工作 1进行的各种参数设置。 图 3.5 图 3.6 （ 4） 图 3.7 与图 3.8 为对工作 2进行的各种参数设置。 图 3.7 图 3.8 nts西北工业大学明德学院本科毕业设计论文 24 （ 5）图 3.9 与图 3.10 为对工作 3 进行的各种参数设置。 图 3.9 图 3.10 （ 6）图 3.11 与图 3.12 为对工作 4 进行的各种参数设置。 图 3.11 图 3.12 nts西北工业大学明德学院本科毕业设计论文 25 （ 7）图 3.13 与图 3.14 为对工作 5 进行的各种参数设置。 图 3.13 图 3.14 （ 8）下图为两台机床，五个作业由 J1J5的排序图。 图 3.15 （ 9） 以下为经过 Lekin 软件 SPT 排序所得结果。 图 3.16 nts西北工业大学明德学院本科毕业设计论文 26 图 3.17 图 3.18 从图 3.17，我们可以看出， J01， J02， J03， J04， J05各自对应黄色，浅蓝，紫色，绿色，灰色。由此与图 3.16 做对比，可知 由 最短作业时间法则 (SPT)所得的排序为 J01 J04 J05 J02 J03。 nts西北工业大学明德学院本科毕业设计论文 27 第四章 仿真分析与算法优化 4.1 车间作业排序问题仿真优化系统的构建思想、方法与框架 传统的仿真优化集成思想如图 4.1所示。对系统建立仿真模型 ,将仿真输出信息作为优化器的输入 ,对仿真输出进行分析与评价后 ,得出新的系统参数或决策变量再作为仿真模型的新输入 ,以上过程不断重复 ,直至满足一定的停止规则。这种思想实现了优化算法与仿真的外部集成 ,提高了对问题的建模能力和灵活性。 输入（决策变量） 输出（性能指标） 输出（优化解） 输入（优化参数） 图 4.1 4.2 算法优化 为了分析启发式算法的好坏 ,通过与最优解之间的平均误差和最大误差的比较 ,得到启发式算法的好坏。按启发式算法 1得到排序的相对误差 Z1 = Cj (ASPT1) CjCj 平均误差 W1 = Z110 仿真模型 数据转换 优化算法 数据转换 nts西北工业大学明德学院本科毕业设计论文 28 其中 ,10 表示对每个问题取 10 组实例进行计算 ,最大误差 R1 为相对误差中最大的误差 ;按启发式算法 2得到排序的相对误差 Z2 = Cj (ASPT2)CjCj 平均误差 W2 = Z210 最大误差 R2为相对误差中最大的误差 ;按启发式算法 3得到排序的相对误差 Z1+2 = Cj (ASPT1+2) CjCj 平均误差 W1+2 = Z1+210 最大误差 R1+2为相对误差中最大的误差。 通过 C#语言编程 ,选取 4 个不同工件数 n=8,10,12,14,在不同的工件数中随机选取 10 组数 ,其中 ,工件的加工时间 pij在 1,100随机产生 ,每组数按启发式算法 1 3,3 种排列进行排序 ,并加入指数学习效应 =0.1,0.5,0.8,分别按 3 种启发式算法求出总完工时间 ,并把 10组数据 根据以上公式求 取平均值 ,得到启发式算法与最优解的平均误差和最大误差 。从计算的结果我们是可以得到一个相应的结论的，即 3个启发式算法之间没有明显的好坏 ,对于参数 =0.1,所求之解更加接近最优解 ,且 大部分 会 产生最优的 排序。 nts西北工业大学明德学院本科毕业设计论文 29 第四章 总结与展望 5.1 论文总结 2014 年 3月，我开始了我的毕业论文工作，时至今日，论文基本完成。从最初的茫然，到慢慢的进入状态，再到对思路逐渐的清晰，整个写作过程难以用语言来表达。历经了几个月的奋战，紧张而又充实的毕业设计终于落下了帷幕。回想这段日子的经历和感受，我感慨万千，在这次毕业设计的过程中，我拥有了无数难忘的回忆和收获。 在 整个设计过程 中遇到困难我就及时和导师联系，并和同学互相交流，请教专业课老师。在大家的帮助下，困难一个一个解决掉，论文也慢慢成型。 当我终于完成了所有打字、 编算法 、排版、校对 等 任务后整个人都很累，但同时看着电脑荧屏上的毕业设计稿件我的心里是甜的，我觉得这一切都值了。这次毕业论文的制作过程是我的一次再学习，再提高的过程。在论文中我充分地运用了大学期间所学到的知识。 我不会忘记这难忘的几个月的时间。毕业论文的制作给了我难忘的回忆。在整个过程中，我学到了新知识，增长了见识。在今后的日子里，我仍然要不断地充实自己，争取在所学领域有所作为。 脚踏实地，认真严谨，实事求是的学习态度，不怕困难、坚持不懈、吃苦耐劳的精神是我在这次设计中最大的收益。我想这是一次意志的磨练，是对我实际能力的一次 提升，也会对我未来的学习和工作有很大的帮助。 通过这一学期的毕业设计
- 温馨提示:
1: 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
2: 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
3.本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
人人文库网所有资源均是用户自行上传分享，仅供网友学习交流，未经上传用户书面授权，请勿作他用。
|
2:不支持迅雷下载,请使用浏览器下载
3:不支持QQ浏览器下载,请用其他浏览器
4:下载后的文档和图纸-无水印
5:文档经过压缩，下载后原文更清晰
|
川公网安备: 51019002004831号