滕國(guó)棟

(杭州師范大學(xué)信息科學(xué)與技術(shù)學(xué)院，浙江 杭州 311121)

1 概述

作為企業(yè)生產(chǎn)制造和經(jīng)營(yíng)管理活動(dòng)中的一項(xiàng)重要職能，高級(jí)計(jì)劃和排程(advance planning and scheduling，APS)[1]系統(tǒng)利用數(shù)學(xué)模型和啟發(fā)式方法，為需要完成的一系列生產(chǎn)任務(wù)按時(shí)間分派銷售、采購(gòu)、庫(kù)存、設(shè)備和人力等資源，使得企業(yè)能夠更好地制定和完成這些任務(wù).

APS系統(tǒng)通常需要解決NP難問(wèn)題，采用常駐內(nèi)存的方式進(jìn)行復(fù)雜的運(yùn)算.實(shí)際上，當(dāng)資源和生產(chǎn)任務(wù)的數(shù)量分別達(dá)到20個(gè)時(shí)，諸如分支定界法、移動(dòng)瓶頸法等經(jīng)典調(diào)度算法，因獲得問(wèn)題的最優(yōu)解耗時(shí)過(guò)長(zhǎng)，已經(jīng)無(wú)法滿足生產(chǎn)實(shí)踐需求.在面對(duì)實(shí)踐中生產(chǎn)任務(wù)數(shù)量達(dá)到數(shù)萬(wàn)，甚至數(shù)十萬(wàn)個(gè)的場(chǎng)景下，APS系統(tǒng)一般利用啟發(fā)式方法，結(jié)合人工輔助排程的方式實(shí)現(xiàn)近似最優(yōu)解.

APS系統(tǒng)提供豐富的甘特圖組件，如資源甘特圖、訂單甘特圖以及任務(wù)甘特圖等，為人工輔助排程提供人機(jī)交互接口.例如，用戶可在系統(tǒng)啟發(fā)式方法獲得排程結(jié)果的基礎(chǔ)上，通過(guò)本資源或跨資源的方式移動(dòng)任務(wù)以調(diào)整排程結(jié)果，也可以分割連續(xù)時(shí)間較長(zhǎng)的任務(wù)來(lái)實(shí)現(xiàn)任務(wù)的精細(xì)化控制，甚至直接在甘特圖組件中選擇任務(wù)的局部調(diào)度，提高排程效率.

國(guó)外應(yīng)用于APS系統(tǒng)的甘特圖組件并不提供二次開(kāi)發(fā)接口，而優(yōu)秀的商用化或開(kāi)源的甘特圖組件主要面向項(xiàng)目管理，并不滿足APS系統(tǒng)的交互需求.在前后端分離、前端組件化的大趨勢(shì)下，如何設(shè)計(jì)和實(shí)現(xiàn)一款功能豐富、性能優(yōu)越的資源甘特圖組件將是一種新的挑戰(zhàn).

本文采用主流的前端技術(shù)框架React[2],以組件化的方式設(shè)計(jì)并實(shí)現(xiàn)了APS系統(tǒng)的核心組件——資源甘特圖RGantt，在滿足可視化和人工輔助排程功能的基礎(chǔ)上，性能不低于同類面向項(xiàng)目管理的甘特圖組件.

2 相關(guān)工作

APS系統(tǒng)中最為核心的排程與調(diào)度問(wèn)題的研究序幕可以追溯到20世紀(jì)50年代[3]，并一直伴隨著計(jì)算機(jī)軟件的發(fā)展歷程.國(guó)外APS系統(tǒng)經(jīng)過(guò)70年的不懈努力，已經(jīng)形成較為成熟的理論體系[4]和工業(yè)軟件產(chǎn)品[5].例如，SAP的PP/DS系統(tǒng)、IBM的IAA系統(tǒng)、AMD的RTDAS系統(tǒng)、ASPROVA 的APS系統(tǒng)、Preactor的PSS系統(tǒng)以及ORTEMS 的AMS系統(tǒng)等等.國(guó)內(nèi)商用的APS系統(tǒng)發(fā)展則較為緩慢，且缺乏成功的案例.在當(dāng)前國(guó)際環(huán)境影響下，商用APS系統(tǒng)的國(guó)產(chǎn)替代已經(jīng)迫在眉睫.

