带有交货期和加工时间可控的单机排序问题毕业设计论文
带有交货期和加工时间可控的单机排序问题毕业设计论文,带有,交货期,加工,时间,可控,单机,排序,问题,毕业设计,论文
本科毕业设计论文题 目 带有交货期和加工时间可控的单机排序问题 专业名称 机械设计制造及其自动化 学生姓名指导教师毕业时间毕业设计论文任务计划书一、题目 带有交货期和加工时间可控的单机排序问题二、指导思想和目的要求 毕业设计(论文)是培养学生自学能力、综合应用能力、独立工作能力的重要教学实践环节。 在毕业设计中,学生应独立承担一部分比较完整的工程技术设计任务。要求学生发挥主观能动性,积极性和创造性,在毕业设计中着重培养独立工作能力和分析解决问题的能力,严谨踏实的工作作风,理论联系实际,以严谨认真的科学态度,进行有创造性的工作,认真、按时完成任务。三、主要技术指标1、优化数学模型;2、算法的优化程序;3、仿真程序;4、仿真验证结果;5、设计说明书一份;四、进度和要求第01周-第02周: 撰写毕业设计开题报告;第03周-第04周: 文献翻译;第05周-第06周: 分析并确定优化的目标函数,根据约束条件建立优化数学模型 ;第07周-第09周: 编制算法的优化程序;第10周-第11周:学习使用软件,设计相应的调度方案;第12周-第13周: 搭建仿真程序,进行仿真、验证;第14周-第16周: 撰写毕业设计论文,论文答辩。五、主要参考书及参考资料1范雁鹏、赵传立.带有交货期和加工时间可控的单机排序问题.沈阳师范大学 数学与系统科学学院,沈阳110034.2 何燕.基于遗传算法的车间调度优化及其仿真.武汉理工大学.20063 欧阳珍.基于遗传算法的车间调度研究与应用.浙江大学.2004.4何少龙.具有安装时间和变量加工时间的单机排序问题.2011.5 潘全科.智能制造系统多目标车间调度研究.南京航空航天大学.2003.6Michael Pinedo(美).调度:原理、算法和系统(第二版).清华大学出版社.7 薛家兵、鄂明成.基于Flexsim仿真的FMS车间级控制开发系统.北京交通大学.机械与电子控制工程学院.北京.100044.2007.8唐恒永.赵传立.排序引论M.北京:科学出版社.9Mor B,Mosheiov G.Scheduling a maintenance activity and due-window assignment based on commom flow allowanceJ.International Jouranl of Production Economics.2012.135(1):220-230.10 Hsu C J,Yang S J,Yang D L. Two due date assignment problems with position- dependent processing time on a single-machineJ. Computers & Industrial Engineering,2011,60(4):796800. 11 Cheng T C E, Oguz C,Qi X D. Due-date assignment for scheduling on a single machine with compressible processing timeJ.International Journal of Production Economics.1996,43(2):107-113.12 Shabtay D, Steiner G. The single-machine earliness-tardiness scheduling problem with due date assignment and resource-dependent processing timesJ. Annals of Operations Research,2008,159(1):25-40.学生 郑新宇 指导教师 王剑 摘要 排序问题是一类重要的组合最优化问题。排序问题普遍应用于管理等学科领域,是组合最优化的一类重要问题。调度的任务是根据生产目标和约束,为每个加工对象确定具体的加工路线、时间、机器和操作等。优良的调度策略对于提高生产系统的最优性、提高经济效益都有着极大的作用。但是由于资源约束和工艺约束的并存,迄今计算复杂性理论表明,多数调度问题属于NP一hard(Nondeterministiepolynomial一Hard,非确定性多项式)难问题,目标解的搜索涉及解空间的组合爆炸。排序算法的竞争比分析是排序问题对算法风险的一种评估和保障,具有重要的理论意义和实用价值。 本文讨论了带有交货期和工件的加工时间可控的单机排序问题本文首先根据最优排序的性质确定了最优资源的分配方法并将问题转化为指派问题通过构造多项式时间算法确定最优排序#然后本文将学习效应与加工时间可控问题结合分别讨论了加工时间是线性资源函数和凸资源函数两种情况证明了该类问题是多项式时间可解的最后讨论了一种特殊情况学习因子是常数加工时间是凸资源函数给出了复杂性为O(nlogn)的算法通过运行此算法确定最优资源分配量和工件的最优排序。关键词:排序单台机器,交货期,指派加工时间可控,资源分配. ABSTARCTScheduling 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.摘 要4ABSTRACT.5第一章 绪论.81.1 课题研究的背景和意义.81.2课题研究的目的意义和主要内容.9 1.2.1 排序问题的简述.9 1.2.2 排序问题的求解.10 1.2.3 算法复杂性的简介.101.3 本章小结.11第二章 带有交货期和加工时间可控的单机排序问题.122.1 单机排序.12 2.1.1 符号说明 .12 2.1.2 常用排序方法.132.2带有交货期和加工时间可控的单机排序问题.14 2.2.1问题描述.14 2.2.2资源约束.16 2.2.3模型推广.192.3应用举例及计算结果.232.4本章小结.25第三章 仿真与分析.25 3.1车间调度仿真.25 3.1.1 车间调度问题的描述.25 3.1.2 车间调度问题的特点.253.2仿真调度的原理和特点.26 3.2.1 仿真调度的原理.26 3.2.2 仿真调度的特点.263.3 仿真的基本方法.27 3.3.1 仿真的三种方法.27 3.3.2 仿真在调度中的作用.273.3.3 车间生产仿真调度业务流程.283.4 实例仿真.293.6 本章小结.41第四章 总结与展望.42参 考 文 献.44毕业设计小结.45致 谢.46 第一章 绪论1.1 课题研究的背景和意义近年来带有可控加工时间的排序问题受到越来越多的关注。加工时间可控是指工件的实际加工时间是一个依赖资源量的函数。关于带有可控加工时间的单机排序问题最早是由Viction提出的。Cheng等研究了带有工期和可控加工时间的单机排序问题,分别讨论了在2种工期分派方法下极小化总提前时间总延误时间和资源消耗的总费用问题。王方等讨论了具有学习效应的工期指派和可控加工时间的单机排序问题目标是确定工件最优的加工顺序)最优工期和资源分配量对于2种不同资源消耗与3种不同的工期分派方法的每一种组合,均给出了多项式时间算法。Chio等研究了带有可控释放时间和可控加工时间的单机排序问题,Shabtay和Steiner对于可控加工时间的排序问题做了详细的综述。在交货期问题中若工件在交货期中完工则不产生惩罚费用若工件在交货期之前或之后完工则会产生提前或延误的费用。Liman等研究了带有公共交货期且交货期的开始时间和大小都是待确定的单机排序问题郭玲等考虑了将加工时间可控与交货期结合在一起的模型讨论了带有公共交货期和可控加工时间的单机排序问题$目标是极小化总完工时间、提前时间、延误时间、交货期的结束时间和资源分配的总费用证明了这个问题是多项式时间可解的。Wan研究了带有大小固定的交货期和可控加工时间的单机排序问题。Mor和Mosheiov讨论了每个工件都有一个待定的交货期且交货期大小相同带有维修活动的单机排序问题目标函数是极小化包括总提前、总延误、交货期的开始时间和交货期的大小的总费用。此外,Mosheiov和Sarig对于带有交货期的排序问题也进行了深入研究。 本文考虑文献的排序模型将加工时间可控与每个工件均有一个待定交货期的问题结合构成一个新的模型给出了一些最优解的性质并将问题最终转化成指派问题证明了该类问题是多项式时间可解的。1.2课题研究的目的意义和主要内容 排序又称调度,作为运筹学的一个分支,是一门应用性很强的学科,有着其深刻的实际背景和广泛的应用空间。在现代企业竞争中,准时生产已经成为一种重要的竞争策略。根据准时生产原则,工件的完工时间要尽量地靠近某一时刻(时间段)。如果工件在该时刻(时间段内)完工,就不会产生惩罚;如果工件在该时刻(时间段)之前或之后完工,就会产生提前或者延误的惩罚,这就是工期问题(工期窗口问题)。同时为提高机器的生产效率,可以考虑在机器上执行维修。本文主要讨论的是带有交货期和加工时间可控的单机排序问题,问题如下:首先,第一章介绍有关排序问题的预备知识、相关问题的研究现状。第二章中,主要讨论了带有交货期和工件的加工时间可控的单机排序问题。其中,工件的加工时间是其资源分配的线性非增函数,并且分配资源会产生费用,目标函数是极小化总完工时间、提前时间、延误时间、工期窗口的结束时间以及资源分配的总费用。我们证明了该问题可以转化为指派问题,即该问题是多项式时间可解的。第三章讨论带有交货期和加工时间可控的单机排序问题的仿真。主要讨论使用软件进行单机排序问题仿真的结果。工件的实际加工时间是关于工件的开工时间、工件的位置以及资源分配的函数。目标给出了最优排序的一些性质及最优资源分配的求解方法、多项式算法,证明了这些问题在多项式时间内可以求得最优解。最后,对本文的主要结果进行总结,并提出将来的研究方向。只有一台处理机作业的排序问题我们称之为单处理机(singleprOCessor)排序问题,又称单机排序间题,否则称为多处理机问题。在多处理机排序问题中,如果所有的处理机都具有相同的功能,称它们为平行机(parallelproCessors)。平行机按处理的速度又可以分为三种类型:同型机(identicalprocessor)、同类机(uniformproeessors)和不相关机(unrelatedproeessors)。在下面文章中主要涉及的是单机排序问题。1.2.1 排序问题的简述排序(scheduling)问题是一类重要的组合优化问题,它产生的背景主要是机器制造,后来在管理科学、计算机控制、硬件设计、生产调度和工程技术等很多领域应用非常广泛。排序问题可描述为利用一些处理机(processor)、机器(maehine)或资源(resouree)最优的完成一批给定的任务(task)或工件(job)。最优的完成指的是使目标函数达到最小,而目标函数通常是对工件加工时间的长短、机器的利用率等的描述。现实生活中的许多问题都可以纳入这种模型之中。在理论上,排序问题又与算法设计和计算复杂性的理论密切相关,引起了国内外许多专家学者的关注,得以迅速发展。排序问题基本上是由处理机的数量、种类与环境,以及任务或作业的性质和目标函数所组成。对于排序问题的分类,目前国际上通用的分类方法是Graham等人首先使用的三参数表示法:、,这里表示机器情况,即机器的数量,类型和环境。表示工件的情况,即工件的特征,加工要求和限制,对加工的影响等约束条件。表示目标函数。1.2.2 排序问题的求解排序间题是一类重要的组合最优化问题,因为排序问题中所涉及的机器、工件都是有限的,绝大多数的排序问题是从有限个可行解中找出一个最优解,使得目标函数达到极小。在排序问题中我们称可行解为可行排序,称最优解称最优排序。对于问题的每一个实例,其可行解的个数是有限的,因而我们可以用枚举的方法求得最优解。然而一般情况下这种方法是没有现实意义的,因为有时问题可行解的数目非常巨大,尽管我们用最先进的计算机,所花费的时间也是不能接受的。1.2.3 算法复杂性的简介在算法复杂性理论中,“问题”指对一类问题总的描述。“例子”是一个给定了一组数据的具体问题。对于某个问题,如果存在一个算法可以解决该问题的任何一个例子,则我们把这个问题称为可计算的。衡量一个算法的好坏,我们主要看占用储存的大小和所用时间的多少。前者称为空间复杂性,后者称为计算复杂性,在组合最优化中,算法复杂性指的是算法的时间复杂性。1.3本章小结排序问题是组合最优化学科的重要组成部分之一。一个医院门诊,大家是按照时间先来后到排序,还是按照病情轻重缓急排序;一个大型工程,各种机械设备是按照机器运行成本排序,还是按进度需要排序;一个工件加工车间,工件加工是按照资源利用率排序,还是按照完工期限排序,这些都要涉及排序问题。它是工业生产和日常生活。虽然排序学科的研究在20世纪50年代开始形成的,但是在近60年来得到了广泛而深入的研究,现在已成为运筹学中柑当有活力的一支。作为一类重要的组合优化问题,排序问题得到了越来越广泛的关注与研究,并且得到了重要的成果与应用。单机排序问题是最简单的一类排序问题,同时也是最重要的排序问题之一。单机排序问题大量存在于现实生活中,有着广泛的实际背景,而且比较容易求解,能够为更复杂的排序问题提供指导。排序问题普遍应用于生产管理、运输调度、计算机系统等领域,引起许多专家学者的广泛关注,并以实际生产活动为基础进行理论研究。经典排序问题的首篇文章是 1954 年Johnson发表的一篇重要论文。虽然我国对于排序问题的研究起步比较晚,始于上世纪六十年代,但是从上世纪九十年代起国内的学者们对排序问题的研究已呈现出新兴景象,排序问题的研究成果亦如雨后春笋。排序问题是组合最优化这门学科的一个重要组成部分,有着重要理论意义和广泛实际背景。排序问题产生的背景最初是机械制造,后来被生产管理、计算机系统和运输调度等领域广泛应用。如今生产计划调度,信息处理,公用事业管理等许多方面都要用到排序的理论和方法,同时排序问题与理论计算机科学、离散数学等学科都存在着紧密的联系。由于本人的水平有限,加之时间比较仓促,文中肯定会有很多错误和不妥之处,恳请各位老师批评指正。 第二章 带有交货期和加工时间可控的单机排序问题2.1 单机排序 排序问题,又称为调度问题,其产生的背景是机器制造。概括地说,单机排序是利用一台机器,在执行某些任务时,在某些限制条件下(如工件的到达时间、完工截止时间、优先约束、资源约束、机器对加工时间的影响等),寻找最优加工方式使某个或某些目标函数达到最优。目标函数通常是对加工时间的长短、处理机的利用率等的描述。它是“投入最少,产出最优”的一种系统优化过程。由于排序问题最早是在机器制造领域中提出来的,因而排序问题各要素的描述沿用了机器制造中的术语。机器(machine)、工件(job)和目标函数(objective function)是各种排序问题的三要素。 现给出单机排序的一般描述。设有n个工件J1,J2,Jn,工件Jj的权为uj,工件Jj的工期为dj。若工件Jj排在第r个位置加工,则其加工时间为,j=1,2,n。其中pJ为工件Jj的正常计算共时间,其单机排序问题可记为。2.1.1符号说明由于排序问题中机器的数量和类型,工件的准备时间、加工位置、完工要求、资源数量等情况错综复杂,因此为简化问题描述和方便各位老师批评,对本文常用符号作如下说明:J1,J2,Jn表示n个待加工的工件; pj(或pjr)(processing time)表示Jj(排在第r个位置上)的实际加工时间;表示工件Jj的正常加工时间;uj表示分配给Jj的资源量;表示分配给工件Jj的资源量上界,;wj表示工件Jj的权重;Cj(completion time)表示工件Jj的完工时间; dj(due time)表示工件Jj的工期,如果djCj表示工件提前完成,如果djCj表示工件延误完工。表示工件Jj的提前时间;表示工件Jj的延误时间;由于排序问题的定义可知,排序问题由排序问题的定义可知,排序问题是由机器的类型和数量、工件的加工要求和性质以及目标函数度量指标组成的,也就是说,机器、工件和目标函数是构成排序问题的三大要素。目前,排序问题中常见的三大要素可作如下总结: 1、机器机器又称为处理机,本文只讨论单机。单机(single machine)是指排序问题中只有一台机器。 2、工件工件又称为作业或任务,排序问题中的约束条件指的是工件的性质及其加工时的要求和限制。常见的约束条件主要有以下几种。(1) 加工时间工件的加工时间pj(或pjr)表示工件Jj(排在第r个位置上)的实际加工时间;(2) 到达时间到达时间(arrival time)又称准备时间(ready time)或释放时间间(realease time)是指工件Jj可以开始加工的时间,通常用rj表示。(3)工期 工期dj表示对工件Jj的完工时间的要求和限制,一般要求工件按时间完工如果不能按时完工就会产生费用。 3、目标函数排序问题的目标函数是一维实数,是用来衡量机器利用效率、加工时间大小的一个标量。2.1.2常用的排序方法 一插入排序 插入排序的基本思想是每步将一个待排序的纪录按其排序码值的大小,插到前面已经排好的文件中的合适位置,直到全部插入完为止。插入排序方法主要有直接插入排序和希尔排序。 二选择排序 选择排序的基本思想是从每步待排序的纪录中选出排序码最小的纪录,顺序存放在已排序的纪录序列的后面,直到全部排完。选择排序中主要使用是直接选择和堆选择。 三交换排序 交换排序的基本思想是:两两比较待排序纪录的排序码,并排序不满足顺序要求的那些偶对,直到满足条件为止。交换排序的主要方法有冒泡排序和快速排序。2.2带有交货期和加工时间可控的单机排序问题现在我们讨论带有两种约束条件的单机排序问题,(1)带有交货期;(2)加工时间可控。近年来,有关交货期的排序问题已被广泛关注,交货期是指:若某个工件在交货期窗口内完工,则不产生惩罚费用,但是如果工件在窗口之前或之后完工则会产生提前或延误的费用。在许多交货期窗口问题中,窗口的开始时间和结束时间都是决策变量,Liman等提出带有交货期窗口的单机排序问题,窗口的开始时间和窗口的大小都是待定的。目标函数是极小化总提前,总延误,窗口的开始时间,与窗口的大小的总费用。近年来,关于加工时间可控与带有交货期的单机排序受到越来越多的关注。加工时间可控是指工件的实际加工时间依赖于所分配的资源。Vickson等最早提出加工时间是资源消耗的线性函数的单机排序问题。目标函数是加工时间压缩的总费用。2.2.1模型描述 设有n个工件J1,J2,Jn在一台机器上加工。全部零件零时刻到达,加工不可中断,且机器在同一时间只能加工一个工件。工件Jj的时间加工时间Pj(j=1, ,n)是一个依赖资源量的线性非增函数,即 (1) 其中j表示工件Jj的正常加工时间,xj表示分配给工件Jj的资源,j表示分配给工件Jj的资源的上界,即0xjj,uj表示工件Jj的正压缩率。bj(0)表示单位资源的费用。不失一般性,j0,xj0。由前面的讨论容易得到以下结果。1) 目标函数可表示为(8)2)最优资源分配。将(8)式看成是关于xj的函数,对其求导并令导数为零。则可以求出最优资源分配 (9)其中j由(3)式决定。将(9)式代入(8)式中可以得出(10)2) 最优排序。问题2可以转化为指派问题,即(6)式。其中(11)3)多项式时间算法。问题2可以通过算法1求得最优排序,不同的是步骤2中的ij由(11)式决定,步骤4中的最优分配资源由(9)式决定,步骤5中的最优加工时间由求得,计算复杂性为O(n3)。其证明过程同定理1。接下来讨论aj=a,j=1,2,n这一特殊情况。由(10)式可以得到(12)其中 (13) (14) 引理112 将(12)式中最小的j匹配给最大的(j)值,第二小的j值匹配给第二大的j值,如此进行下去,得到的排序是最优排序。 算法2 步骤1 置,其中,; 步骤2 对每一个目标函数,通过(13)、(14)式计算,j,j,j=1,2,n; 步骤3 按照引理1的方法对工件进行排序,定义最优排序为*=(J(1),J(2),J(3),J(n); 步骤4 通过(9)式计算最优资源分配; 步骤5 通过式子计算最优加工时间; 步骤6 置交货期的最优长度为。 定理2 算法2求得排序问题 的最优排序,计算复杂性是O(nlog n)。 证明 由以上讨论可知,算法2的主要计算在于步骤2,由于步骤2的计算复杂性为O(nlog n),因此算法2的计算复杂性为O(nlog n)。 证毕23 应用实例及计算结果例1 机械加工一个机械加工车间要加工一批机器零件,每一个零件都具有相同的工序,即按相同的顺序在几个不同的机床上加工,但每个零件在每个机床上的加工时间可能不同。如何安排加工顺序才能以最短的时间加工完所有的零件?这是一个流水作业排序间题。例2 进程排序在计算机多道程序操作系统中,并行执行多个进程:在宏观上同时执行多个进程,在微观上在任何时刻CPU只能执行一个进程。进程的到达时间是不同的,怎样排序这些进程才能使CPU的利用率最高或进程的平均周转时间最短?这也是一个排序间题。例3 机场排序在一个飞机场,有几十个登机门,每天有几百架飞机降落和起飞。登机门的种类和大小是不同的,班机的机型和大小也是不同的。一些登机门安放在能容纳大型飞机的地方,小登机门只能容纳小型飞机。飞机按时刻表降落和起飞,由于天气和机场的其它原因,时刻表也有很大的随机性。当飞机占有登机门时,到达的旅客下飞机,出发的旅客上飞机,飞机要接受诸如加油、维护和装卸行李等服务。如果飞机在下一个机场不能按时降落,此时为了节省燃料,飞机不能起飞,登机时间推迟,飞机需要占有一个登机门而其它的飞机不能使用。机场的排序人员需要制订一个可行的方案,把登机门分配给降落的飞机,使机场的利用率最高或晚点起飞的飞机最少,这也是一排序问题。在这里飞机被看成是被加工的工件,登机门当作机器,机场的规定是约束条件。这里,由于本科期间的专业限制,本文举例侧重于机械加工。设n=5,工件的正常加工时间向量为=(11,9,15,7,12)工件的正压缩率向量为=(0.5,0.7,0.4,0.3,0.9)。资源分配的上界向量为=(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,则,计算k*=2,因此,d*=C2。然后,利用求得向量=(10,11,12,8,4),利用和分别求得向量 =(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软件解指派问题求得最优排序为且指派问题的最优值为,利用求得=100,最优值=648.24。对于i=1,2,3,4的情况的计算与此相同(如图)。图2-1从表中可知,因此最优维修位置是i*=4,最优排序是。2.4本章小结 本文讨论的是工件的加工时间是资源分配的线性函数的单机排序问题及与位置相关的加工时间可控问题。给出了最优排序的一些性质,及最优资源分配的求解方法、多项式算法,证明了这些问题在多项式时间内可以求得最优解。第三章 课题仿真由于本人在本科期间的专业限制,所以本文把排序问题延伸至车间调度问题上,再进行仿真。3.1 车间调度仿真 车间资源的有限性制约着能否有效利用车间现有资源完成任务,以最快的速度响应市场需求,促使制造型企业能否赢得市场竞争。调度任务是根据生产目标和约束,为每个加工对象确定具体的加工路线、时间、机器和操作等。优良的调度策略对于提高生产系统的最优性、提高经济效益都有着极大的作用。3.1.1 车间调度问题的描述 车间生产调度问题是调度问题的一个子集。可以描述为:个工件在台机器上加工,一个工件分为道工序,每道工序可以在若干台机器上加工。典型的生产调度问题涉及一个要完成的任务集,其中每一个任务包含一组需要执行的作业序列(工序),这些作业序列需要占用系统的机器、工具等资源,并且必须按照一定的工艺顺序执行;一个资源集合,包括人员、设备、工具和材料等,每台设备可以完成一种或多种作业,不同设备能完成的作业集可能相同也可能不同;一个约束条件集,如任务的优先级、工序的先后关系、每个作业要求完成的时间、资源的能力等;一个性能指标集,用以规定生产过程中需要优化的目标,如生产周期、在制品量、订单交货期、资源利用率和生产成本等。调度的目标就是要为作业集中的作业合理分配资源,合理安排每个作业的加工次序,使约束条件被满足,同时使部分或全部生产性能指标得到优化。3.1.2 车间调度问题的特点在实际的制造企业车间生产环境中,更普遍的调度类型应当是具有Job-shop调度和动态调度属性的混合类型,车间调度问题主要具有以下几个特点。 1)复杂性:由于生产车间中工件、机器、缓存及搬运系统之间相互影响、相互作用,每个作业又要考虑它的加工时间、操作顺序和交货期等,因而相当复杂。同时计算量极大,是典型的非多项式(Nonpolynomial,NP)难题。 2)动态随机性:在实际的生产调度系统中存在很多随机的和不确定的因素,环境是不断变化的,在运行过程中会遇到多种随机干扰,而且生产系统中常出现一些突发偶然事件,动态随机性大。 3)多目标性:实际的计划调度往往是多目标的,并且这些目标间可能发生冲突。这种多目标性导致调度的复杂性和计算量急剧增加。4)多约束性:生产车间中资源的数量、缓存的数量、工件的加工时间和加工顺序都是约束。此外还有一些人为的约束,如要求各设备上的负荷平衡等等。3.2 仿真调度的原理和特点3.2.1 仿真调的德原理制造系统的调度问题是在制造资源、加工工艺等约束条件下,寻求一组控制和决策变量,使得某个目标达到或接近最优。优化理论方法用一组等式或不等式表示这种约束关系,通过推导和计算确定使目标函数最优的决策变量值,具有很好的优化效果。但是当调度问题比较复杂时,数学模型可能非常复杂,计算量大,也可能出现无解的现象。仿真调度的基本原理是,建立仿真调度模型,在仿真调度决策规则的引导下,在模型上试探性地经历整个加工过程,记录该过程中系统的状态变化,统计、处理并产生调度方案和性能数据。因此仿真调度方法实际上是一种实验性和试探性的方法,不会出现无解的现象。3.2.2 仿真调度的特点离散事件系统建模和仿真的关键是对导致系统状态发生变化的事件的定义和处理。在仿真调度问题中,通常把工序(或操作)的启动事件和结束事件看作两类最基本的事件。在工序启动函数中实现对资源的竞争和申请,在结束函数中实现资源的释放和再分配。由于存在竞争,一个工序可能在多次启动尝试后,才能真正开始。当一个工序开始时调度其结束事件;当一个工序结束时调度下一个工序的开始事件;在处理这些事件中实现仿真时钟的推进,直到所有订单的所有工序加工完毕。由于仿真中对资源的竞争和分配始终满足资源的容量约束,工序启动后对结束事件的安排满足加工时间约束,工序结束后对下一个工序的安排满足工艺顺序约束,因此仿真产生的调度方案是调度问题的可行解。由于采用事件调度和进程交互等仿真建模方法,只处理那些导致系统状态发生改变的有限个事件,而且仿真步长是可变的,因此能够有效地减少仿真的计算量,提高调度速度。在仿真运行过程中,全面收集和记录系统状态变化数据,使仿真具有很强的调度能力,具体表现在以下几个方面。1)根据这些数据生成针对设备、操作、库存和物料系统的详细调度方案等,调度能够用符合企业惯例和控制需要的形式表达。2)能够给出完整的性能统计数据,有利于对调度进行综合评价和选择。3)当出现紧急订单、原材料迟到、设备故障等情况时,原来的调度不再适用,需要重新调度,而该时刻系统状态完整地保存着,可以作为系统状态的初始值。3.3
收藏