基于ILOG CPLEX的任務(wù)規(guī)劃過程的設(shè)計(jì)與實(shí)現(xiàn)

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

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

中圖分類號(hào)：TP319? ? ? 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：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è)的實(shí)際生產(chǎn)設(shè)計(jì)過程中，往往需要解決規(guī)模很大的問題，同時(shí)在任務(wù)實(shí)施過程中人力、資源、時(shí)間等條件因素是有窮的。單純依靠人工進(jìn)行協(xié)調(diào)安排是不切實(shí)際的，并且也容易出錯(cuò)，而一般的任務(wù)規(guī)劃過程解決問題的過程比較煩瑣，同時(shí)使用起來也不夠靈活，所以對(duì)任務(wù)規(guī)劃過程提出了更高的要求。無錫某RFID智能標(biāo)簽制造公司在生產(chǎn)RFID智能標(biāo)簽的過程中，由于在生產(chǎn)之前沒有對(duì)所有任務(wù)進(jìn)行合理的規(guī)劃，導(dǎo)致出現(xiàn)不能按時(shí)完成生產(chǎn)任務(wù)、生產(chǎn)資源浪費(fèi)等現(xiàn)象。因此委托我校物聯(lián)網(wǎng)學(xué)院基礎(chǔ)部團(tuán)隊(duì)針對(duì)其公司的各項(xiàng)生產(chǎn)任務(wù)進(jìn)行生產(chǎn)前的任務(wù)規(guī)劃，由該公司給出任務(wù)優(yōu)先級(jí)、時(shí)間約束以及各個(gè)任務(wù)之間的關(guān)系，通過任務(wù)規(guī)劃過程，判斷出每個(gè)生產(chǎn)任務(wù)的開始和結(jié)束時(shí)間以達(dá)到生產(chǎn)總時(shí)間的最優(yōu)化，解決生產(chǎn)任務(wù)不能按時(shí)完成的問題。

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

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

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

1? ILOG CPLEX介紹

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

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

本文提出的任務(wù)規(guī)劃過程就是使用C++語(yǔ)言編寫的User-Written應(yīng)用程序，然后通過Concert技術(shù)與ILOG CPLEX對(duì)象構(gòu)建連接求解優(yōu)化結(jié)果。IloCplex對(duì)象是ILOG CPLEX優(yōu)化軟件用來定義優(yōu)化模型對(duì)象的。一個(gè)IloCplex對(duì)象從CPLEX優(yōu)化器中讀取一個(gè)模型并提取出數(shù)據(jù)。然后由IloCplex對(duì)象提取和查詢信息解決方案返回給User-Written應(yīng)用。具體結(jié)構(gòu)圖如圖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）設(shè)置求解目標(biāo)。為構(gòu)建的模型設(shè)置求解目標(biāo)。

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

2? 設(shè)計(jì)與實(shí)現(xiàn)

2.1? 整體設(shè)計(jì)

實(shí)際生產(chǎn)應(yīng)用中需要完成的任務(wù)往往比較復(fù)雜，我們?cè)谠O(shè)計(jì)實(shí)現(xiàn)中將其分解為若干個(gè)簡(jiǎn)單任務(wù)，這些任務(wù)本身存在時(shí)間約束、優(yōu)先級(jí)約束，任務(wù)之間存在著關(guān)系約束，下文對(duì)各個(gè)約束條件進(jìn)行分析。

2.1.1? 時(shí)間約束條件

任務(wù)的時(shí)間約束條件可能包括：任務(wù)的開始時(shí)間、任務(wù)結(jié)束時(shí)間、任務(wù)最長(zhǎng)持續(xù)時(shí)間、任務(wù)最短持續(xù)時(shí)間。根據(jù)實(shí)際生產(chǎn)應(yīng)用中的任務(wù)的實(shí)際情況來定義此時(shí)間約束條件。

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

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

2.1.3? 關(guān)系約束條件

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

（1）BB：任務(wù)一開始之后任務(wù)二開始;

（2）BE：任務(wù)一開始之后任務(wù)二結(jié)束;

（3）EB：任務(wù)一結(jié)束之后任務(wù)二開始;

（4）EE：任務(wù)一結(jié)束之后任務(wù)二結(jié)束。

整個(gè)規(guī)劃過程的優(yōu)化目標(biāo)是要求完成整個(gè)任務(wù)的時(shí)間最小化，求解每個(gè)子任務(wù)的開始及結(jié)束時(shí)間。

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

2.2? 輸入

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

2.3? 輸出

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

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

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

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

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

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

2.4.2? 優(yōu)化目標(biāo)

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

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

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

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

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

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

2.4.5? 設(shè)定新的優(yōu)化目標(biāo)

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

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

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

2.4.6? 求解出結(jié)果

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

3? 結(jié)? 論

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

參考文獻(xiàn)：

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

[2] 劉盛銘，馮書興.基于CPLEX的航天試驗(yàn)項(xiàng)目管理應(yīng)用 [J].裝甲兵工程學(xué)院學(xué)報(bào)，2015，29（5）：89-93.

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

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

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

作者簡(jiǎn)介：鄭雅倩（1988—），女，漢族，江蘇連云港人，助教，碩士，研究方向：模式識(shí)別、機(jī)器學(xué)習(xí)。