具有学习效应的总完工时间流水线排序问题与仿真论文

西北工业大学明德学院本科毕业设计论文本科毕业设计论文题 目 具有学习效应的总完工时间流水线排序问题与仿真 专业名称 机械设计制造及其自动化 学生姓名 毕业时间 二一四年 七月 IV西北工业大学明德学院本科毕业设计论文设计论文毕业 任务书一、题目具有学习效应的总完工时间流水作业排序与仿真二、指导思想和目的要求（1）掌握运用所学理论知识分析解决工程实际问题的一般方法；（2）培养分析问题、解决问题和独立工作的能力；（3）通过毕业实习、毕业设计及毕业答辩全过程的训练，加强 老师与学生之间、学生与学生之间知识的相互交流，互相渗透，培养学术研讨的好学风；（4）要求同学们以满腔的热情、科学的态度，严谨的作风、高度的责任感从事毕业设计工作；不得敷衍了事、马马虎虎、得过且过；提倡周密思考、大胆创新，反对死搬硬套、墨守陈规；提倡共同研究，反对相互抄袭；（5）要求遵守学校的各项规章制度，确保毕业设计顺利地、高质量地完成。三、主要技术指标过去处理排序问题，大多采用两种方式:一种是根据以往经验，必要时作些修改，另一种是事物并不复杂，作些考虑即可奏效，排序问题不成其为一门学问。计算不周即可造成重大损失，依靠拍拍脑袋已不能解决问题;而且产品更新很快，新产品的生产、销售等没有成法可资参考，此时各种新的组合优化问题便涌现出来，排序问题便是其中之一。1. 翻译文献15002000字2. 讨论单机排序问题3. 利用仿真软件对单机排序问题做出算法并给出最优解4. 研究学习效应对机器的影响四、进度和要求（1）第1-3周收集资料，根据需要学习相关的硬软件；（2）第4周进行系统概要设计，提出设计的总体思想；（3）第5周，初步确定设计方案；（4）第6-12周，完成单机，针对设计中存在的缺点和不足，不断完善设计方案；（5）第13-14周，撰写并修改论文；（6）第15-16周，完成论文，准备答辩资料。五、主要参考书及参考资料自行确定本页不够可以续页 学生 张红伟 指导教师 王剑 系主任 摘 要排序问题的一大特点是:模型繁多，适用于某一模型的算法，只要将模型的条件稍加变化，该算法即不适用. 包括如何对各个部件进行分隔、布线和布局的问题”.排序论是国际上发展最迅速、研究最活跃、成果最丰硕、前景最诱人的学科领域之一特别引人注目的是:随着现代工业的发展，经典的排序模式已被突破，新的模式层出不穷，吸引了越来越多的理论工作者和实际工作者、可控排序、多目标排序、成组分批排序、同时加工排序、准时排序和窗时排序、资源受限排序、不同时开工排序、随机排序、模糊排序、应用排序等，就是其中发展最为迅速的一些新方向. 在我国，对排序问题的研究较晚，虽然早在20世纪50年代末，就有人注意到这一问题一问题的研究，并开始作一些宣传普及的工作;但由于众所周知的原因，对这，直至70年代中才开始，到80年代，对算法感兴趣的人越来越多。现研究工件具有学习效应的单台机器流水作业排序问题与仿真。工件的学习效应指工件的加工时间为所排位置的指数函数。目标函数为极小化总完工时间。给出该问题的数学规划模型。同时对大规模问题给出3个启发式算法,并给出计算结果。 ，关键词：排序，流水作业，学习效应，总完工时间 ABSTRACTScheduling 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 time西北工业大学明德学院本科毕业设计论文目 录第一章绪论71.1 流水作业排序问题71.2.1排序问题的分类111.3 排序问题的求解121.3.1可行排序和最优排序12第二章 具有学习效应的总完工时间流水线排序142.1 问题描述142.2 预备知识142.2.1学习效应的概念142.3 单机排序问题162.3.1 加权总完工时间问题162.4数学规划模型172.5启发式算法182.5.1 启发式算法1182.5.2 启发式算法2192.5.3 启发式算法3192.6 数值试验192.6.1基本假设192.6.2数据模拟20第三章 流水线作业排序模型仿真223.1仿真软件介绍223.2 Liken仿真软件算法介绍223.2.1 EDD算法规则223.2.2 加权最短作业时间法则（WSPT）223.2.3 SPT算法规则223.3 仿真243.3.1仿真前提条件243.3.2仿真计算24第四章 仿真分析与算法优化294.1 车间作业排序问题仿真优化系统的构建思想、方法与框架294.2 算法优化29第四章 总结与展望315.1 论文总结315.2后续与展望32致 谢33参考文献34毕业设计小结3534第一章 绪 论1.1 流水作业排序问题1.1.l引例排序(scheduling)问题产生的背景主要是机器制造，后来被广泛应用于计算机系统、运输调度、生产管理等领域.从普通的生产部门的计划安排、人员调度，学校课程表的制订，到宇宙飞船的复杂庞大的飞行计划，都要用到排序的理论和算法。在给出排序问题的一般定义之前，我们先看几个排序在实际领域中应用的例子。例1.1机械加工 一个机械加工车间要加工一批机器零件，每一个零件都具有相同的工序，即按相同的顺序在几个不同的机床上加工，但每个零件在每个机床上的加工时间可能不同.如何安排加工顺序才能以最短的时间加工完所有的零件，这是一个流水线排序问题。 例1.2进程调度 在计算机多道程序操作系统中，并发执行多个进程，在宏观上同时执行多个进程，在微观上在任何时刻CPU只能执行一个进程。进程的到达时间是不同的，怎样调度这些进程才能使CPU的利用率最高或进程的平均周转时间最短?这也是一个排序问题。另外，每个进程的到达时间和执行时间事先是不知道的，但随机到达时间和执行时间的分布、它们的数学期望、方差等是已知的，这时的目标是极小化平均周转时间的数学期望。排序问题中出现了随机变量称作随机排序问题。例1.3机场调度在一个飞机场，有几十个登机门，每天有几百架飞机降落和起飞。登机门的种类和大小是不同的，而班机的机型和大小也是不同的，一些登机门安放在能容纳大型飞机的地方，小登机门只能容纳小型飞机。飞机按时刻表降落和起飞，由于天气和机场的其他原因，时刻表也有很大的随机性。当飞机占有登机门时，到达的旅客下飞机，出发的旅客上飞机，飞机要接受诸如加油、维护和装卸行李等服务。如果飞机在下一个机场不能按时降落，此时为了节省燃料，飞机不能起飞，登机时间推迟，飞机需要占有一个登机门，而其他的飞机不能使用。机场的调度人员需要制订一个可行的方案，把登机门分配给降落的飞机，使机场的利用率最高或晚点起飞的飞机最少，这也是一个排序间题，在这里飞机被看成是被处理的任务，登机门当作处理机，机场的规定是约束条件。1.2 排序问题的定义排序(scheduling)问题是一类重要的组合最优化问题，它是利用一些处理机(processor)、机器(machine)或资源( resource )，最优地完成一批给定的任务(task)或作业(yob)。在执行这些任务或作业时需要满足某些限制条件，如任务的到达时间、完工的限定时间、任务的加工顺序、资源对加工时间的影响等.最优的完成指的是使目标函数达到最小，而目标函数通常是对加工时间的长短、处理机的利用率的描述。在排序问题中，处理机的数量和种类，任务或作业的顺序、到达时间、完工限制，资源的种类和性能等情况是错综复杂的，很难用精确的数学描述给出一般的排序定义。在本书中，我们用如下方式来描述排序问题: 给定n个任务的任务集 T = ,m个处理机的处理机集 P =, 和s种资源的资源集 R =,排序问题指的是在一定条件下，为了完成各项任务，把沙中的处理机和(如果有)中的资源分配给了中的任务，使目标函数达到最优。排序问题基本上是由处理机的数量、种类与环境，以及任务或作业的性质和目标函数所组成。处理机只有一个处理机的排序问题称为单(处理)机(single processor, single machine)排序问题，否则称为多(处理)机排序问题。在多处理机排序问题中，如果所有的处理机都具有相同的功能，称它们为同类机或平行机(parallel processors)。同类机按处理的速度又分为三种类型:如果所有的处理机都具有相同的速度，称之为同速机(identical processors );如果处理机的速度不同，但每个处理机的速度都是常数，不依赖被加工的任务，称它们为恒速机(uniform processors);如果处理机的速度依赖被加工的任务，它们被称为变速机(unrelated processors)。 多处理机的另一种情况是多类型机(dedicated processors)。多类型机指的是m个处理机具有不同的功能。在多处理机环境中，被加工的任务需要在不同的处理机上加工.在这种情况下，把任务(task )称为作业(job)。设有作业集 J=,每个作业,有，道工序(operation) ，.工序指的是作业在某处理机上被加工的这部分任务。如果每个作业需要在每个处理机上加工，即=m ,j二1，2，n.而且每个作业的工序也相同，即在处理机上加工的顺序相同，把这种多类机的环境称为同顺序作业或流水作业(flow shop)。 如果每个作业需要在每个处理机上加工，每个作业有自己的加工顺序，称之为异顺序作业(job shop)。 如果每个作业需要在每个处理机上加工，每个作业可按任意顺序加工，把它称为自由顺序作业或开放作业(open shop ) 。 在多处理机中，还有一种更复杂的情况，这就是柔性流水作业(flexible flow shop)，它是流水作业和平行机的推广。在柔性流水作业中，有，类处理机，第J类有个平行机，每个作业有s道工序，每道工序需要在每类平行机中的一个处理机上加工，且每个作业的加工顺序相同。 为方便起见，以后我们把同顺序作业、异顺序作业、开放作业、柔性流水作业通称为车间作业。处理机的各种类型和环境总结如下: 单处理机 同速机 同类机（平行机） 恒速机 自由顺序作业（开放作业） 柔性流水作业任务和作业排序问题中的约束条件，主要指的是任务或作业的性质以及它们在加工过程中的要求和限制。下边的数据描述了任务的一些性质(1)加工时间向量任务的加工时间向量是 =(,)其中是任务 在处理机，上所需要的加工时间，对同速机有=，i=1,2，m，对恒速机有,= /，i=1,2，,m。其中 是标准的加工时间(一般是速度最慢的处理机的加工时间)，是处理机的速度因子，在车间作业的排序问题中，作业的加工时间向量是 =(,)其中,是工序。在对应的处理机上的加工时间。(2)到达时间到达时间( arrival time)或准备时间(ready time) 是任务已经准备好可以被加工的时间如果所有的任务的准备时间相同，取=0 ;j=1,2, ,n。(3)工期和截止期限工期(due date)表示对任务限定的完工时间.如果不按期完工，应受到一定的惩罚。绝对不准许延误的工期称为截止期限(deadline) 。(4)优先因子优先因子玛是一个权，它表示任务相对于其他任务的重要程度.为了叙述方便起见，我们假设以上参数，和都是整数.实际上这等价于它们可以是任意的有理数。我们经常用向量和矩阵的列给出这些数据。例如用 r=(,) d=(,) w=(,)分别表示n个任务的到达时间、工期和优先因子。用 的第i行(, ,)表示n个任务在第i个处理机上的加工时间。任务被加工时的一个重要约束是可中断(preemptive)或不可中断(nonpreemptive).如果排序问题中，每一个任务在加工时的任一时刻都可暂停加工，加工该任务的处理机可去加工任何其他任务，以后可在任何时刻在任意处理机上重新继续加工，这种排序问题称之为可中断排序.任何任务都不允许中断的排序问题称为不可中断排序。加工任务时的另一个重要限制是任务之间的优先约束(precedence constraints)。任务之间的优先约束是任务集上的一个偏序关系。味着必须加工完才能开始加工。如果任务集T中至少有两个任务受到优先约束的限制，集T的任务称为相关的(dependent)，否则称为无关的(indepent)。1.2.1排序问题的分类在排序问题中，如果所有的数据在进行决策之前都是己知的，排序问题称为确定性排序(deterministic scheduling)问题。如果有的数据，例如加工时间、准备时间和工期等，在做决策时是未知的，它们是一些随机变量，但它们的分布是己知的，这样的排序问题称为随机排序(stochastic scheduling)问题。无论是确定性排序还是随机排序，我们都假设: (1)任务或作业和处理机都是有限的。 (2)在任一时刻，任何处理机只能加工一个任务或一道工序。 (3)极小化单一目标函数，在随机排序中，极小化目标函数的数学期望。处理机、任务或作业和目标函数三要素组成了排序问题。处理机的数量、类型和环境有近十种情况，任务或作业和资源的约束条件更是错综复杂，再加上度量不同指标的目标函数，形成了种类繁多的排序类型。我们用Graham等人首先使用的三元组来描述排序问题的类型，这样能大大简化排序问题的表示。1.3 排序问题的求解1.3.1可行排序和最优排序排序问题是一类组合最优化问题.由于排序问题中的处理机、任务或作业都是有限的，绝大部分排序问题是从有限个可行解中找出一个最优解，使目标函数达到极小。在排序问题中，把可行解称为可行排序(feasible schedule)，最优解称为最优排序(optimal schedule)。在排序问题中，一个可行排序是一个顺序(sequence)或排列(permutalion)，按照这个顺序，在给定的处理机上加工所有的任务或作业。例1.1给定排序问题1|，其中n=4, P=(3，2，5，i)，r=(0，1，0，0),是一个可行排序，对应的总加工时间是31,是一个最优排序，最优总加工时间是21。符号说明 第J个任务 T 一一任务集第j个作业J 一一作业集第J种资源R 一一资源集任务的加工时间P n个任务的加工时间向量 任务的随机加工时间任务在处理机上的加工时间任务在处理机上的随机加工时间任务或作业的到达时间rn个任务的到达时间向量任务或作业的工期或截止期限d - n个任务的工期向量任务的优先因子(权)Wn个任务的优先因子向量任务或作业的完工时间时间表长任务或作业的延误时间 任务或作业的误工时间对任务或作业误工的单位惩罚 m个同速机第二章 具有学习效应的总完工时间流水线排序2.1 问题描述具有学习效应的流水作业排序问题的一般描述如下:设有n个工件,依次在机器上加工。工件在2台机器和上加工,在每个机器上的加工顺序相同,工件在机器的工序记为,工序的正常加工时间为。设工序排在第r个位置的实际加工时间为。 = （21）式中:i=1,2, ,m; r,j=1,2,n; 为学习因子,且01;r表示工件实际加工时所排的位置。对于给定的排序,工序的完工时间记为,工序的完工时间称为工件的完工时间,记为即。对于2台机器上具有指数学习效应的最大完工时间的流水作业问题,用三参数表示法表示为 F2|=|对于经典流水作业问题F2是NP-难的,所以问题F2|=|也是NP-难的。2.2 预备知识2.2.1学习效应的概念在制造业系统中,排序问题是一类重要的问题,多年来人们一直致力于该问题的研究。在大多数排序问题中,工件的加工是一个独立的且与加工位置无关的常数。然而,在一些实际排序问题中,由于工人(机器)在长时间加工相同或类似的工件时,加工效率有可能逐渐提高,使后加工的工件的加工时间变小,这种现象被称为具有学习效应。学习曲线又叫经验曲线，是一种可以显示单位产品生产时间与所生产的产品总数之间的关系的曲线。学习曲线可以用于个人和组织。当人们重复同一过程工作中并从他们自己的作业经历中获得技能和提高效率，个人的学习能力将得到提高，即所谓的“熟能生巧”。组织的学习能力同样来源于实践，但也来源于管理、设备和产品设计等方面的变化。在组织学习中我们期望能够同时达到两种学习能力的提高，通常用一条学习曲线来描述两者相结合的结果。学习曲线基于以下三条假设：1、每次完成同一性质的工作后，下次完成该性质的工作或生产单位产品的时间将减少；2、单位产品生产时间将以一种递减的速率下降；3、单位产品生产时间的减少将遵循一个可预测的模式。学习曲线方程的一般形式是:Yx=K（n为X的指数）式中: X =单位数量 = 生产第X个产品所需的直接劳动小时数K = 生产第一个产品所需的直接劳动小时数n = lgb/lg X，其中b 为学习比例以上三条假设最初是从飞机制造过程中得到验证的，也就是学习曲线最先被应用在飞机制造业。在飞机制造过程中发现，每当产量翻倍，用于制造飞机的时间就会减少20%。也就是说，假设制造第一架飞机用时100000小时，那么当制造第二架的时候，用时就为80000小时，而第四架就会耗去64000小时，以此类推。换言之，制造第二架飞机所用时间是制造第一架飞机时间的80%，制造第四架飞机所用时间是制造第二架飞机时间的80%，当时的人们把这种关系称为学习曲线，80%叫做学习率。学习曲线理论有两种主要的模型：单位产品生产时间学习曲线和累计平均时间学习曲线。单位产品生产时间学习曲线表示的是生产第N个单位的产品耗用了多少时间，而累计平均时间学习曲线表示的是生产N个单位的产品总共耗用了多少时间不同的人或者组织或者工作，由于环境、方法、素质等因素的差异，学习率会有不同。一般来说，对于简单的任务，倾向于采用95%的学习率，中等复杂的任务采用80%-90%的学习率，高复杂程度的任务倾向于使用70%-80%的学习率。2.3 单机排序问题单机排序问题是最简单的一类排序问题，同时也是最重要的排序问题之一首先单机排序问题比较容易求出解决方法，这些方法对于研究比较复杂的排序问题具有指导作用，可以为处理复杂排序问题提供近似算法;其次，单机排序问题大量存在于现实生活中，具有广泛的实际背景，许多实际问题都可以归结为单机排序问题。因此，单机排序问题对于有效地利用资源，提高生产效率，具有十分重要的指导意义。2.3.1 加权总完工时间问题单机排序问题的一个重要目标函数是加权平均流时间。由于极小化加权平均流时间等价于极小化加权总完工时间，因此下面仅以加权总完工时间为目标函数讨论问题.首先讨论问题 1 (21)其中是任务的完工时间，是赋予任务的权，它表示的重要程度.对于问题(2.3.1)，应用加权最短加工时间优先(weighted shortest processing time first，简记WSPT)规则可以得到最优排序。按照这一规则，任务按/非增的顺序进行排序。对于相等的特殊情况，加权最短加工时间优先规则化为最短加工时间优先(shortest processing time first，简记SPT)规则。 定理2.1对于问题(2.1),WSPT规则得到的是最优排序。 证明假定某最优排序 违反了WSPT规则，则在此排序中，至少有两个相邻任务与 (在前)，使/()与是最优排序矛盾.定理证毕。2.4数学规划模型下面给出问题F2|=|的数学规划模型。目标函数:约束条件: i=1,2; r=1,2，n , r1,2, ,n （25） ， r1,2, ,n (26) (27) r1,2, ,n；0式中:j为工件数,j=1,2,n;i为机器数，i=1,2；为在机器i上排在第r个位置工件的实际加工时间,i=1,2；r=1,2,n; 为在第二台机器上第r个工件的开始时间与第r-1个工件的完工时间之间的空闲时间，r=1,2，n；为第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个位置= 0 否则j,r=1,2,n式(1)中的与式(4)中的表达的意思不同,式(1)中的表示在机器上的工件排在第r个位置的实际加工时间;而式(4)中的表达的是在机器上排在第r个位置的实际加工时间。2.5启发式算法前面已把求F2|=|的最优解问题转化为求解相应的数学规划模型,数学规划问题通过数学软件Lingo或Lindo进行计算,得到最优解,但是,数学规划模型只能解决小规模问题,大规模问题运行的时间过长,很难求到最优解。引理1对于问题1 |=|,SPT(把工件按非减顺序排列)规则产生最优排序。受单机排序问题的启发(引理1),可以给出把工件按照在第1台机器上的加工时间的SPT规则排序或把工件按照在第1和第2台机器上的加工时间和的SPT规则排序作为启发式算法。为了进一步改进启发式算法,可以用交换工件位置的方法,得到改进解。下面给出这3个算法的详细步骤:2.5.1 启发式算法1(1)把工件按 (表示工件在第1台机器上的加工时间)非减(SPT规则)顺序排列,即把工件按 排列得到的排序;(2)设由步骤(1)得到的排序为 ;(3)置k=1;(4)置i=k+1;(5)通过交换第k和第i个工件得到新的排序。如果排序的目标函数值小于排序的目标函数值,则用代替;(6)如果in,则置i=i+1,转(5);(7)如果kn-1,则置k=k+1,转(4);否则,停止。2.5.2 启发式算法2(1)把工件按 (表示工件在第2台机器上的加工时间)非减(SPT规则)顺序排列,即 排列得到的排序;(2)设由步骤(1)得到的排序为;(3)置k=1;(4)置i=k+1;(5)通过交换第k和第i个工件得到新的排序。如果排序的目标函数值小于排序的目标函数值,则用代替;(6)如果in,则置i=i+1,转(5);(7)如果kn-1,则置k=k+1,转(4);否则,停止。2.5.3 启发式算法3(1)把工件按+非减(SPT规则)顺序规列,即+ +排列得到的排序;(2)设由步骤(1)得到的排序为;(3)置k=1;(4)置i=k+1;(5)通过交换第k和第i个工件得到新的排序。如果排序的目标函数值小于排序的目标函数值,则用代替;(6)如果in,则置i=i+1,转(5);(7)如果kn-1,则置k=k+1,转(4),否则,停止。2.6 数值试验2.6.1基本假设（1）工件数为5个，机器数为2台（2）假设第1台机器上第r个工件的完工时间和它在第2台机器上的开始时间之差皆为5min，即。（3）假设5个不同工件在第一台机器每一个批次的实际加工时间分别为4,6,7,5，9。在第二台机器实际加工时间分别为7,11,10,9,6。另外，每种工件各有5个批次。（4）假设学习因子=0.9（5）假设第二台机器上第r个工件的开始时间与第r-1个工件的完工时间之间的空闲时间为0，即。2.6.2数据模拟对于问题F2|=|，令 表示得到的最优解,令表示按启发式算法1得到的排序, ()表示用启发式算法1得到的总完工时间。令表示按启发式算法2得到的排序, ()表示用启发式算法2的总完工时间。令表示按启发式算法3得到的排序,Cj()表示用启发式算法3排序得到的总完工时间。由以上假设我们可以得到|=| 代入数据后可知：目标函数： 根据2.4数学规划模型我们可得出：即第一种工件的五个批次的完工时间分别为4,3.6,3.24,2.92,2.62min。那么第一种工件五个批次的总完工时间为18.74min。即 。 以此类推可知， r1,2, ,5 则目标函数 第三章 流水线作业排序模型仿真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) 法则排序可使得平均流程时间最小化，也就是。范例3.1给予一组工作集如下表所示，目标为最小化平均流程时间 表 3.1工作 i 作业时间 ti 142837435106127685 依SPT派工法则排序，顺序为4-1-8-7-3-2-5-6。其流程时间计算如下表 表 3.2工作 i 流程時間 ti 4313+483+4+573+4+5+633+4+5+6+723+4+5+6+7+853+4+5+6+7+8+1063+4+5+6+7+8+10+12 所以平均流程时间为由以上可知工作流程时间的计算方式为除了最小化平均流程时间以外，在单机排序问题中SPT法则亦可以最小化平均延误时间、最小化平均等候时间。3.3 仿真3.3.1仿真前提条件（1）工件数为5个，机器数为2台（2）假设5个不同工件在第一台机器每一个批次的实际加工时间分别为4,6,7,5，9。在第二台机器实际加工时间分别为7,11,10,9,6。另外，每种工件各有5个批次。（3）假设学习因子=0.9（4）假设第1台机器上第r个工件的完工时间和它在第2台机器上的开始时间之差皆为5min，即。 （5）假设5个作业的优先级都为1。3.3.2仿真计算利用车间排序软件Lekin，设置参数如下图：（1）如图3.1与图3.2，进入lekin软件后，点击如图中的Flow。并设置两台机器，五个作业，点击OK。 图 3.1 图 3.2（2）图3.3与图3.4为对机器和进行参数设置。 图 3.3 图 3.4（3）图3.5与图3.6为对工作1进行的各种参数设置。 图 3.5 图 3.6（4）图3.7与图3.8为对工作2进行的各种参数设置。 图 3.7 图 3.8（5）图3.9与图3.10为对工作3进行的各种参数设置。 图 3.9 图 3.10（6）图3.11与图3.12为对工作4进行的各种参数设置。 图 3.11 图 3.12（7）图3.13与图3.14为对工作5进行的各种参数设置。 图 3.13 图 3.14（8）下图为两台机床，五个作业由的排序图。 图 3.15（9）以下为经过Lekin软件SPT排序所得结果。 图 3.16 图 3.17 图 3.18从图3.17，我们可以看出，各自对应黄色，浅蓝，紫色，绿色，灰色。由此与图3.16做对比，可知由最短作业时间法则(SPT)所得的排序为。 第四章 仿真分析与算法优化4.1 车间作业排序问题仿真优化系统的构建思想、方法与框架 传统的仿真优化集成思想如图4.1所示。对系统建立仿真模型,将仿真输出信息作为优化器的输入,对仿真输出进行分析与评价后,得出新的系统参数或决策变量再作为仿真模型的新输入,以上过程不断重复,直至满足一定的停止规则。这种思想实现了优化算法与仿真的外部集成,提高了对问题的建模能力和灵活性。仿真模型 输入（决策变量） 输出（性能指标）数据转换数据转换优化算法 输出（优化解） 输入（优化参数） 图 4.14.2 算法优化为了分析启发式算法的好坏,通过与最优解之间的平均误差和最大误差的比较,得到启发式算法的好坏。按启发式算法1得到排序的相对误差 平均误差 其中,10表示对每个问题取10组实例进行计算,最大误差R1为相对误差中最大的误差;按启发式算法2得到排序的相对误差平均误差最大误差为相对误差中最大的误差;按启发式算法3得到排序的相对误差平均误差最大误差为相对误差中最大的误差。 通过C#语言编程,选取4个不同工件数n=8,10,12,14,在不同的工件数中随机选取10组数,其中,工件的加工时间在1,100随机产生,每组数按启发式算法13,3种排列进行排序,并加入指数学习效应=0.1,0.5,0.8,分别按3种启发式算法求出总完工时间,并把10组数据根据以上公式求取平均值,得到启发式算法与最优解的平均误差和最大误差。从计算的结果我们是可以得到一个相应的结论的，即3个启发式算法之间没有明显的好坏,对于参数=0.1,所求之解更加接近最优解,且大部分会产生最优的排序。 第四章 总结与展望5.1 论文总结2014年3月，我开始了我的毕业论文工作，时至今日，论文基本完成。从最初的茫然，到慢慢的进入状态，再到对思路逐渐的清晰，整个写作过程难以用语言来表达。历经了几个月的奋战，紧张而又充实的毕业设计终于落下了帷幕。回想这段日子的经历和感受，我感慨万千，在这次毕业设计的过程中，我拥有了无数难忘的回忆和收获。 在整个设计过程中遇到困难我就及时和导师联系，并和同学互相交流，请教专业课老师。在大家的帮助下，困难一个一个解决掉，论文也慢慢成型。当我终于完成了所有打字、编算法、排版、校对等任务后整个人都很累，但同时看着电脑荧屏上的毕业设计稿件我的心里是甜的，我觉得这一切都值了。这次毕业论文的制作过程是我的一次再学习，再提高的过程。在论文中我充分地运用了大学期间所学到的知识。我不会忘记这难忘的几个月的时间。毕业论文的制作给了我难忘的回忆。在整个过程中，我学到了新知识，增长了见识。在今后的日子里，我仍然要不断地充实自己，争取在所学领域有所作为。脚踏实地，认真严谨，实事求是的学习态度，不怕困难、坚持不懈、吃苦耐劳的精神是我在这次设计中最大的收益。我想这是一次意志的磨练，是对我实际能力的一次提升，也会对我未来的学习和工作有很大的帮助。通过这一学期的毕业设计，我对流水线排序问题有了一个基本的了解和掌握，但是每一种排序算法根据其实际生产线的要求却又是各有不同的，所以我在今后的工作和学习中将会继续努力学习，了解与应用各种流水线排序算法仿真软件，结合自己大学以来学习的各种加工软件，我相信在以后的工作中一定能有很大的帮助。5.2后续与展望此次毕业设计在此就将有一个阶段性的成果，但是在此过程中，自己还是有很多的不足之处，专业知识有很强烈的匮乏感，这都源于知识面不够广阔，未能深刻钻研专业相关的知识，针对这次的毕业设计，我认为还有必要进一步进行完善工作。 流水线排序软件如Lekin、Arena等是一款很好的流水线排序软件，虽然在毕业设计阶段对此软件有所学习，但我感觉操作还是生疏，需要投入更多的精力在此项学习。 在实际生产中，排序问题影响因素众多我们能想到的如各种机器故障，所用机床的实际效能，车间流水线加工的学习效应，工件的特殊性等等都可使排序问题变得复杂，我们应尽可能地减少或避免它们。另外，因时间的关系，我对很多参数了解很肤浅，排序算法软件中的参数较多，尤其一些功用繁多的算法软件，这些参数的意义都非常重要，应在今后的工作中重点掌握。致 谢 在此论文撰写过程中，要特别感谢我的导师王剑老师，没有她的帮助也就没有今天的这篇论文。求学历程是艰苦的，但是有时快乐的。在这个过程中，王老师一直严格要求我，督促着我们，针对同学们提出的一些问题，总能够提出针对性的见解，同时她更注重对我们的自学能力的培养。这一切都使我学到了很多知识，培养了我们独立做研究的能力。同时也很感谢我们设计小组的成员们，在他们的热心帮助和鼓励下使我顺利的完成了这篇论文。在毕业设计即将完成之际，大学的学习生活也已经接近尾声，在此，我对帮助过我的老师和同学们表达由衷的谢意，感谢大家四年以来对我的帮助与照顾！同时，我还要感谢我所在的大学西北工业大学明德学院，是她为我提供了舒适的生活条件及良好的学习环境。本文参考了大量的文献资料，在此，向学术界的前辈们致敬！ 参考文献1Badiru A B.Computational survey of univariate and multivariate learning curve modelsJ.IEEE transactions on Engineering Management 1992;39(2):176-188.2BiskupD.Single-machine scheduling with learning considerations J.European Journal of Operational Research 1999;115(1):173-178.3Cheng T C E,Wang G.Single machine scheduling with learning effect considerationsJ.Annals of Operations Research 2000;98(1-4):273-290.4Mosheiov G.Scheduling problems with a learning effectJ.European Journal of Operational Research 2001;132(3):687-693.5Mosheiov G.Parallel machine scheduling with a learning effectJ.Journal of the Operational Research Society,2001,52(10):1165-1169.6Mosheiov G,Sidney J B.Scheduling with general job-dependent learning curvesJ.European Journal of Operational Research,2003,147:665-670.7Mosheiov G,Sidney J B.Note on scheduling with general learning curves to minimize the number of tardy jobs.Journal of the Operational Research Society,2005,56:110-112.8Bachman A,Janiak A.Scheduling jobs with position dependent processing timesJ.Journal of the Operational Research Society,2004,55:257-264.9Wang J B.Flow shop scheduling jobs with position-dependent processing timesJ.Journal of Applied Mathematics and Computing,2005,18(1-2):383-391.10Wang J B,Xia Z Q.Flow shop scheduling with a learning effectJ.Journal of the Operational Research Society,2005,56(11):1325-1330.11Wang J B,Wang M Z,Xia Z Q.Single machine scheduling problems with a general learning effect J.Journal of Ma