基于OPL的带资源的计划优化方法研究与实践

杨伟宏、王易南、徐珊珊、岳晓飞、王晓鹏 /北京宇航系统工程研究所

型号研制计划是航天工程管理重要的表征形式，是保证型号研制能否按期保质完成的重要指导性文件，在型号研制管理中占有特殊的地位。型号研制计划规定了各参研、参制单位研制任务的逻辑顺序、任务和资源的关联关系以及工期要求，是在型号研制过程中开展指挥、控制、评价等管理工作的主要依据和基准。因此，航天型号管理的本质是围绕研制计划的管理，必须以型号研制计划为纲，才能抓住型号管理的主线，做到纲举目张。

型号研制计划受到各种技术以及技术研发进展的影响，当在新技术应用或技术实现过程中出现各种可能或矛盾时，必然影响研制计划全局，如有些重要的计划安排有可能因为总体技术状态的改变而需要重新调整。与人类认识世界的过程一样，技术实现过程也是一个循环往复的过程，型号研制计划虽然在执行过程中具有一定的强制性，但与对客观世界的认识过程是统一的、目标是一致的，其复杂性和动态性就表现在技术实现过程与最终目标的不断折衷。因此，在型号研制过程中型号研制计划需要不断调整，而这种调整是客观的，也是必要的。正是由于型号研制计划在航天型号管理中的重要作用，以及其特有的复杂性、动态性，使得在实际计划管理中急需一种既能反映计划各个任务之间的逻辑关系，又能反映资源配置使用情况的管理工具和方法。

一、带资源的计划优化的必要性和理论依据

1.计划优化的必要性

按照项目管理理论，开展航天型号研制计划管理是一个复杂的网络体系。各研制任务之间的关系不仅是一套时间进度管理的关系，也是一套资源配置管理的关系。 同 时，要特别体现研制任务之间的逻辑关系，借以控制和跟踪技术状态变化。这些关系有的可以与时间进度关系重合，有的则仅仅是在单个计划任务上才能结合在一起，共同形成多重网络。在经典项目管理中，关键路径是指直接影响项目最终完成时间的任务集合，而在型号实际管理过程中关键路径有时是多重的。确定关键路径，不但要从时间进度关系上考虑，还要从技术风险上考虑。此外，在不同节点中改变计划任务的某一个属性或数值时，很可能影响与之有关的下游任务是否还是关键路径、影响其他任务的资源是否能够按期投入使用等。

编制计划应当客观准确地反映型号研制实际，不能脱离实际以人为主观因素或要求编制计划。特别是各承研、承制单位的型号研制计划，由于涉及的专业繁杂，必须全面统筹考虑各种要素才能编制出系统、科学、可行的计划。

当前，各承研、承制单位大都面临多型号并举的实际情况，在实际型号研制活动中资源争夺现象比较普遍，同一个资源被多个型号使用，如试验场地会发生冲突、主要设计人员的时间分配出现“撞车” 等，进而导致资源不足或资源冲突等问题，这些是计划执行不力引发计划调整最常见也是最主要的原因。因此，计划管理中有效的资源配置和平衡管理能力已经成为确保计划完成的决定性因素，如何实现带资源的计划优化是型号研制计划管理中亟待解决的问题。

这些关系有的可以与时间进度关系重合，有的则仅仅是在单个计划任务上才能结合在一起，共同形成多重网络。在经典项目管理中，关键路径是指直接影响项目最终完成时间的任务集合，而在型号实际管理过程中关键路径有时是多重的。确定关键路径，不但要从时间进度关系上考虑，还要从技术风险上考虑。此外，在不同节点中改变计划任务的某一个属性或数值时，很可能影响与之有关的下游任务是否还是关键路径、影响其他任务的资源是否能够按期投入使用等。

2.调度优化理论

计划优化属于现代运筹学的调度问题。调度是指考虑随时间的变化，如何安排有限的资源在执行任务的同时满足特定的约束。调度问题分为作业车间调度问题、群体作业调度问题、并行机床调度问题、资源约束的项目调度问题和多处理器调度问题等几个大类。

调度问题一般采用三段式的描述方法，即α/β/γ的表达方式，α表示机床的环境或资源的环境因素，β表示过程和约束的情况，γ表示优化的目标是什么。

根据算法理论，对复杂算法的难度采用是否在一定限制下完成计算作为衡量，即存在一个多项式函数g(x)， 如 果复杂问题的算法在该多项式描述的时间内完成计算，则称该算法为解决该问题的多项式时间算法，该问题则被称为多项式时间可解问题。多项式函数增长的速度比指数函数增长的速度慢得多，因此如果能够证明一个问题存在算法，且算法是多项式算法，则认为该算法是高效的，此问题也被称为P 问题。

NP 问题：可以在多项式时间内验证某个解是否合法，但不能确定存在多项式算法的问题。

NP 难问题：如果对于某个问题X，任意NP 问题Y，都有YocpolyX（X 比Y 难）， 则X 是NP 难问题(比NP 问题难，但不是NP 问题)。

NP 完全问题：如果问题是NP 难问题，且它是一个NP 问题。

实际中，典型的NP 完全问题有着色问题、TSP、划分问题、作业车间调度问题等几种。经证明，带资源的计划优化问题也属于NP 完全问题。

二、带资源的计划优化模型与解决方法

1.带资源的计划优化模型

带资源的计划优化问题在调度理论中表示为Pm/prec，multi-s，Pij=PJ/Cmax。 其 中，Pm表示多项目，prec表示具有紧前关系，s为单项任务需要资源的最大的项数。

