摘  要：在实际生产应用中，存在很多需要在规定时间内完成的复杂任务，任务的持续时间、任务之间的先后顺序、任务的优先级等都导致任务规划的过程存在困难。该文提出一种任务规划过程，对给定的具有优先级、时间约束条件的任务实现任务规划过程，达到任务总耗时最小的目标。ILOG公司提供的CPLEX可以用于解决多种线性规划问题。采用ILOG优化引擎嵌套VC来实现任务规划过程的算法。

关键词：ILOG CPLEX;任务规划;线性规划

中图分类号：TP319      文献标识码：A 文章编号：2096-4706（2020）17-0152-03

Abstract：In actual production applications，there are many complex tasks that need to be completed within the specified time. The duration of tasks，the sequence of tasks，and the priority of tasks all make the process of task planning difficult. This paper proposes a task planning process to achieve the task planning process for a given task with priority and time constraints，and achieve the goal of minimizing the total time-consuming task. CPLEX provided by ILOG can be used to solve a variety of linear programming problems. Use ILOG optimization engine nested VC to realize the algorithm of task planning process.

Keywords：ILOG CPLEX;task planning;linear programming

0  引  言

目前，在企業的实际生产设计过程中，往往需要解决规模很大的问题，同时在任务实施过程中人力、资源、时间等条件因素是有穷的。单纯依靠人工进行协调安排是不切实际的，并且也容易出错，而一般的任务规划过程解决问题的过程比较烦琐，同时使用起来也不够灵活，所以对任务规划过程提出了更高的要求。无锡某RFID智能标签制造公司在生产RFID智能标签的过程中，由于在生产之前没有对所有任务进行合理的规划，导致出现不能按时完成生产任务、生产资源浪费等现象。因此委托我校物联网学院基础部团队针对其公司的各项生产任务进行生产前的任务规划，由该公司给出任务优先级、时间约束以及各个任务之间的关系，通过任务规划过程，判断出每个生产任务的开始和结束时间以达到生产总时间的最优化，解决生产任务不能按时完成的问题。

本文提出了一种基于ILOG CPLEX的任务规划过程的设计与实现。将企业生产任务的输入信息以XML文件的形式来进行描述，描述内容包括任务起始时间、持续时间、结束时间、任务关系、任务优先级等;将这些描述构建成数学线性规划的模型，求解任务总耗时最短的优化方案，为任务实施提供决策支持。

线性规划[1]是运筹学中广泛应用、发展迅速并且方法比较成熟的一个分支，在经济管理、工农业生产、交通运输等重要经济活动中，辅助决策者进行科学管理。可以用线性方程、不等式进行规划，将约束条件组合构建数学线性规划模型，求解最优解。

本文提出的任务规划过程是通过ILOG优化引擎嵌套VC来实现的。由于时间约束等条件可能使任务规划过程中存在冲突导致优化方案无解。在进行任务规划之前先对任务实行冲突检测，若未检测到冲突则给出任务规划结果，若检测到冲突则直接退出任务规划过程。

1  ILOG CPLEX介绍

ILOG CPLEX是一种优化程序，其提供了解决实际大型优化问题所需的能力，同时具有当下交互应用程序所需的速度。ILOG CPLEX能够以最快的速度最可靠地实现基本算法，以解决困难的数学优化问题。ILOG CPLEX提供灵活的高性能优化程序，解决线性规划（Linear Programming）、二次方程规划（Quadratic Programming）、二次方程约束规划（Quadratically Constrained Programming）和混合整数规划（Mixed Integer Programming）问题[2]。

Concert技术：ILOG CPLEX提供了C++、JAVA、.NET等编程语言实现的算法库支持。基于此技术ILOG CPLEX可以嵌套在多种语言编写的程序中使用。

本文提出的任务规划过程就是使用C++语言编写的User-Written应用程序，然后通过Concert技术与ILOG CPLEX对象构建连接求解优化结果。IloCplex对象是ILOG CPLEX优化软件用来定义优化模型对象的。一个IloCplex对象从CPLEX优化器中读取一个模型并提取出数据。然后由IloCplex对象提取和查询信息解决方案返回给User-Written应用。具体结构图如图1所示。

利用ILOG CPLEX求解线性规划问题的一般步骤如下[3]：

（1）定义环境变量、模型、变量数组和约束条件数组。通过IloEnv创建环境变量，通过IloModel创建模型，通过IloNumVarArry创建变量数组，通过IloRangeArrary创建约束条件数组。

（2）向变量数组中添加变量。明确问题中的变量以及变量的界限，然后添加到变量数组中。

（3）向约束条件数组中添加约束条件。将问题中的约束条件添加到约束条件数组中，然后把约束条件数组添加到模型。

（4）设置求解目标。为构建的模型设置求解目标。

（5）求解。定义基于该模型的IloCplex对象cplex，调用cplex.solve（）方法，通过返回值确定是否找到最优解。通过cplex.getObjValue（）来获取目标变量值。

2  设计与实现

2.1  整体设计

实际生产应用中需要完成的任务往往比较复杂，我们在设计实现中将其分解为若干个简单任务，这些任务本身存在时间约束、优先级约束，任务之间存在着关系约束，下文對各个约束条件进行分析。

2.1.1  时间约束条件

任务的时间约束条件可能包括：任务的开始时间、任务结束时间、任务最长持续时间、任务最短持续时间。根据实际生产应用中的任务的实际情况来定义此时间约束条件。

2.1.2  优先级约束条件

