摘? 要：在實際生產應用中，存在很多需要在規(guī)定時間內完成的復雜任務，任務的持續(xù)時間、任務之間的先后順序、任務的優(yōu)先級等都導致任務規(guī)劃的過程存在困難。該文提出一種任務規(guī)劃過程，對給定的具有優(yōu)先級、時間約束條件的任務實現(xiàn)任務規(guī)劃過程，達到任務總耗時最小的目標。ILOG公司提供的CPLEX可以用于解決多種線性規(guī)劃問題。采用ILOG優(yōu)化引擎嵌套VC來實現(xiàn)任務規(guī)劃過程的算法。

關鍵詞：ILOG CPLEX;任務規(guī)劃;線性規(guī)劃

中圖分類號：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? 引? 言

目前，在企業(yè)的實際生產設計過程中，往往需要解決規(guī)模很大的問題，同時在任務實施過程中人力、資源、時間等條件因素是有窮的。單純依靠人工進行協(xié)調安排是不切實際的，并且也容易出錯，而一般的任務規(guī)劃過程解決問題的過程比較煩瑣，同時使用起來也不夠靈活，所以對任務規(guī)劃過程提出了更高的要求。無錫某RFID智能標簽制造公司在生產RFID智能標簽的過程中，由于在生產之前沒有對所有任務進行合理的規(guī)劃，導致出現(xiàn)不能按時完成生產任務、生產資源浪費等現(xiàn)象。因此委托我校物聯(lián)網(wǎng)學院基礎部團隊針對其公司的各項生產任務進行生產前的任務規(guī)劃，由該公司給出任務優(yōu)先級、時間約束以及各個任務之間的關系，通過任務規(guī)劃過程，判斷出每個生產任務的開始和結束時間以達到生產總時間的最優(yōu)化，解決生產任務不能按時完成的問題。

本文提出了一種基于ILOG CPLEX的任務規(guī)劃過程的設計與實現(xiàn)。將企業(yè)生產任務的輸入信息以XML文件的形式來進行描述，描述內容包括任務起始時間、持續(xù)時間、結束時間、任務關系、任務優(yōu)先級等;將這些描述構建成數(shù)學線性規(guī)劃的模型，求解任務總耗時最短的優(yōu)化方案，為任務實施提供決策支持。

線性規(guī)劃[1]是運籌學中廣泛應用、發(fā)展迅速并且方法比較成熟的一個分支，在經(jīng)濟管理、工農業(yè)生產、交通運輸?shù)戎匾?jīng)濟活動中，輔助決策者進行科學管理。可以用線性方程、不等式進行規(guī)劃，將約束條件組合構建數(shù)學線性規(guī)劃模型，求解最優(yōu)解。

本文提出的任務規(guī)劃過程是通過ILOG優(yōu)化引擎嵌套VC來實現(xiàn)的。由于時間約束等條件可能使任務規(guī)劃過程中存在沖突導致優(yōu)化方案無解。在進行任務規(guī)劃之前先對任務實行沖突檢測，若未檢測到?jīng)_突則給出任務規(guī)劃結果，若檢測到?jīng)_突則直接退出任務規(guī)劃過程。

1? ILOG CPLEX介紹

ILOG CPLEX是一種優(yōu)化程序，其提供了解決實際大型優(yōu)化問題所需的能力，同時具有當下交互應用程序所需的速度。ILOG CPLEX能夠以最快的速度最可靠地實現(xiàn)基本算法，以解決困難的數(shù)學優(yōu)化問題。ILOG CPLEX提供靈活的高性能優(yōu)化程序，解決線性規(guī)劃（Linear Programming）、二次方程規(guī)劃（Quadratic Programming）、二次方程約束規(guī)劃（Quadratically Constrained Programming）和混合整數(shù)規(guī)劃（Mixed Integer Programming）問題[2]。

Concert技術：ILOG CPLEX提供了C++、JAVA、.NET等編程語言實現(xiàn)的算法庫支持?；诖思夹gILOG CPLEX可以嵌套在多種語言編寫的程序中使用。

