工件硕士毕业论文大纲,带装载和卸载的平行机调度问题

怎么写作好工件和算法和加工相关的论文。这篇带装载和卸载的平行机调度问题的硕士毕业论文大纲会给到你参考帮助。

1 绪 论


1。1调度问题概述
调度问题通常被描述为“分配一组资源来执行一组任务”,即排序(scheduling).它是组合优化领域中的一类重要问题,产生的背景主要是机器制造,现在被广泛运用到信息处理、生产计划调度、供应链管理等领域.随着经济生产的发展和国与国之间密切的交流,调度问题的理论和应用也得到很快的发展.在目前激烈的市场竞争环境下,高效率的调度也成为企业在市场竞争中取胜的一个重要因素.近几十年来,调度问题得到计算机科学界、运筹学界、工程学界和管理学界的极大关注,鉴于经典问题的研究已经日益深入,并且具有实际背景的新问题又不断出现,可以说,对调度问题的研究正在进入成熟期.根据调度问题的最初背景,把需要完成的任务称为工件(job),把完成任务需要的资源称为机器(machine).调度问题是希望找到一个可行的调度,使得某个满足特定约束条件的目标函数最小(大).可行的调度一般是指:在同一时刻,一个工件只能在一台机器上加工,一台机器上也最多只能加工一个工件,并且该调度满足问题特定的约束要求.通常用Graham等人[1]首先使用的“三参数表示法”(three-field parameter)α | β | γ来表示一个调度问题,α, β, γ分别刻画了机器环境、工件特征和最优准则.α域表示处理机的类型、环境和数量.根据处理机的不同,可以将调度问题分为多处理机(multiprocessor)问题和单处理机(single machine)问题.如果所有的处理机都具有相同的功能,则把它们称为平行机(parallel processors),并且可以再根据加工速度的不同,把它们分为同型机(所有处理机具有相同的速度)、同类机(处理机的速度不同,但不依赖被加工的任务)、不同类机(速度依赖于被加工的任务).
………


1。2算法的设计与分析
调度问题的算法指事先给定了一个可执行的程序,这个调度问题的任何一个实例可以按照该程序得到一个可行的调度.根据离线和在线两种情况,有离线算法和在线算法,例如LPT 算法[1](Graham,1969)和LS算法[2](Graham,1966)是分别解决离线问题和在线问题的经典算法.其中LPT算法是指将所有工件按非增序列排成一列,然后依次将它们安排在尽早使工件完工的机器上,而在在线问题中,由于工件信息是随着工件的到来而知道的,所以LS算法是指将工件安排在使其能最早加工的机器上.所谓算法的时间复杂度是度量算法执行的时间长短.如果存在一个算法,使得一个调度问题可以在多项式时间内得到解决,则称该算法为多项式时间算法,该算法的时间复杂性为O(p(n)).由于调度的问题基本上都是NP难问题,除非P = NP,否则不存在求最优解的多项式时间算法,因此一般寻找的是能在较短时间(多项式时间)内得到接近于最优解算法(optimal algorithm)的算法,也即用近似算法(approximation algorithm)来解决该调度问题.
………。


2 带单个服务器的平行机调度问题的最优算法设计


2。1 引言
带服务器的调度问题在实际生活中也有很广泛的应用.比如,柔性制造系统(FMS)中,有一个机器人(Koulamas,1996)[16]或者是自动导引车(AGV)(Ganesharajah etal。,1998)[27]在几条生产线中负责工具的变换或是部分的装载工作;单元式制造(Daw&#

带装载和卸载的平行机调度问题
工件和算法和加工硕士毕业论文大纲

97;ndeet al。,2005[28];Batur et al。,2012[29])或是半导体工业(Kim and Lee,2012)[30]中,服务器负责装载和卸载物料或者是在加工站之间运送零部件;2012年Xie等人[23]在钢铁行业箱式退火工艺的关键环节(加热和冷却)中,又发现了一个新的应用.关于带服务器的平行机调度问题的文章很多,但大部分都只考虑装载的情形,很少有文章同时考虑装载和卸载.对于服务器负责装载和卸载的平行机调度问题,Hu等人[24]在2013 年研究了不可中断的情形,证明该问题是二元NP难的,并使用LS算法和LPT算法得出最坏情况界分别为12/7和4/3.对于带服务器的调度问题,2012年Xie[22]等人考虑的是服务器负责卸载操作,并在工件加工完成后允许延迟的情形,对于该问题Xie等人将工件预先进行分配的情况下,提出了一个紧界为2的算法.Yip 等人[26]在2006年研究了带多个服务器装卸载操作的流水作业问题.
………。


2。2 符号及最优解下界
对于经典的平行机调度问题,某时刻机器完成了上一个加工任务,只要后继还有等待加工的工件,则这台机器就可以立刻开始加工下一个工件,但是随着科技的发展,在现代化大规模制造系统中常常遇到这样的情形:几个机器人在多台数控机床之间管理工件的加工,工件在被放到一台机床上开始加工之前,首先需要一个机器人负责把工件安装在这台机器上,然后机器再独立地对工件进行加工.实际在该模型中,每个工件的加工过程包括着两道工序:首先对待加工的工件进行安装作业;其次再对该工件进行加工作业.目前这类带装载的平行机调度问题研究的也较多,该问题从19世纪六十年代中期就已经开始有人研究,自从Allahverdi, A。等在1999年做出对该问题的总结后,基本上每年都有近40篇有关这类问题的论文出现,而且也渐渐从理论研究转到更贴近实际的应用上来[4 11].在柔性制造系统中,一个机器人负责多个工具的转换或是部分工具的装载;或是在单元式制造中,一个工人负责多个机器生产单元以及钢铁行业箱式退火工艺的关键环节(加热和冷却)或是自动物料搬运系统都可以看做是带服务器的平行机调度问题.Ou等[7]研究了带多个卸载服务器的平行机调度问题.该问题是由一家上海手机制造商的入厂物流系统所引发的.该工厂将许多不重要的部件外包给许多独立的供应商,并且由第三方物流提供商(3PL)从供应商那里收集零部件运送到手机制造商那里.
…………。。


3 带两个服务器的平行机调度问题。。。。。。 17
3。1 引言。。。。。。。。 17
3。2 预备知识。。。。。。。。。。。18
3。3 LS算法。。。。。。。。。。。18
3。3。1 LS算法的结构。。。。 19
3。3。2 LS算法的最坏情况界分析。。。。。。。。 21
3。4 LP T 算法。。。。。。 23
3。5 小结。。。。。。。。 28
4 LP T 算法在配送中心的应用。。。。。。 29
4。1 引言。。。。。。。。。 29

1 2

社会保障硕士论文 致谢,中国社会保障差异规范思考

内部审计硕士毕业论文,内部审计有效性对注册会计师审计质量的影响研究

管理审计硕士毕业论文致谢模板,卓越绩效管理审计--集团初步应用理论与实务分析