具体数学模型为：

j为任务数，Pij为第i个资源加工第j个任务的工期，这里要求Pij=PJ，即所有资源对同一任务的工期是一样的。Rj为任务j的使用资源集合，D为紧前、紧后关系集合。优化目标是最大完成时间（makespanCmax）最小。

2.计划优化的实现

运筹学在20 世纪40 年代出现以来，经过科技工作者的不断完善已经成为具有完整理论体系的庞大理论体系。近几十年各种优化算法不断涌现，在国际、国内科研生产和经济管理等各个方面取得了大量成果，如广泛用于科研管理的优化算法主要有线性规划方法、动态规划方法、组合优化方法等。同时，面对市场的强烈需求，市面上发布了许多有效的计算工具和软件系统，为实际应用提供了强大的支撑。

Ilog 公司是国外一家专业从事优化计算系统开发的公司，旗下有一系列产品。OPL studio（简称OPL）是一个集成环境的优化计算系统，能够解算线性规划、整数规划、混合整数规划等问题，其核心是Complex 优化模块。该软件拥有其他软件没有的Activity 对象，该对象专门用来进行计划和高级排产问题（APS）的建模，能够充分体现项目的特点，便于使用。此外，与该对象相关的资源类型的定义，项目之间紧前、紧后关系的定义等均非常独特，大大简化了计划优化问题建模的难度。另外，OPL 同样可以和数据库系统接口，方便模型与数据的对接。

使用OPL 语言明确优化目标、约束条件、任务和资源的关系，就完成了模型的构建。

三、带资源的计划优化应用效果

1.数据模型

在实际应用中，选择一个具有代表性的某型号的某项研制任务的研制计划进行优化计算。该计划被分解成59 项子任务（其中一项为里程碑计划），资源共有4 类、12 个，其中总设计师（正副）2 人（ZS1、ZS2）、总体设计师4 人（ZT1-ZT4）、结构设计师4 人(JG1-JG4)、电气设计师3 人(DQ1-DQ2)。根据实际型号研制规律和流程，计划中各个子任务满足一定的紧前、紧后关系。在计划的中期设置了初样评审任务，作为计划中期的检查节点。

按照优化模型的要求，每个子任务具有明确的工期，子任务之间存在紧前、紧后的关系，关系由数据结构表示。此外，共有4 类资源，资源和子任务之间的映射关系通过数据结构表示，每个子任务使用2 类或2 类以上的资源配合完成。资源属于唯一型资源，即在同一时间内不能被2个子任务同时使用。

2.计划优化计算过程与结果应用

首先，按照常规的依据主观经验的方法编制计划，只考虑任务之间的逻辑关系，不考虑资源配置等情况，制定的计划总工期为700 天，如图1 所示。但是该计划包含大量的资源冲突问题，如ZT3 的资源需求将超过其能力的300%，如图2 所示。

图1 某研制计划甘特图

图2 资源冲突示意图

经过OPL 系统优化计算，系统通过调整子任务的开始时间，各项资源在时间轴上没有冲突，给出了817 天的优化计算结果，如图3 所示，优化后的计划比原计划更具有科学性和合理性。

从优化计算结果中可以看到，虽然优化后总工期比优化前延长了117 天，但各个子任务和资源（本模型为双资源）的匹配关系，以及任务之间的紧前、紧后的逻辑关系，资源的约束关系全部都得到了满足。计划优化前，各个子任务的工期都是理想状态，资源配置情况也是如此，但是在实施过程中由于实际执行情况千变万化，工期和资源配置发生变化是必然的，因此可以将初步优化后的计划视为项目的计划基线。

图3 优化后与优化前对比

从优化计算结果中还可以得到各个资源的使用情况（资源负载率）。12 个资源（列中的单元）均按照要求承担不同的子任务，其中资源ZT1 和资源DQ2 工作最饱满，这就是计划实施中的关键资源（不一定是关键链上的资源）。对于任务不饱满的资源，也明确地给出了空闲时间，在计划实施中可以在其空余时间段调配去承担其他任务。

如果通过调整资源配置，增加关键资源的投入（增加ZT 和DQ 类资源的数量），减少任务不饱满资源，再经过优化计算，势必会进一步缩短总工期。如果再将多个项目计划进行联合优化计算，将本项目空闲的资源提供给其他需要该项资源的项目，从其他项目中争取到本项目继续的关键资源，计划优化的效果将会更加明显。因此，通过OPL 系统优化计算，不但可以帮助管理者科学编制计划，而且还可以制定资源调整配置的策略，进而通过调整资源配置及资源和任务的关系，逐步逼近理想的工作目标。

后续，在型号研制计划的大规模实践中将会遇到计算量达十万级和百万级的优化项目，这就需要有更加强大的计算引擎完成计算。目前，资源与子任务之间是按照唯一型关系设定的，在实践工作中还会遇到总量约束型、能力恢复型等多种匹配类型的资源，需要进一步研究新的更加高效的模型和算法。此外，还需要关注计划管理的复杂性和动态性，临时性任务和资源配置需求在实际工作中会不时出现，各任务计划完成时间也会出现一定的偏差，这就需要建立一个有效的信息采集机制，及时采集资源管理和计划实施过程中的各种信息，并通过OPL 系统完成优化计算，不断完善制定最优的调度方案，而开展这些工作需要从组织层面建立健全完善的规章制度和精细化的工作流程。▲