本文提出的任務規(guī)劃過程就是使用C++語言編寫的User-Written應用程序，然后通過Concert技術與ILOG CPLEX對象構建連接求解優(yōu)化結果。IloCplex對象是ILOG CPLEX優(yōu)化軟件用來定義優(yōu)化模型對象的。一個IloCplex對象從CPLEX優(yōu)化器中讀取一個模型并提取出數(shù)據(jù)。然后由IloCplex對象提取和查詢信息解決方案返回給User-Written應用。具體結構圖如圖1所示。

利用ILOG CPLEX求解線性規(guī)劃問題的一般步驟如下[3]：

（1）定義環(huán)境變量、模型、變量數(shù)組和約束條件數(shù)組。通過IloEnv創(chuàng)建環(huán)境變量，通過IloModel創(chuàng)建模型，通過IloNumVarArry創(chuàng)建變量數(shù)組，通過IloRangeArrary創(chuàng)建約束條件數(shù)組。

（2）向變量數(shù)組中添加變量。明確問題中的變量以及變量的界限，然后添加到變量數(shù)組中。

（3）向約束條件數(shù)組中添加約束條件。將問題中的約束條件添加到約束條件數(shù)組中，然后把約束條件數(shù)組添加到模型。

（4）設置求解目標。為構建的模型設置求解目標。

（5）求解。定義基于該模型的IloCplex對象cplex，調用cplex.solve（）方法，通過返回值確定是否找到最優(yōu)解。通過cplex.getObjValue（）來獲取目標變量值。

2? 設計與實現(xiàn)

2.1? 整體設計

實際生產應用中需要完成的任務往往比較復雜，我們在設計實現(xiàn)中將其分解為若干個簡單任務，這些任務本身存在時間約束、優(yōu)先級約束，任務之間存在著關系約束，下文對各個約束條件進行分析。

2.1.1? 時間約束條件

任務的時間約束條件可能包括：任務的開始時間、任務結束時間、任務最長持續(xù)時間、任務最短持續(xù)時間。根據(jù)實際生產應用中的任務的實際情況來定義此時間約束條件。

2.1.2? 優(yōu)先級約束條件

實際任務規(guī)劃過程中，各個任務本身可能存在著優(yōu)先級的差別，有些任務的優(yōu)先級最高，必須首先完成，其他任務才可以進行實施。本文中將任務的優(yōu)先級以0～9這十個符號來表示優(yōu)先級的高低，0表示優(yōu)先級最高，9表示優(yōu)先級最低，0～9優(yōu)先級依次降低。

2.1.3? 關系約束條件

被分解出來的子任務，他們的執(zhí)行過程可能是串行，絕大部分情況下也可以是并行的，那么并行過程中，某兩個任務之間就存在著一定的關系約束條件。本過程中用“BB”、“BE”、“EB”、“EE”四種類型來表示關系約束的類型。具體描述為（假設某兩個任務的任務名分別為“任務一”和“任務二”）：

（1）BB：任務一開始之后任務二開始;

（2）BE：任務一開始之后任務二結束;

（3）EB：任務一結束之后任務二開始;

（4）EE：任務一結束之后任務二結束。

整個規(guī)劃過程的優(yōu)化目標是要求完成整個任務的時間最小化，求解每個子任務的開始及結束時間。

此任務規(guī)劃[4]過程的設計結構：首先輸入XML文件存儲的任務信息，此任務信息包括任務本身的時間、優(yōu)先級約束及任務之間的關系信息;接著預處理輸入信息，將其描述為ILOG CPLEX可識別的語言;然后調用ILOG CPLEX對數(shù)據(jù)進行優(yōu)化求解;最后將優(yōu)化的結果即各個子任務的開始、結束時間寫入XML文件保存。

2.2? 輸入

任務的信息以一個XML文件來存儲，該文件的結構圖如圖2所示，該文件是以樹結構來存儲數(shù)據(jù)的。任務樹的根節(jié)點名稱為任務規(guī)劃根節(jié)點，對一個任務的描述包括原點情況、任務情況和任務關系。原點情況下的原點的屬性值原點時間描述的是一個時間值，本文描述的時間值都是在該原點時間基礎上發(fā)生的偏移量，偏移量的單位為秒。任務情況可能包含若干個任務，每個任務的屬性包括任務編號、任務名稱、任務級別（0～9）、開始時間、結束時間、最短持續(xù)時間、最長持續(xù)時間。任務關系描述兩個任務之間的關系，其可包含多個關系，每個關系包含的屬性包括任務一編號、任務二編號、關系類型（“BB”、“BE”、“EB”、“EE”）、時間差（兩個任務關系之間相差的時間）。

