本文是一篇工程论文，本文结合制造业转型升级的大背景，从实际的生产调度背景出发，进行了生产调度的优化与改进，研究了带有交货期的最大化提前完工总量的少量机器调度模型。
第1章 绪论
1.1 研究背景和意
制造业作为国民经济的主体，其发展情况一直受到广泛人民的关注。虽然近年来我国制造业发展迅速，丰富的产业链遍布全球的制造市场，但总体上还是大而不强，主要矛盾体现在供需不平衡、质量效益以及资源利用效率低下等方面。面对这种现实情况，改善生产过程已经成为制造业的首要选择。近年来，国家不断出台相关法律法规来推动制造业的稳健发展。《智能制造试点示范 2016 专项行动实施方案》指出要大力推动传统制造业向智能化改造，并提出了五种智能制造新模式，其中离散型智能制造是其中重要一环。党的十九大指出企业必须加强生产性服务，创新活跃、质量卓越和效益显著是发展制造业的重要因素。《中国制造 2025》指出实现制造强国的战略目标。为了实现制造业的转型升级，从世界工厂的制造大国转变为制造强国，创新生产制造模式是制造业发展的关键。
调度（Scheduling），又称排序，是组合优化领域的一个研究热点。而生产调度实际上是一个决策过程，它指的是：在一定时期内，根据不同的任务安排，通过合理分配资源，实现目标的优化，比如邮递员问题、最小连接问题和售货员问题等调度问题的优化。调度最早被应用于工业制造领域，从系统角度来说，合理的优化算法是提升生产过程中资源利用率、生产效率和吞吐量的关键；从用户角度来说，其关乎及时性、响应速度和周转时间等问题，是提高客户服务满意度的重要组成部分。因此，选择合适的调度模型和优化算法已成为制造业转型升级的关键。
1.2 研究现状
1.2.1 公共交货期的研究现状
公共交货期指的是所有工件具有一个相同的交货期。目前大多数的研究主要是在此背景下研究的。Panwalkar 和 Seidman（1982）最早提出公共交货期问题，研究了单机环境下最小化总惩罚问题，并给出了最优算法。Baker 等（1990）以最小化延迟惩罚和总提前成本为目标，研究了具有公共交货期的一般调度模型，并在此基础上添加了并行机和不同交货期等环境下的分析，得出了许多成果。Jackson 等（1995）首次研究了具有公共交货期的最小化最大延误成本的调度问题。Gordon 等（2002）为具有公共交货期分配的单机和并行机调度模型提供了一个统一的框架。Gordon 等（2007）将最小化加权总成本作为研究对象，包括提前、延误和交货期成本，并给出了多项式时间内的最优算法。Chang 等(2009)将学习和老化效应考虑在内，研究了具有公共交货期的最小化总成本的调度模型，并在多项式时间内给出了工件的最优排列次序。Yang 等（2010）研究了具有公共交货期的单台机调度问题，并将工件老化效应和维修活动考虑在内，给出了多项式时间算法。随着研究的深入，Yang 等（2013）研究了在单机环境下多个公共交货期分配的最小化总惩罚函数调度问题，并根据问题特性，给出了两种多项式时间算法。此外，Yin 等（2013），Chen 等（2020）和 Zhao 等（2016）也进行了公共交货期调度问题的深入研究。
1.2.2 最小化误工损失的研究现状
Blazewicz（1984）首次提出了误工损失的概念，目标是在控制系统中收集信息，因此最初误工损失被称为“信息丢失”，之后 Potts 和 Van Wassenhove（1992）研究发现这样的参数不仅涉及建模与数据收集相关的场景，还涉及到建模与业务流程相关的场景，如农业中的土地收获和易腐烂商品等相关场景。因此，研究者们建议使用“误工损失”而不是“信息丢失”一词作为更普遍的用语。对于在一台机器上进行调度的情形，Potts 和 Van Wassenhove（1992）通过背包问题的转换证明了单机下最小化误工损失是 NP 难问题，并在此基础上，提出了伪多项式时间的动态规划方法，同时还研究了带有一些特殊的条件和优先权的调度模型，并证明可以在多项式内求解。同年，他们针对单机下最小化误工损失的调度问题提出了近似算法。
第2章 调度问题相关理论
2.1 组合优化问题概述
组合优化（Combinatorial Optimization）不仅涉及运筹学领域，还与计算机科学密切相关。优化问题的变量可分为连续型变量和离散型变量，其中本文研究的是难度系数更高的离散优化问题，求解该类问题时，有效性是判断解决一个离散优化问题的首要指标，组合优化是通过对数学的研究，为了实现目标最大化（或最小化，）在满足约束条件的情况下，从可行编排中找到使得目标最优的方案。工业工程是最先被组合优化问题研究的领域，之后广泛应用于调度、信息技术、通讯网络、人工智能、生产制造、工业工程和管理科学等领域。常见的组合优化问题有装箱问题、聚类问题和调度问题等。
组合优化问题与实际生活非常相关，虽然看起来比较简单，也容易理解，但求解过程是非常困难的。例如中国邮递员问题，是由中国学者管梅谷于二十世纪六十年代初提出的，它是一种经典的组合优化问题。该问题是指“有一位邮差，承包了某一特定区域的信件投递工作，他每天从邮局出发，必须走过投递范围内的所有街道，可以重复经过相同的街道，且完成投递工作后需要返回邮局。问如何安排邮差的信件投递路线，从而使得总路程最短？”该问题很容易被描述和理解，但很难解决。中国邮路问题会随着道路数量的增加而变得越来越复杂，一般采用的求解方法是枚举法，但随着道路数量的增加，会花费大量的时间和数据存储空间，枚举法显然不适用。就现有的计算机硬件水平，难以实现该类问题的求解。因此选择有效可行的方法是解决组合优化问题的关键。
2.2 算法及复杂度理论
2.2.1 算法概述及应用
近年来随着新兴技术和 IT 产业的快速发展，智能技术广泛应用于物流、推荐系统、交通、医疗和人脸识别等领域，而支持智能技术发展的便是算法设计和应用。在应用数学和计算机科学中，算法（Algorithm）是求解问题的步骤、方法或程序。算法是针对问题的任一实例，都能找到使得目标最优的可行方案。对于一个实例，可以使用很多种算法，通过算法之间性能的比较和针对性的改进，可以更有效率的求解问题。比如找出一个序列（21，300，273，809，134）中最大的数，这可以当作是最大值的一般问题来解决。为了求解最大值，需要设计合适的算法，而通常解决问题的算法有很多种，其中评估算法的性能好坏的方法主要有以下两种：一是算法求解问题的时间复杂度（Time complexity），二是计算最坏情况界，即分析算法解与最优解之间的偏差程度。
目前，一般常用以下三种算法进行求解组合优化问题。
多项式时间算法的时间复杂度表示为 (( ))O P n ，其中 P(n) 是关于 n 的多项式表达式。启发式算法（Heuristic Algorithm）在可接受的计算时间和空间下，对每个实例都能给出一个可行解，但不能估计与最优解之间的偏离程度。近似算法一般用来研究 NP-hard 问题，求得的近似最优解通常有质量保证，且可以衡量其与最优解之间的偏差程度。
第 3 章 带有交货期的最大化提前完工总量的一般模型.................... 19
3.1 符号说明...................... 19
3.2 模型描述以及近似算法描述...................... 20
第 4 章 带有交货期的最大化提前完工总量的少量机器模型................ 25
4.1 本章研究内容.............................. 25
4.2 最坏情况界分析......................... 25
第 5 章 算例分析........................... 39
5.1 算例介绍............................ 39
5.2 算例求解............................... 40
第5章 算例分析
5.1 算例介绍
为了衡量前两章中 LPT 近似算法的性能，本章主要采用 Java 和 LINGO 工具进行算例分析，利用数据实验给出了具体算例及其算法解，并比较了算法解与最优解之间的GAP 值。
运行算法的计算机配置为：（1）Inte（lR）Cor（eTM）i5-10310U CPU @ 1.70GHz 2.21 GHz；（2）memory-16.0 GB（15.7 GB 可用）；（3）operation system：windows10。实验中提出的 LPT 近似算法通过 Java 程序运行得到结果。
第6章 总结和展望
6.1总结
本文结合制造业转型升级的大背景，从实际的生产调度背景出发，进行了生产调度的优化与改进，研究了带有交货期的最大化提前完工总量的少量机器调度模型。由于本文所研究的问题是 NP-难问题，结合问题模型特点，采用了 LPT 近似算法，并研究了 m 台机器调度模型和两种少量机器模型下算法的最坏情况界，并得到了一些理论上的突破。与此同时，为了证明 LPT 近似算法对于所研究问题的实际适用性，结合了算例实验来佐证研究该问题的价值和意义以及近似算法的可行性和有效性。其主要内容如下：
（1）首先介绍了研究背景及意义，并总结了交货期、最小化误工损失以及最大化提前完工总量的研究现状，最后提出了本文所研究的基本问题。
（2）介绍了与本文相关的基本知识，包括组合优化和调度问题的相关知识及其求解方法等。然后具体介绍了 NP-hard 问题的概念及其求解思路和方法。最后介绍了本文采用的近似算法和求解