作為APS人機(jī)交互的重要組件資源甘特圖，主要用于顯示和調(diào)整生產(chǎn)任務(wù)在時(shí)間維度上資源的占用情況.目前，開(kāi)源或商用的甘特圖組件主要用于項(xiàng)目進(jìn)度管理，如采用原生js開(kāi)發(fā)的DHTMLX[6]甘特圖，雖然功能強(qiáng)大，但是難以滿足APS系統(tǒng)中資源甘特圖中人機(jī)交互的需求.

2016年以來(lái)，JavaScript開(kāi)發(fā)框架得到了快速發(fā)展，其中Angular、React以及Vue占據(jù)著主流地位[7].React和 Vue 都擅長(zhǎng)處理組件，并且更好地滿足微服務(wù)和微應(yīng)用.相比Vue，React在靈活性和生態(tài)系統(tǒng)上更有優(yōu)勢(shì).因此，在本文中，我們采用React作為資源甘特圖開(kāi)發(fā)框架.

3 系統(tǒng)需求

3.1 布局

資源甘特圖一方面用于呈現(xiàn)生產(chǎn)任務(wù)在時(shí)間維度上資源的占用情況，另一方面對(duì)于基于算法的排程結(jié)果進(jìn)行人工干預(yù)和調(diào)整，有利于改善排程結(jié)果和提升用戶的交互體驗(yàn).

為滿足上述需求，資源甘特圖整體布局可分為資源區(qū)、時(shí)間區(qū)和任務(wù)區(qū).資源區(qū)通常在整體布局的左側(cè)以列表的形式展示可分配的資源，支持資源的排序、篩選、顏色區(qū)分、分組等基本功能；時(shí)間區(qū)位于整體布局的上側(cè)用于展示時(shí)間軸，支持不同時(shí)間粒度呈現(xiàn)、節(jié)假日顯示樣式等基本功能；任務(wù)區(qū)在整體布局的中央，是資源甘特圖展示和操作的核心工作區(qū)，支持任務(wù)、連線的交互操作功能.

為了便于以面向?qū)ο蟮姆椒ㄟM(jìn)行建模，把資源區(qū)、時(shí)間區(qū)還是任務(wù)區(qū)相關(guān)對(duì)象的外觀和設(shè)置值稱為屬性，把對(duì)區(qū)域中對(duì)象的一系列操作稱為方法.

3.2 屬性

在任務(wù)區(qū)，通過(guò)參考時(shí)間線屬性設(shè)置計(jì)劃基準(zhǔn)時(shí)間、分派開(kāi)始時(shí)間、分派結(jié)束時(shí)間、顯示開(kāi)始時(shí)間和顯示結(jié)束時(shí)間等；任務(wù)和連接線的相關(guān)屬性包括外觀顯示、提示文字、移動(dòng)步長(zhǎng)等操作設(shè)置；通過(guò)工廠日歷和出勤模式獲得可分派的時(shí)間區(qū)間.在時(shí)間區(qū)可設(shè)置時(shí)間間隔單位，如月、日、時(shí)等.資源區(qū)中可設(shè)置資源的分組、優(yōu)先級(jí)等.

因此，資源甘特圖的核心屬性應(yīng)包括參考時(shí)間線、任務(wù)、連接線、出勤模式、時(shí)間間隔、分組、優(yōu)先級(jí)等.

3.3 方法

方法中除去基本的任務(wù)選擇、資源排序和篩選、訂單和工作的查找后的高亮顯示、時(shí)間區(qū)間變更等基本功能外，還應(yīng)包括以下屬于資源甘特圖的特定操作，并在完成特定操作后，任務(wù)以不同的樣式進(jìn)行呈現(xiàn).

