滕國棟

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

1 概述

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

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

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

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

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

2 相關工作

APS系統(tǒng)中最為核心的排程與調(diào)度問題的研究序幕可以追溯到20世紀50年代[3]，并一直伴隨著計算機軟件的發(fā)展歷程.國外APS系統(tǒng)經(jīng)過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)等等.國內(nèi)商用的APS系統(tǒng)發(fā)展則較為緩慢，且缺乏成功的案例.在當前國際環(huán)境影響下，商用APS系統(tǒng)的國產(chǎn)替代已經(jīng)迫在眉睫.

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

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

3 系統(tǒng)需求

3.1 布局

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

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

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

3.2 屬性

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

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

3.3 方法

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

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

任務移動，通過鼠標或鍵盤在當前分派的資源和可分配的資源組上進行移動，即支持持垮資源移動，任務完成移動后自動變更為固定任務.

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

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

任務報工，支持計件和即時報工、實時報工和累計報工，任務報工后同樣不允許移動，不參與再次分派.

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

4 架構設計

4.1 技術架構

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

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

4.2 組件設計

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

圖1 組件布局Fig.1 Component layout

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

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

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

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

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

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

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

4.3 核心算法

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

(1)任務選擇算法

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

算法偽代碼見算法1描述，算法復雜度O(N).

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

(2)局部分派算法

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

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

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

5 實現(xiàn)

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

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

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

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

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

圖3 性能測評Fig.3 Performance evaluation

6 結論

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