2.3? 輸出

將任務規(guī)劃過程得到的結果進行輸出，存在沖突則輸出沖突信息，不存在沖突則將每個子任務的開始、結束時間寫入XML文件，文件的數(shù)據(jù)形式與輸入相同。

2.4? ILOG CPLEX實現(xiàn)過程

本文以一個具體的實例來說明任務規(guī)劃的具體實現(xiàn)過程。表1和表2分別是對各個子任務的信息描述及某兩個任務之間的關系描述。

2.4.1? 數(shù)據(jù)預處理

例：表1中任務A的最短持續(xù)時間是10 s，最長持續(xù)時間為50 s，則可以列出：10<=A.end-A.begin<=50;已知任務A的開始時間，可以列出A.begin=0;已知任務A的優(yōu)先級為0，則可以列出A.priority=0;同理任務B的已知情況也可以列出約束條件。

表2中任務A和任務B之間存在“EB”的關系約束，時間差為0 s，則可以列出：B.begin-A.end=0。

2.4.2? 優(yōu)化目標

求解所有子任務的最大完成時間與最小開始時間之差的最小值，即最短任務完成時間：Minimize（Max{A.end，B.end}-Min{A.begin，B.begin}）

2.4.3? 調用ILOG CPLEX優(yōu)化

調用IloCplex：：sovle（）方法優(yōu)化求解整個過程，得到任務完成的最短時間minT。若優(yōu)化過程出錯，則返回錯誤代碼false，正常情況返回true。

2.4.4? 新增優(yōu)化條件

新增優(yōu)化條件，求解完成所有任務所需要的最短時間minT：

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

2.4.5? 設定新的優(yōu)化目標

求解所有優(yōu)先級為0的任務完成的最短時間：

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

求解出結果min0，將等式代入優(yōu)化條件，繼續(xù)求解優(yōu)先級為1的任務完成最短時間，即Minimize（Max{B.end}-Min{B.begin}）的最優(yōu)結果min1，按此方法直到所有優(yōu)先級的任務時間都計算完成[5]。

2.4.6? 求解出結果

表3中顯示的是最終任務規(guī)劃的結果，結果顯示該優(yōu)化過程可以實現(xiàn)，最終任務編號為YQ202003的任務A在0 s開始，持續(xù)10 s結束，緊接著任務編號為YQ202004的任務B開始執(zhí)行，持續(xù)時間為190 s，在200 s的時候整個任務結束。

3? 結? 論

本文主要介紹了一種基于ILOG CPLEX的任務規(guī)劃過程的設計與實現(xiàn)，它是用戶通過在VC環(huán)境下編寫C++程序，連接CPLEX優(yōu)化引擎進行對象優(yōu)化求解的一個過程。求解的是在任務時間條件、優(yōu)先級條件具有一定約束條件的情況下，如何實現(xiàn)最終完成任務的總時間最短的問題。通過本文研究，可以發(fā)現(xiàn)利用ILOG CPLEX來解決任務規(guī)劃的問題效率非常高，在某些制造企業(yè)的實際的生產應用中具有重要意義，可以提高制造企業(yè)的生產效率。

參考文獻：

[1] 雷婕.線性規(guī)劃最優(yōu)解在企業(yè)生產管理決策中的應用 [J].企業(yè)技術開發(fā)，2019，38（3）：98-102.

[2] 劉盛銘，馮書興.基于CPLEX的航天試驗項目管理應用 [J].裝甲兵工程學院學報，2015，29（5）：89-93.

[3] 魯奎，楊昌輝，戴道明.能力受限批量問題的啟發(fā)式算法與CPLEX仿真優(yōu)化 [J].系統(tǒng)仿真學報，2008，20（23）：6365-6368+6371.

[4] 韋東鑫.用于線性規(guī)劃的診斷與決策可視化 [J].現(xiàn)代計算機，2020（8）：26-29.

[5] 張智聰.ILOG OPL優(yōu)化軟件及其教學工作探討 [J].科技信息，2009（22）：186-187.

作者簡介：鄭雅倩（1988—），女，漢族，江蘇連云港人，助教，碩士，研究方向：模式識別、機器學習。