任務(wù)固定，對(duì)于瓶頸工序相關(guān)的任務(wù)，可按時(shí)間、資源在甘特圖中進(jìn)行固定，固定的任務(wù)在排程算法重新執(zhí)行時(shí)會(huì)視作已經(jīng)完成分派的任務(wù).

任務(wù)移動(dòng)，通過(guò)鼠標(biāo)或鍵盤在當(dāng)前分派的資源和可分配的資源組上進(jìn)行移動(dòng)，即支持持垮資源移動(dòng)，任務(wù)完成移動(dòng)后自動(dòng)變更為固定任務(wù).

任務(wù)分割，已分派的任務(wù)可按比例、數(shù)量和批次等參數(shù)進(jìn)行分割，自動(dòng)生成多個(gè)子任務(wù)，以支持并行分派等更加靈活的分派需求.

狀態(tài)變更，變更已完成分派任務(wù)的狀態(tài)，如分派完畢改為開(kāi)啟任務(wù)，開(kāi)啟任務(wù)改為任務(wù)完畢.分派完成的狀態(tài)變更后，該任務(wù)將被確定，不允許移動(dòng)，不參與再次分派.

任務(wù)報(bào)工，支持計(jì)件和即時(shí)報(bào)工、實(shí)時(shí)報(bào)工和累計(jì)報(bào)工，任務(wù)報(bào)工后同樣不允許移動(dòng)，不參與再次分派.

局部分派，為減輕前后端通信和后端排程算法的壓力，前端可在后端排程結(jié)果的基礎(chǔ)上對(duì)局部任務(wù)基于啟發(fā)式規(guī)則進(jìn)行重新分派，前端局部分派能更好地滿足用戶排程體驗(yàn).

4 架構(gòu)設(shè)計(jì)

4.1 技術(shù)架構(gòu)

React是一種組件化的用于構(gòu)建用戶界面的 JavaScript 庫(kù)，能創(chuàng)建擁有各自狀態(tài)的組件，再由這些組件構(gòu)成更加復(fù)雜的UI.此外，React具有豐富的生態(tài).

我們選擇MobX、Ant Design、Router以及Mock.js搭建前端系統(tǒng)架構(gòu)，該框架包括實(shí)現(xiàn)仿真組件和功能組件.其中，功能組件中的MobX用于狀態(tài)管理，Ant Design用于UI組件庫(kù)；Router和Mock.js用于搭建仿真環(huán)境，分別用于前端路由和模擬各種場(chǎng)景.

4.2 組件設(shè)計(jì)

我們?cè)O(shè)計(jì)了滿足React規(guī)范的〈RGantt/〉組件，該組件采用Ant Design的〈Layout/〉組件進(jìn)行布局，分別劃分成資源區(qū)、時(shí)間區(qū)和任務(wù)區(qū)，分別嵌套〈Resource/〉、〈Scale/〉和〈Task/〉組件.如圖1所示.

圖1 組件布局Fig.1 Component layout

資源區(qū)〈Resource/〉組件由〈List/〉組件渲染，〈List/〉組件中每一項(xiàng)〈List.Item/〉可設(shè)置顏色、大小等外觀屬性，同時(shí)支持鼠標(biāo)左鍵單擊關(guān)聯(lián)任務(wù)區(qū)、右鍵單擊關(guān)聯(lián)上下文菜單事件.

時(shí)間區(qū)〈Scale/〉由〈ul〉〈li〉〈/li〉〈/ul〉渲染，時(shí)間區(qū)除外觀屬性外，預(yù)設(shè)了月、日、時(shí)3個(gè)顯示標(biāo)準(zhǔn)，根據(jù)任務(wù)區(qū)獲取的數(shù)據(jù)展示時(shí)間軸線.如果對(duì)時(shí)間軸線的渲染有其他展示需求，可以傳遞時(shí)間控制參數(shù)，自定義渲染.

