《具有学习效应的总完工时间流水线排序问题与仿真论文》由会员分享，可在线阅读，更多相关《具有学习效应的总完工时间流水线排序问题与仿真论文（34页珍藏版）》请在金锄头文库上搜索。
1、西北工业大学明德学院本科毕业设计论文本科毕业设计论文题 目 具有学习效应的总完工时间流水线排序问题与仿真 专业名称 机械设计制造及其自动化 学生姓名 毕业时间 二一四年 七月 IV西北工业大学明德学院本科毕业设计论文设计论文毕业 任务书一、题目具有学习效应的总完工时间流水作业排序与仿真二、指导思想和目的要求（1）掌握运用所学理论知识分析解决工程实际问题的一般方法；（2）培养分析问题、解决问题和独立工作的能力；（3）通过毕业实习、毕业设计及毕业答辩全过程的训练，加强 老师与学生之间、学生与学生之间知识的相互交流，互相渗透，培养学术研讨的好学风；（4）要求同学们以满腔的热情、科学的态度，严谨的作风
2、、高度的责任感从事毕业设计工作；不得敷衍了事、马马虎虎、得过且过；提倡周密思考、大胆创新，反对死搬硬套、墨守陈规；提倡共同研究，反对相互抄袭；（5）要求遵守学校的各项规章制度，确保毕业设计顺利地、高质量地完成。三、主要技术指标过去处理排序问题，大多采用两种方式:一种是根据以往经验，必要时作些修改，另一种是事物并不复杂，作些考虑即可奏效，排序问题不成其为一门学问。计算不周即可造成重大损失，依靠拍拍脑袋已不能解决问题;而且产品更新很快，新产品的生产、销售等没有成法可资参考，此时各种新的组合优化问题便涌现出来，排序问题便是其中之一。1. 翻译文献15002000字2. 讨论单机排序问题3. 利用仿真
3、软件对单机排序问题做出算法并给出最优解4. 研究学习效应对机器的影响四、进度和要求（1）第1-3周收集资料，根据需要学习相关的硬软件；（2）第4周进行系统概要设计，提出设计的总体思想；（3）第5周，初步确定设计方案；（4）第6-12周，完成单机，针对设计中存在的缺点和不足，不断完善设计方案；（5）第13-14周，撰写并修改论文；（6）第15-16周，完成论文，准备答辩资料。五、主要参考书及参考资料自行确定本页不够可以续页 学生 张红伟 指导教师 王剑 系主任 摘 要排序问题的一大特点是:模型繁多，适用于某一模型的算法，只要将模型的条件稍加变化，该算法即不适用. 包括如何对各个部件进行分隔、布线
4、和布局的问题”.排序论是国际上发展最迅速、研究最活跃、成果最丰硕、前景最诱人的学科领域之一特别引人注目的是:随着现代工业的发展，经典的排序模式已被突破，新的模式层出不穷，吸引了越来越多的理论工作者和实际工作者、可控排序、多目标排序、成组分批排序、同时加工排序、准时排序和窗时排序、资源受限排序、不同时开工排序、随机排序、模糊排序、应用排序等，就是其中发展最为迅速的一些新方向. 在我国，对排序问题的研究较晚，虽然早在20世纪50年代末，就有人注意到这一问题一问题的研究，并开始作一些宣传普及的工作;但由于众所周知的原因，对这，直至70年代中才开始，到80年代，对算法感兴趣的人越来越多。现研究工件具有
5、学习效应的单台机器流水作业排序问题与仿真。工件的学习效应指工件的加工时间为所排位置的指数函数。目标函数为极小化总完工时间。给出该问题的数学规划模型。同时对大规模问题给出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 a
6、pply. 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 mode
7、rn 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 no
8、t 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.Howev
9、er, 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 p
10、osition.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 a
11、re effective in solving the problem with large scale.KEYWORDS: scheduling，flow shop，learning effect，the total completion time西北工业大学明德学院本科毕业设计论文目 录错误!未找到引用源。33第一章 绪 论1.1 流水作业排序问题1.1.l引例排序(scheduling)问题产生的背景主要是机器制造，后来被广泛应用于计算机系统、运输调度、生产管理等领域.从普通的生产部门的计划安排、人员调度，学校课程表的制订，到宇宙飞船的复杂庞大的飞行计划，都要用到排序的理论和算法。在给出
12、排序问题的一般定义之前，我们先看几个排序在实际领域中应用的例子。例1.1机械加工 一个机械加工车间要加工一批机器零件，每一个零件都具有相同的工序，即按相同的顺序在几个不同的机床上加工，但每个零件在每个机床上的加工时间可能不同.如何安排加工顺序才能以最短的时间加工完所有的零件，这是一个流水线排序问题。 例1.2进程调度 在计算机多道程序操作系统中，并发执行多个进程，在宏观上同时执行多个进程，在微观上在任何时刻CPU只能执行一个进程。进程的到达时间是不同的，怎样调度这些进程才能使CPU的利用率最高或进程的平均周转时间最短?这也是一个排序问题。另外，每个进程的到达时间和执行时间事先是不知道的，但随机
13、到达时间和执行时间的分布、它们的数学期望、方差等是已知的，这时的目标是极小化平均周转时间的数学期望。排序问题中出现了随机变量称作随机排序问题。例1.3机场调度在一个飞机场，有几十个登机门，每天有几百架飞机降落和起飞。登机门的种类和大小是不同的，而班机的机型和大小也是不同的，一些登机门安放在能容纳大型飞机的地方，小登机门只能容纳小型飞机。飞机按时刻表降落和起飞，由于天气和机场的其他原因，时刻表也有很大的随机性。当飞机占有登机门时，到达的旅客下飞机，出发的旅客上飞机，飞机要接受诸如加油、维护和装卸行李等服务。如果飞机在下一个机场不能按时降落，此时为了节省燃料，飞机不能起飞，登机时间推迟，飞机需要占
14、有一个登机门，而其他的飞机不能使用。机场的调度人员需要制订一个可行的方案，把登机门分配给降落的飞机，使机场的利用率最高或晚点起飞的飞机最少，这也是一个排序间题，在这里飞机被看成是被处理的任务，登机门当作处理机，机场的规定是约束条件。1.2 排序问题的定义排序(scheduling)问题是一类重要的组合最优化问题，它是利用一些处理机(processor)、机器(machine)或资源( resource )，最优地完成一批给定的任务(task)或作业(yob)。在执行这些任务或作业时需要满足某些限制条件，如任务的到达时间、完工的限定时间、任务的加工顺序、资源对加工时间的影响等.最优的完成指的是使
15、目标函数达到最小，而目标函数通常是对加工时间的长短、处理机的利用率的描述。在排序问题中，处理机的数量和种类，任务或作业的顺序、到达时间、完工限制，资源的种类和性能等情况是错综复杂的，很难用精确的数学描述给出一般的排序定义。在本书中，我们用如下方式来描述排序问题: 给定n个任务的任务集 T = ,m个处理机的处理机集 P =, 和s种资源的资源集 R =,排序问题指的是在一定条件下，为了完成各项任务，把沙中的处理机和(如果有)中的资源分配给了中的任务，使目标函数达到最优。排序问题基本上是由处理机的数量、种类与环境，以及任务或作业的性质和目标函数所组成。处理机只有一个处理机的排序问题称为单(处理)机(single processor, single machine)排序问题，否则称为多(处理)机排序问题。在多处理机排序问题中，如果所有的处理机都具有相同的功能，称它们为同类机或平行
