本文是一篇工程硕士论文范文，本文结合制造业中半成品工件加工面临的实际问题，研究了实际生产中逆区间调度相关的新问题。
第1章绪论
1.1研究背景及意义
制造业作为国民经济的主体，对我国的现代化建设以及国际竞争力的提升具有积极的推动作用。中国自2002年加入世界贸易组织之后，为了适应国际贸易规则和国内外经济环境的变化，不断加大改革开放的力度，吸引了世界各国的大型企业到中国落户发展，促使中国逐渐成为“世界工厂”。2010年中国制造业在全球制造业中占比达19.8%，跃居世界排名第一。然而随着全球制造业格局的不断变化和我国国民经济的高速发展，中国制造业正面临着生产成本提高、资源利用率低、资源匮乏、环境严重污染等问题，这些问题导致中国制造业增长动能减弱、核心竞争力不足等问题日益显现。《2021中国制造强国发展指数报告》中指出，我国目前处于全球制造业的第三阵列。为了缩小与第一、二阵列制造强国之间的差距，突破制造业面临的质量和效益难以提高的瓶颈，让中国从制造大国转型为制造强国，实现更高效、更可持续、更安全的高质量发展，不仅要在技术上进行改革与创新，还要针对制造企业在生产过程中面临的实际问题开展理论创新，统筹生产所需的资源、时间、成本，在规定的时间内达到资源利用最大化以及成本最小化的目标，制定出符合企业生产调度的策略，推动我国制造业的转型升级。
调度（Scheduling），又称为排序，是运筹学离散优化的重要分支之一，也是影响企业管理和工业生产的重要课题之一。研究调度问题事实上是在给定约束条件的基础上，以目标优化为导向，对有限的资源实行合理的分配，从而实现生产效益最大化的目标。生产调度是调度领域中最重要的一类问题，它在遵守一定的规律和原则的基础上，从企业的效益和未来发展出发，通过协调生产环节中的资源和流程，对企业生产的效率进行提高。生产调度在实际生产中具体体现为：企业在生产制造中通常会受到一些限制，例如生产工期时长限制、生产成本限制、各种资源限制等，需要通过合理的调度资源，达到极小化工期、极小化成本、极大化利润等生产目标。生产调度早期主要用于解决工业生产领域的问题，为工业企业的资源配置提供理论支持。
1.2国内外研究现状
逆区间调度问题是由Yim等（2022）提出的新调度问题，Yim在文献中主要证明了即使在单机情况下，逆区间调度是NP难问题，并针对该问题给出了一个完全多项式近似算法（fully polynomial time approximation scheme，简称FPTAS）。然而目前还未出现其他新的关于逆区间调度的文献。
基于对已有文件的研究，观察到逆区间调度问题与区间调度问题（interval schedulingproblem）的一些拓展研究有一定的相似性，甚至从离散特性来看，逆区间调度问题可以看作是区间调度问题的一个推广问题——工件区间选择问题（job interval selectionproblem）的特例。此外，逆区间调度问题在一定程度上接近于处理时间可控的调度问题。因此，以下将从区间调度问题和处理时间可控的调度问题两个角度出发，分别分析它们的研究现状以及它们和逆区间调度问题的联系与区别。
1.2.1区间调度问题研究现状
区间调度又称为固定工件调度，Gertsbakh和Stern（1978）首先提出了固定工件调度问题，证明了固定工件调度是数学问题Dilworth问题的一个特例，并提出了一种求解固定工件调度的近似算法。事实上，固定工件调度问题是多项式时间内可解的，Gupta等（1979）给出了时间复杂度为Onlogn的多项式时间算法。此后，有部分学者对固定工件调度的衍生问题进行研究，Fischetti等（1992）考虑了带有扩展时间约束的固定工件调度问题和带有工作时间约束的固定工件调度问题，给出了这两个问题的多项式时间近似算法，并分析了它们的复杂性和最坏情况下的性能；
第2章基本理论介绍
2.1组合优化问题概述
组合优化（Combinatorial Optimization）问题又称为离散优化问题，属于最优化问题中的一类。在运筹学、数学、管理学等多个领域中，组合优化问题的研究都有着重要的意义，它是基于已有的一些数学方法，研究离散事件中的最优序列、分组、筛选和次序等问题，即在有限集合的的子集簇中，求解满足约束条件且使目标最优的唯一或多个最优解。
从现实意义来说，许多组合优化问题涉及到社会生活中的不同领域，包括生产制造、智能运输、网络通信、物联网技术、项目管理等。经典的组合优化问题有：旅行商问题（Traveling Salesman Problem-TSP）、调度问题（Scheduling Problem）、装箱问题（BinPacking Problem）和图着色问题（Graph Coloring Problem）等。本文的研究内容为组合优化问题中的调度问题（Scheduling Problem）。
2.2算法及复杂度理论
2.2.1算法概述
算法（Algorithm）是求解组合优化问题的重要方法，也是计算机科学的核心课题之一。随着社会信息化程度越来越高，物流运输、智慧交通、智能安防、线上教育等社会生产各个领域的快速发展都与算法有着密切的联系，本文涉及到的制造业领域的优化发展也与算法息息相关。从广义上看，算法是解决某个方案时使用的准确且完整的描述；从狭义上看，算法是由一系列清晰的指令、程序或方法组成的序列。对于任意符合规范的输入，能够在有限的时间内通过算法得到符合相应要求的结果。在运用算法时需要注意算法的适用性，可以用某一种算法对同一类型的多个问题进行处理和求解，当问题的本质发生了改变，就需要设计新的算法去解决新问题。不同算法在运行时间和运行空间上存在着差异，运行时间越短、运行空间越小的算法越理想。
（2）启发式算法（Heuristic Algorithm）
启发式算法是一种根据已有认知设计的算法。它能够在可以控制的时间和空间范围内，针对某些组合优化问题的所有实例给出可行解，但这类可行解与问题最优解之间的偏差是无法预计的，一般需要通过相应的数值实验去衡量启发式算法性能的优劣。目前，组合优化问题中常用的启发式算法以仿自然体为主，例如蚁群算法、遗传算法、神经网络算法等。启发式算法的时间复杂度一般是指数级别的，但它的使用效果较好，因此该算法具有较高的接受度。
（3）近似算法（Approximation Algorithm）
组合优化问题中有一类NP-hard问题，这类问题一般不存在多项式时间最优算法，通常选择采用启发式算法或近似算法进行求解。由于启发式算法的时间复杂度较高，并且需要进行数值实验，无法从理论上对算法解和最优解的偏离程度进行分析。而在近似算法中，通过降低精确度，在多项式时间内找到问题的次优解，并且可以在理论上对近似算法解与最优解之间的偏差进行分析。
第3章子区间有限的逆区间调度问题................................20
3.1引言...............................20
3.2符号说明..........................................20
3.3问题描述和NP-hard分析............................21
第4章开始时间不可修改的逆区间调度问题..........................32
4.1引言................................32
4.2符号说明......................................32
4.3问题描述和NP-hard分析................................33
第5章考虑老化效应和速率维修活动的逆区间调度问题.........................47
5.1引言.................................47
5.1.1基于机器老化效应的生产调度问题概述..........................47
5.1.2考虑速率维修活动的生产调度问题概述.................49
第5章考虑老化效应和速率维修活动的逆区间调度问题
5.1引言
为了使机器的利用率达到最大化，企业在接收开始时间不可修改的半成品工件的加工订单时，尽量选择能将机器的空闲时间压缩到0并且能够避免工件加工时间发生冲突的订单。当满足上述条件时，意味着订单中工件之间没有交集和等待时间，这是一种理想的开始时间不可修改的逆区间调度。然而在实际生产过程中，工件在机器上的加工时长会受到老化效应的影响，工件的实际加工时长大于其初始加工时长，导致工件区间的实际结束时间相对于初始结束时间延后，需要对工件区间进行修改，否则影响后面工件的正常加工。为了缓解老化效应造成的影响，企业决定在某个时间段安排一次速率维修活动。在机器上不同位置执行速率维修活动的效果不同，因此本章研究了考虑老化效应和速率维修活动的逆区间调度问题，目标是找到区间修改总成本的最小值，以及取得最小值的调度中对应的速率维修活动的执行位置。
本节首先分别对考虑老化效应和速率维修活动的生产调度问题的实际应用背景和研究现状进行概述，再对本章的主要内容进行介绍。
第6章总结与展望
6.1研究工作总结
本文结合制造业中半成品工件加工面临的实际问题，研究了实际生产中逆区间调度相关的新问题。在新问题模型中，突破了逆区间调度一般模型中工件在区间修改后可以得到初始区间的任意子区间的假设，研究了子区间有限的逆区间调度问题，以及研究了开始时间不可修改的逆区间调度问题，并且在区间连续无交集的开始时间不可修改的逆区间调度中，考虑