任務(wù)區(qū)〈Task/〉組件由〈List/〉組件渲染，〈List/〉組件中每一項(xiàng)〈List.Item/〉分2層〈div/〉分別用于控制可分派的時(shí)間區(qū)間和分派的任務(wù).

〈RGantt/〉組件參數(shù)實(shí)現(xiàn)了資源甘特圖所需的屬性和方法，其核心屬性和方法如表1所示.

其中，外觀屬性包括資源區(qū)、時(shí)間區(qū)和任務(wù)區(qū)對(duì)象的顏色、字體、大小等屬性任務(wù)，屬性至少包括任務(wù)開(kāi)始時(shí)間、結(jié)束時(shí)間、資源、當(dāng)前任務(wù)狀態(tài)等，任務(wù)連接屬性包括前后序任務(wù)列表.事件發(fā)生時(shí)，在實(shí)現(xiàn)既定任務(wù)如拖拽、固定、分割等功能外，用戶還可以通過(guò)回調(diào)函數(shù)添加自定義功能，如聯(lián)動(dòng)組件的屬性渲染.

此外，為滿足〈RGantt/〉組件可視化效果、靈活的屬性設(shè)置以及多樣的事件觸發(fā)機(jī)制，設(shè)計(jì)了諸如氣泡、彈窗和上下文菜單等功能.

表1 RGantt/組件核心屬性和方法Tab.1 RGantt/ component core attributes and methods

4.3 核心算法

為滿足人機(jī)交互需求，應(yīng)實(shí)現(xiàn)諸如時(shí)間區(qū)間、任務(wù)選擇、局部分派等核心算法.其中，時(shí)間區(qū)間算法根據(jù)用戶設(shè)置的工廠日歷、工作模式和法定節(jié)假日自動(dòng)生成可用于分派的時(shí)間區(qū)間，考慮到區(qū)間數(shù)量較多，算法應(yīng)在前端資源甘特圖組件中進(jìn)行計(jì)算并渲染.下面我們著重給出任務(wù)選擇算法和局部分派算法的詳細(xì)描述.

(1)任務(wù)選擇算法

非終結(jié)點(diǎn)任務(wù)具有前序任務(wù)和后續(xù)任務(wù)，如果將關(guān)聯(lián)的任務(wù)之間按時(shí)間方向進(jìn)行連接，可構(gòu)建成一張有向圖，任務(wù)選擇算法就是在這張有向圖中高量顯示選定任務(wù)的所有前序任務(wù)和后續(xù)任務(wù)以及相關(guān)的有向連接線.

算法偽代碼見(jiàn)算法1描述，算法復(fù)雜度O(N).

算法1 TaskSelected(taskID, taskList)輸入:taskID選擇的任務(wù)ID,taskList任務(wù)列表;輸出:taskList任務(wù)列表,taskID所在訂單所有任務(wù)高亮顯示、建立連接線;1. 在taskList中高亮taskID任務(wù);2. 在taskList中遞歸遍歷taskID任務(wù)的后序任務(wù),如存在后序任務(wù),則高亮顯示后序任務(wù)、建立從taskID任務(wù)到后序任務(wù)的有向連接線;3. 在taskList中遞歸遍歷taskID任務(wù)的前序任務(wù),如存在前序任務(wù),則高亮顯示前序任務(wù)、建立從前序到taskID任務(wù)的有向連接線.

(2)局部分派算法

通常局部分派過(guò)程中選取的工作數(shù)量有限，因此可對(duì)多種啟發(fā)式規(guī)則進(jìn)行模擬分派，根據(jù)逾期任務(wù)數(shù)、交貨期遵守率、平均等待時(shí)間等因素對(duì)分派結(jié)果進(jìn)行綜合評(píng)估，最終獲取綜合評(píng)估結(jié)果最好的任務(wù)分派結(jié)果.

算法偽代碼見(jiàn)算法2描述，算法復(fù)雜度O(NK)，N為啟發(fā)式規(guī)則數(shù)量，K為對(duì)應(yīng)啟發(fā)式算法的最壞復(fù)雜度.