实际任务规划过程中，各个任务本身可能存在着优先级的差别，有些任务的优先级最高，必须首先完成，其他任务才可以进行实施。本文中将任务的优先级以0～9这十个符号来表示优先级的高低，0表示优先级最高，9表示优先级最低，0～9优先级依次降低。

2.1.3  关系约束条件

被分解出来的子任务，他们的执行过程可能是串行，绝大部分情况下也可以是并行的，那么并行过程中，某两个任务之间就存在着一定的关系约束条件。本过程中用“BB”、“BE”、“EB”、“EE”四种类型来表示关系约束的类型。具体描述为（假设某两个任务的任务名分别为“任务一”和“任务二”）：

（1）BB：任务一开始之后任务二开始;

（2）BE：任务一开始之后任务二结束;

（3）EB：任务一结束之后任务二开始;

（4）EE：任务一结束之后任务二结束。

整个规划过程的优化目标是要求完成整个任务的时间最小化，求解每个子任务的开始及结束时间。

此任务规划[4]过程的设计结构：首先输入XML文件存储的任务信息，此任务信息包括任务本身的时间、优先级约束及任务之间的关系信息;接着预处理输入信息，将其描述为ILOG CPLEX可识别的语言;然后调用ILOG CPLEX对数据进行优化求解;最后将优化的结果即各个子任务的开始、结束时间写入XML文件保存。

2.2  输入

任务的信息以一个XML文件来存储，该文件的结构图如图2所示，该文件是以树结构来存储数据的。任务树的根节点名称为任务规划根节点，对一个任务的描述包括原点情况、任务情况和任务关系。原点情况下的原点的属性值原点时间描述的是一个时间值，本文描述的时间值都是在该原点时间基础上发生的偏移量，偏移量的单位为秒。任务情况可能包含若干个任务，每个任务的属性包括任务编号、任务名称、任务级别（0～9）、开始时间、结束时间、最短持续时间、最长持续时间。任务关系描述两个任务之间的关系，其可包含多个关系，每个关系包含的属性包括任务一编号、任务二编号、关系类型（“BB”、“BE”、“EB”、“EE”）、时间差（两个任务关系之间相差的时间）。

2.3  输出

将任务规划过程得到的结果进行输出，存在冲突则输出冲突信息，不存在冲突则将每个子任务的开始、结束时间写入XML文件，文件的数据形式与输入相同。

2.4  ILOG CPLEX实现过程

本文以一个具体的实例来说明任务规划的具体实现过程。表1和表2分别是对各个子任务的信息描述及某两个任务之间的关系描述。

2.4.1  数据预处理

例：表1中任务A的最短持续时间是10 s，最长持续时间为50 s，则可以列出：10<=A.end-A.begin<=50;已知任务A的开始时间，可以列出A.begin=0;已知任务A的优先级为0，则可以列出A.priority=0;同理任务B的已知情况也可以列出约束条件。

表2中任务A和任务B之间存在“EB”的关系约束，时间差为0 s，则可以列出：B.begin-A.end=0。

2.4.2  优化目标

求解所有子任务的最大完成时间与最小开始时间之差的最小值，即最短任务完成时间：Minimize（Max{A.end，B.end}-Min{A.begin，B.begin}）

2.4.3  调用ILOG CPLEX优化

调用IloCplex：：sovle（）方法优化求解整个过程，得到任务完成的最短时间minT。若优化过程出错，则返回错误代码false，正常情况返回true。

2.4.4  新增优化条件

新增优化条件，求解完成所有任务所需要的最短时间minT：

Minimize（Max{A.end，B.end}-Min{A.begin，B.begin}）= minT

2.4.5  设定新的优化目标

求解所有优先级为0的任务完成的最短时间：

Minimize（Max{A.end}-Min{A.begin}）

求解出结果min0，将等式代入优化条件，继续求解优先级为1的任务完成最短时间，即Minimize（Max{B.end}-Min{B.begin}）的最优结果min1，按此方法直到所有优先级的任务时间都计算完成[5]。

2.4.6  求解出结果

表3中显示的是最终任务规划的结果，结果显示该优化过程可以实现，最终任务编号为YQ202003的任务A在0 s开始，持续10 s结束，紧接着任务编号为YQ202004的任务B开始执行，持续时间为190 s，在200 s的时候整个任务结束。

3  结  论

本文主要介绍了一种基于ILOG CPLEX的任务规划过程的设计与实现，它是用户通过在VC环境下编写C++程序，连接CPLEX优化引擎进行对象优化求解的一个过程。求解的是在任务时间条件、优先级条件具有一定约束条件的情况下，如何实现最终完成任务的总时间最短的问题。通过本文研究，可以发现利用ILOG CPLEX来解决任务规划的问题效率非常高，在某些制造企业的实际的生产应用中具有重要意义，可以提高制造企业的生产效率。

参考文献：

[1] 雷婕.线性规划最优解在企业生产管理决策中的应用 [J].企业技术开发，2019，38（3）：98-102.

[2] 刘盛铭，冯书兴.基于CPLEX的航天试验项目管理应用 [J].装甲兵工程学院学报，2015，29（5）：89-93.

[3] 鲁奎，杨昌辉，戴道明.能力受限批量问题的启发式算法与CPLEX仿真优化 [J].系统仿真学报，2008，20（23）：6365-6368+6371.

[4] 韦东鑫.用于线性规划的诊断与决策可视化 [J].现代计算机，2020（8）：26-29.

[5] 张智聪.ILOG OPL优化软件及其教学工作探讨 [J].科技信息，2009（22）：186-187.

作者简介：郑雅倩（1988—），女，汉族，江苏连云港人，助教，硕士，研究方向：模式识别、机器学习。