带有交货期和加工时间可控的单机排序问题答辩稿

专业：机械设计制造及其自动化 姓名： 西北工业大学明德学院 2010级本科生毕业设计答辩 题目： 带有交货期和加工时间可控的单机排序问题 任务：讨论了带有交货期和工件的加工时间可控的单机排序问题。本文首先根据最优排序的性质确定了最优资源的分配方法，并将问题转化为指派问题 $通过构造多项式时间算法确定最优排序。 论文工作安排 第一章 绪 论 第二章 单机排序问题的建模 第三章 仿真与分析 第四章 总结与展望 第一章 绪 论 1.1课题研究的背景和意义 1.2课题研究的目的意义和主要内容 1.3本章小结 近年来带有可控加工时间的排序问题受到越来越多的关注。加工时间可控是指工件的实际加工时间是一个依赖资源量的函数。 在交货期问题中若工件在交货期中完工则不产生惩罚费用若工件在交货期之前或之后完工则会产生提前或延误的费用。 排序又称调度 ,作为运筹学的一个分支 ,是一门应用性很强的学科 ,有着其深刻的实际背景和广泛的应用空间。在现代企业竞争中，准时生产已经成为一种重要的竞争策略。根据准时生产原则，工件的完工时间要尽量地靠近某一时刻（时间段）。如果工件在该时刻（时间段内）完工，就不会产生惩罚 ； 如果工件在该时刻（时间段）之前或之后完工，就会产生提前或者延误的惩罚，这就是工期问题（工期窗口问题）。同时为提高机器的生产效率，可以考虑在机器上执行维修。本文主要讨论的是带有交货期和加工时间可控的单机排序问题。 排序 (scheduling)问题是一类重要的组合优化问题，它产生的背景主要是机器制造，后来在管理科学、计算机控制、硬件设计、生产调度和工程技术等很多领域应用非常广泛。 排序间题是一类重要的组合最优化问题，因为排序问题中所涉及的机器、工件都是有限的，绝大多数的排序问题是从有限个可行解中找出一个最优解，使得目标函数达到极小。在排序问题中我们称可行解为可行排序，称最优解称最优排序。 排序问题是组合最优化学科的重要组成部分之一。一个医院门诊 ,大家是按照时间先来后到排序 ,还是按照病情轻重缓急排序 ；一个大型工程 ,各种机械设备是按照机器运行成本排序 ,还是按进度需要排序 ；一个工件加工车间 ,工件加工是按照资源利用率排序 ,还是按照完工期限排序 ,这些都要涉及排序问题。 排序问题普遍应用于生产管理、运输调度、计算机系统等领域，引起许多专家学者的广泛关注，并以实际生产活动为基础进行理论研究。 第二章 单机排序问题的建模 2.1 单机排序 2.2 应用举例及计算结果 。 J r Jp p r1 ( )J r Jp p r f c现给出单机排序的一般描述。设有 n个工件 J1， J2， ， Jn， 工件 Jj的权为 uj，工件 Jj的工期为 dj。若工件 Jj排在第 r个位置加工，则其加工时间为 ， j=1， 2， ， n。其中 pJ为工件 Jj的正常计算共时间，其单机排序问题可记为 。 。 设有 n个工件 J1， J2， ， Jn在一台机器上加工。全部零件零时刻到达，加工不可中断，且机器在同一时间只能加工一个工件。工件 Jj的时间加工时间 Pj（ j=1, ,n）是一个依赖资源量的线性非增函数。 显而易见，最优排序满足工件的开始加工时间从零时刻开始，且机器没有空闲。 () jaj r j jjp x p r u x( ) ( )jaj kjrjprpxx Lu Yuan-yuan等讨论了具有具有学习效应的加工时间可控的单机排序问题 ,1） 2） 。 本文讨论的是工件的加工时间是资源分配的线性函数的单机排序问题及与位置相关的加工时间可控问题。给出了最优排序的一些性质，及最优资源分配的求解方法、多项式算法，证明了这些问题在多项式时间内可以求得最优解。 第三章 仿真与分析 3.1 车间调度仿真 3.2 仿真调度的原理和特点 3.3 仿真的基本方法 3.4 实例仿真 3.5 本章小结 车间资源的有限性制约着能否有效利用车间现有资源完成任务 ,以最快的速度响应市场需求 ,促使制造型企业能否赢得市场竞争。调度任务是根据生产目标和约束，为每个加工对象确定具体的加工路线、时间、机器和操作等。优良的调度策略对于提高生产系统的最优性、提高经济效益都有着极大的作用。 车间生产调度问题是调度问题的一个子集。可以描述为 :个工件在台机器上加工 ,一个工件分为道工序 ,每道工序可以在若干台机器上加工。 在实际的制造企业车间生产环境中，更普遍的调度类型应当是具有 Job-shop调度和动态调度属性的混合类型，车间调度问题主要具有以下几个特点。（ 1）复杂性。（ 2）动态随机性。（ 3）多目标性。 （ 4）多约束性。 制造系统的调度问题是在制造资源、加工工艺等约束条件下 ,寻求一组控制和决策变量，使得某个目标达到或接近最优。优化理论方法用一组等式或不等式表示这种约束关系，通过推导和计算确定使目标函数最优的决策变量值，具有很好的优化效果。但是当调度问题比较复杂时，数学模型可能非常复杂，计算量大，也可能出现无解的现象。 仿真调度的基本原理是，建立仿真调度模型，在仿真调度决策规则的引导下，在模型上试探性地经历整个加工过程，记录该过程中系统的状态变化，统计、处理并产生调度方案和性能数据。因此仿真调度方法实际上是一种实验性和试探性的方法，不会出现无解的现象。 离散事件系统仿真中仿真进程的推进方法是十分重要的。应用任何一种方法都应考虑如何选择下一事件，以便执行相应的程序模块来修改系统状态，进行各种统计计算。根据处理的方法不同， 可将离散事件仿真分成三类，（ 1）事件调度法。（ 2）活动扫描法。（ 3）进程交互法。 第四章 总结与展望 排序问题起源于制造业，作为运筹学的一个分支，发展非常迅速。近年来，排序问题已发展成为运筹学、系统科学、管理科学和计算机科学等多个学科领域的一个交叉学科，有着深刻的实际背景和广阔的应用前景。在 20世纪 80年代以前，对于排序问题的研究主要集中在一些经典模型上。近十多年来，出现了许多现代排序问题。这些现代排序间题突破了经典模型的基本假设，具有更广泛的实际应用背景，同时也更为复杂。随着各种实际问题的提出，现代排序问题不断产生。尽管某些