算法2 PartialTaskScheduling(subTaskList, ruleList)輸入:subTaskList擬局部分派的子任務(wù)列表,ruleList局部分派啟發(fā)式規(guī)則列表輸出:subTaskList完成分派的子任務(wù)列表1. subTaskList根據(jù)ruleList 中每條啟發(fā)式規(guī)則進(jìn)行模擬分派,并對(duì)分派結(jié)果進(jìn)行評(píng)估;2. 返回具有最大評(píng)估因子的分派結(jié)果.

5 實(shí)現(xiàn)

我們通過(guò)資源甘特圖組件構(gòu)建了商用的APS系統(tǒng)[8]，該系統(tǒng)采用制造BOM、物料、資源以及工廠日歷獲得基礎(chǔ)數(shù)據(jù)，將銷售訂單展開(kāi)后獲得制造訂單、庫(kù)存訂單以及采購(gòu)訂單，并進(jìn)一步生成一系列的制造任務(wù)、庫(kù)存任務(wù)以及采購(gòu)任務(wù).調(diào)度算法則將這些任務(wù)分派至企業(yè)的各種資源，并通過(guò)可視化的方式呈現(xiàn)在資源甘特圖和訂單甘特圖以及資源負(fù)荷圖上.

圖2展示的是已上線的面向五金行業(yè)APS系統(tǒng)資源甘特圖的實(shí)現(xiàn)案例.位于左側(cè)的資源區(qū)包括采購(gòu)資源(CG-1012)、庫(kù)存資源(KC-1010)、設(shè)備資源(鉆孔ZK2002、噴涂PT-5002、PT-5002、PT-5005、機(jī)加JJ-1501，組裝設(shè)備ZZ-8002，檢測(cè)設(shè)備JC-2501)、人力資源(操作員JJ-CZY-1601)以及銷售資源(XS1010).時(shí)間區(qū)位于甘特圖上方，顯示日期和單位刻度.任務(wù)區(qū)展示了多個(gè)銷售訂單(如BT100-2020080101)展開(kāi)成制造訂單(如B0001、B0007、B0013等)，并拉動(dòng)庫(kù)存訂單(K0001)和采購(gòu)訂單(如P0001)，通過(guò)任務(wù)選擇的方式，清楚地查看到有向連接線關(guān)聯(lián)的展開(kāi)訂單，并固定瓶頸任務(wù)(如B0018)，變更任務(wù)狀態(tài)(如B0013).

圖2 甘特圖實(shí)現(xiàn)樣例Fig.2 Gantt chart implementation example

同時(shí)在不同任務(wù)數(shù)量下對(duì)甘特圖增加、檢索、修改和拖拽等用戶操作，DHTMLX和RGantt用戶在性能方面的操作體驗(yàn)無(wú)明顯差別.實(shí)測(cè)表明，當(dāng)數(shù)量小于10 000條時(shí)，DHTMLX和RGantt均不卡頓，50 000條時(shí)基本不卡頓，而超過(guò)100 000條時(shí)均卡頓明顯，點(diǎn)擊之后需要等待4～5 s時(shí)間.

性能測(cè)試表面，RGantt性能不低于同類面向項(xiàng)目管理中非常優(yōu)秀的DHTMLX甘特圖組件.

圖3 性能測(cè)評(píng)Fig.3 Performance evaluation

6 結(jié)論

資源甘特圖RGantt在滿足商用APS系統(tǒng)對(duì)于任務(wù)呈現(xiàn)和調(diào)整的需求基礎(chǔ)上，性能不低于同類面向項(xiàng)目管理的甘特圖組件，滿足了實(shí)踐應(yīng)用的需求.APS系統(tǒng)除資源甘特圖外，還應(yīng)提供訂單甘特圖、任務(wù)甘特圖.為此，在后續(xù)的工作中，我們的工作重心將集中在如何以更加抽象的方式統(tǒng)一APS前端的各型甘特圖，更好地發(fā)揮APS系統(tǒng)在人機(jī)交互方面的能力.