本文是一篇工程硕士论文，笔者考虑多台机器的相关调度问题，在本文中我们研究的是单台机模型，可进一步研究多台机器的时间窗调度问题，多台机模型适合更大规模的生产问题，在现实中更具实用性，当然，问题的难度也会增大，多台机下我们的问题有可能是 NP 难的，因此我们可以设计相关近似算法或多项式算法对问题进行求解。
第1章 绪论
1.1 研究背景与意义
我国互联网与信息技术的发展催生了多样化，个性化的市场需求，这要求我国供应链生产向智能化，高效化转型升级。制造业处于供应链环节的上游，是供应链价值的源头和基础，然而近年来我国制造业人口红利消失，制造业发展成本难控制，供应链资金紧缺等问题层出不断，因此我国制造业急需转型升级，以应对不断变化的市场和愈加激烈的全球化竞争，柔性制造是精益生产的基础，不仅能帮助企业抵御来自市场变化的风险，对于提升供应链整体价值也具有重要意义。2020 年疫情爆发初期，口罩的需求量暴增，在原材料紧缺，各制造业春节还在停工的状态下，市场出现了严重的供不应求的局面，没有货物供应的情况下供应链难以实现其价值，一系列问题导致市场上出现口罩价格水涨船高而大部分地区依旧购买不到的局面。制造业信息与生产系统的搭建对于整个供应链的运作有着承上启下的作用，近年来国家不断作出向“中国智造”转型的指示，李克强总理提出中国制造 2025 要融合互联网，推动大众创新，万众创新，推进中国制造的智能转型，在云计算，AI 智能及 5G 技术环境下，用更高的制造业水准倒逼中国制造高质量发展。工业 4.0 的目标明确提出，“要满足用户的个性化需求，能够在设计、配置、排序、规划、制造和运行等阶段中纳入个性化的、用户特定的标准，并能够合并最后的修改”，以实现对时间、资源、成本、鲁棒性等的动态配置①。这也意味着供应链生产过程中要提升其流程的柔性以适应市场多变的需求，同时在制造业利润不断被压缩的情况下，加快由粗放型生产转变为集约型生产的步伐，减少资源浪费，改进效率低下，促进供应链整体价值的提升。要实现这些目标，背后依托的是先进的排序和算法及企业的生产调度技术，结合企业面临的实际问题挖掘模型，优化算法。
调度是运筹学重要的一部分，是离散优化中常见的一类问题，任何企业的制造生产都受到资源的限制，如何合理分配这些有限资源以达到某种目标是调度的本质目的。日常生产作业中许多流程可以简化为调度模型，例如在机场的跑道分配任务中，其跑道可视为资源，飞机的起飞与降落可视为任务，合理分配跑道保证飞机起飞降落效率是该模型的目标。同样，在车间工件的分配任务中，车间中的机器可视为资源，各个工件则为任务，目标可以是最小化任务的制造期或最大完工时间等。
............................
1.2 相关研究综述
1.2.1 时间窗调度研究现状
时间窗（Due-window）概念由到期日(Due-date)模型扩展而来,前者将交货时间设置为一段时间，后者将交货时间看作一个时间点，然而现实生活中许多交货行为并不是瞬时完成的，因此时间窗模型会更贴合现实生活中的生产情况。在时间窗模型中，交货时间早于时间窗开始时间会产生提前成本，例如仓储、管理费用，交货时间晚于时间窗会产生延误罚金，甚至会产生影响企业信誉的隐形成本，在时间窗内完成的货物不产生任何罚金。时间窗概念最早由 Anger 等（1986）提出，其目标是最小化时间窗外完成的工件数， Krämer 等（1993）以最小化提前成本和延迟罚金为目标，分别研究了时间窗为决策变量和既定参数两种模型，并为前者提供了一个O(nlog n) 的多项式算法，为后者提供了伪多项式动态规划算法。Liman 等（1998）在 Krämer 等人的基础上将规划目标扩展为最小化提前成本，延后罚金，时间窗开始时间成本及时间窗尺寸成本之和，如今该目标被广泛应用于时间窗模型中。在相同目标下，Mosheiov 等（2009）考虑将速率维修活动（Rate-modifying activity，简称 RMA）纳入时间窗模型中，并给出了多项式时间算法。执行 RMA 需要占用机器一段时间，执行后可提升机器加工效率，除了安排最优工件序列及时间窗位置，还要求解出最适当的 RMA 位置。
一般情况下，调度中订单数或待加工工件数是固定已知的，而现实生活中制造商碰到自己无法完成的订单是可以选择外包加工的，例如出现模具不符，利润不理想等情况，在这种情况下，最终加工的订单数或工件数是需要讨论的。调度领域中很多学者用工件拒绝定义订单外包，因为在数学模型中，拒绝与外包都意味着企业自身不需要加工该订单，并且需要支付额外的费用。早在 1996 年 Bartal 等（1996）便考虑了带拒绝的平行机调度问题，每个工件都有其相应的拒绝成本，目标是最小化加工工件的制造期（maxC ）和被拒绝工件的罚金，该文章考虑了离线调度和在线调度两个版本。
................................
第2章 相关理论介绍
2.1 调度问题概念
调度又称为排序问题，指在一定机器环境中，受到某些约束的条件下，完成特定的任务，机器环境可以是单台机器，多台平行机，并行机等，约束条件可以是加工时间变动，资源分配，工件外包等，常见的任务目标有制造期，完工时间，调度作为一种决策过程，在生产和服务业中有着重要意义且被广泛应用（Michael，2018）。调度问题分类可见表 2-1。
工程硕士论文怎么写
本文中，我们的问题是确定的，静态的，研究单机环境下工件各信息已知的调度问题。接下来，我们将介绍调度中常见的符号及其定义。
..........................
2.2 符号及定义
调度问题基本用三参数法来表示，三参数法最早由 Graham 等（1979）提出，形如|| ，其中 ， ， 分别表示机器环境（Machine environment），加工约束条件（Processing characteristics），和目标函数（Optimality criteria），这三种参数的不同组合可以表示不同的调度问题，接下来我们介绍调度领域中常见的机器环境，加工约束及目标函数。
工程硕士论文怎么写
.........................
第 3 章 相关新模型介绍及简单问题求解 .................................... 21
3.1 工件加工基于工件外包、位置、资源分配的调度问题 ....................................... 21
3.1.1 引言 ................................. 21
3.1.2 极小化最大完工时间及资源分配，外包成本 ............................ 21
第 4 章 考虑外包和维修活动的公共时间窗调度模型 ........................... 27
4.1 引言 ........................................ 27
4.2 问题描述 .................................... 27
4.3 前提条件分析 ..................................... 31
第 5 章 考虑外包和维修活动的松弛时间窗调度模型 ................................. 45
5.1 引言 ............................................. 45
5.2 问题描述 .......................................... 45
5.3 前提条件分析 ................................. 48
第6章 数据实验
6.1 算例介绍
本章节将提供一个包含 7 个工件的算例来解释前文给出的算法，我们将用 Python 去完成这一实验过程。
工件的原始加工时间，老化因子，正压缩率，修正率，单位资源成本，外包成本以及线性资源分配下资源上限均列于表 6-1。
工程硕士论文参考
生产过程中各成本为： 提前完工成本???? = 6，延误成本???? = 25，时间窗开始时间成本???? = 8，时间窗尺寸成本???? = 10。我们设速率维修活动（RMA）的固定时长是 22，其恶化系数为 0.2，资源去量纲系数???? = 0.75。凸资源函数中的常数???? = 1。
..............................
第7章 总结与展望
7.1 研究总结
本文提出了基于时间窗调度的新模型，为了贴近现实生活中的制造环境，我们做出了工件可以外包的假设，并考虑基于位置及工件本身的老化效应，管理者可以安排速率维修活动调整机器状态，提升加工速率，同时可以为工件配置额外的资源，缩减工件加工时间。我们要联合找到最优的企业内加工工件集合以及这些工件的最优排序，时间窗的位置（松弛时间窗模型下求公共流量），速率维修活动的位置以及企业内加工工件的资源配置，从而最小化时间窗下工件的提前成本，延误罚金，时间窗开始时间成本及尺寸，资源配置成本以及外包成本之和。我们分别研究了公共时间窗和松弛时间窗两种模型，其中公共时间窗中所有工件共用同一个时间窗，松弛时间窗中每个工件都有自己的时间窗，同时我们又将资源分配分为线性资源函数与凸资源函数分别研究，线性资源分配模型中工件加工时间随分配的资源线性递减，而凸资源函数可以反映资源分配的边际递减效应，这四种假设形成了本文四种模型，反映了准时制制造中不同的生产细节。
本文首先对准时制背景环境做了大致分析，并通过国内外文献综述介绍了调度领域中时间窗模型，工件外包，以及影响工件加工时间的多种因素的研究发展，在此基础上形成本文的研究框架与内容。我们在第二章介绍了有关调度的概念及基础知识，算法复杂性相关理论，并介绍了指派问题与匈牙利算法，给出了匈牙利算法的算例解析，为后文相关分析技术做理论介绍，在第二章的基础上，我们给出了与本文相关的简单调度模型分析，我们研究了单台机上考虑老化效应，资源分配以及工件可外包的调度模型 ，目标为最小化制造期( )maxC 及资源分配成本，外包成本，给出了模型的算法及分析，在第四章与第五章提出时间窗的模型，结合上一章中工件外包，老化效应，资源分配的因素，并考虑安排维修速率活动，形成本文重点研究的时间窗调度新模型，给出了相应的理论分析与算法设计，在第六章对这些模型进行算例求解，我们用包含 7 个工件的算例去分别演示文章提出的四个时间窗模型，分别为公共时间窗下考虑线性资源分配的模型，公共时间窗下考虑凸资源分配的模型，松弛时间窗下考虑线性资源分配的模型以及松弛时间窗下考虑凸资源分配的模型。我们通过 Python 实现对模型的建立以及算例求解，并在最终结果中得出相应的启发与结论，以为现实中的生产调度工作提供建设性意见，提高制造业的生产柔性，缩减生产过程中的成本并保证效率。
参考文献（略）