基于ILOG CPLEX的任務規劃過程的設計與實現

摘? 要：在實際生產應用中，存在很多需要在規定時間內完成的復雜任務，任務的持續時間、任務之間的先后順序、任務的優先級等都導致任務規劃的過程存在困難。該文提出一種任務規劃過程，對給定的具有優先級、時間約束條件的任務實現任務規劃過程，達到任務總耗時最小的目標。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—），女，漢族，江蘇連云港人，助教，碩士，研究方向：模式識別、機器學習。