鄧鑫睿 曹陽

（重慶理工大學電氣與電子工程學院 重慶 401320）

光伏輔助供能的柔性作業(yè)車間調(diào)度問題（FJSPPE）是在柔性作業(yè)車間調(diào)度問題（FJSP）基礎上加入了光伏儲能微電網(wǎng)，在生產(chǎn)過程中，優(yōu)先使用光伏儲能，光伏儲能使用完畢后，切換電網(wǎng)供電，進而減少化石能源消耗，減少碳排放。在FJSP 環(huán)境下，工件的工序加工可以選擇的機器更多。車輛組裝、紡織、材料加工、半導體制造等場景都可以抽象為FJSP模型，該模型是一類典型的NP難問題。

在求解FJSP方面，智能優(yōu)化算法都發(fā)揮了極為重要的作用，并取得了一定的研究成果。Gu和Ding提出了一種改進型的粒子群算法（PSO），求解車間調(diào)度問題。Mouzon 和Yildirim將貪婪隨機自適應搜索算法應用于以總能耗和總延誤最小為目標的單機多目標優(yōu)化調(diào)度問題。Rager 等人提出了一種面向能量的并行機器調(diào)度進化算法。Liu 等人提出了一種以總能耗和總加權拖期為目標的經(jīng)典作業(yè)車間調(diào)度問題多目標調(diào)度方法。趙小惠等人為求解FJSP，提出一種改進型蟻群算法，仿真結(jié)果驗證了算法的有效性。王家海等人設計了一種精確鄰域結(jié)構混合進化算法求解FJSP。

隨著綠色生產(chǎn)研究的興起，智能算法優(yōu)化車間調(diào)度問題成為了熱門研究方向。20世紀50年代起，關于生產(chǎn)調(diào)度的研究就受到運籌學、應用數(shù)學等領域?qū)W者的關注。20世紀80年代起，人們就一直在嘗試并致力于解決實際調(diào)度問題，調(diào)度研究由理論研究轉(zhuǎn)向應用研究階段。關于使用光伏輔助供能對碳排放的影響，吳秀麗和崔琪根據(jù)太陽能的發(fā)電特性，建立了光伏供電模型，在此基礎上，構建了考慮光伏供能的柔性流水車間調(diào)度數(shù)學優(yōu)化模型，通過大量實例，證明了引入光伏供能能夠在保證完工時間的前提下有效降低碳排放量。

1 問題描述

光伏輔助供能的柔性作業(yè)車間調(diào)度問題可作如下描述：工件集={，，…，J}包含個工件，每個工件都需要經(jīng)過一道或多道加工工序，工件J具有h道工序，工序o為工件J的第道工序。每道工序均有多臺相同的機器可供選擇。每臺機器具有種速度，={，，…，v}為速度集合。機器的加工速度在加工工件時就已經(jīng)確定，不可在加工過程中變更加工速度。

機器的狀態(tài)可分為加工狀態(tài)和準備狀態(tài)。當機器M以速度v加工時，加工狀態(tài)下單位時間的能耗為E；機器M∈不加工工件時，處于準備狀態(tài)，單位時間的該機器瞬時能耗為E。每道工序o在機器M∈上有一個給定的標準加工時間η，當工序o在機器M上以速度加工時，相應的加工時間p= η v。p是工序o在機器M上的總的加工時間，總加工時間包含使用普通能源的時間pN及使用光伏電能的加工時間pL，即p= pN+ pL。

光伏輔助供能的柔性作業(yè)車間調(diào)度問題滿足以下約束：不同工件的工序之間沒有先后順序約束，但同一工件的各道工序必須按照預先規(guī)定順序完成；一臺機器同一時刻只能用于一道工序的加工；每道工序同一時刻只能在一臺機器上加工；工序一旦開始加工不能中斷；所有加工機器優(yōu)先使用太陽能儲能裝置供能，儲能裝置的能量用盡后，再切換至普通電網(wǎng)。

FJSP-PE 包含4 個子問題：（1）調(diào)度子問題；（2）機器分配子問題；（3）速度選擇子問題；（4）能耗分配子問題。問題（1）確定每臺機器加工工件的順序，問題（2）確定每道工序的加工機器，問題（3）為每道工序的加工機器確定加工速度，問題（4）確定每臺機器使用太陽能儲能裝置的時長。

同時，考慮以下兩個目標函數(shù)。

碳排放量：

最小化最大完成時間：

其中，y()、z()均為二進制量。

時刻，機器M∈處于加工狀態(tài)，則y()=1，否則，y()=0；時刻，機器M∈為準備狀態(tài)，則z()=1，否則z()=0。

為能耗與碳排放量之間的轉(zhuǎn)化系數(shù)，通常為0.680。表示最大完成時間，E為機器在待機狀態(tài)下的單位時間能耗，E表示令機器M以速度v加工時的單位時間能量消耗。式（3）表示每臺機器的空轉(zhuǎn)時間包含該機器使用兩種能源的空轉(zhuǎn)時間；式（4）表示太陽能儲能裝置的容量為，周期內(nèi)可使用的太陽能來自于前一周期太陽能產(chǎn)生的電能；式（5）表示周期內(nèi)，使用太陽能進行加工時的總能耗及機器空轉(zhuǎn)總能耗不超過周期內(nèi)可使用的太陽能。

Ding 等給出了一種假設描述機器的加工時間與能耗的關系，即能耗與速度正相關，更快的加工速度縮短了加工時間，同時也會導致更高的能耗。因此，本文研究的兩個目標函數(shù)之間的沖突關系是顯而易見的，更快的加工速度會縮短最大完成時間，同時也會造成更多的碳排放量。

表1給出一個例子的加工信息，4個工件總共10道工序，其中，工件包含2道工序，工件包含3道工序，工件僅有1道工序，而工件包含4道工序。每道工序均有3臺加工機器可供選擇，工序在機器上的加工時間如表1所示，每臺機器的能耗信息如表2所示。

圖1是表1中的算例的一種調(diào)度甘特圖。表2是每個階段各臺機器的加工功率及空載功率，根據(jù)相關文獻中的計算方法，算出光伏供能的時間及普通能源供能的時間，繪制出能耗甘特圖，如圖2所示，其中，淺色部分表示工件加工消耗的是光伏能源，深色部分表示消耗的是普通能源。經(jīng)計算，采用光伏輔助供能的作業(yè)車間碳排放降低18.4%。

圖1 調(diào)度甘特圖

圖2 能耗甘特圖

表1 加工信息

表2 機器能耗

2 多學習對象蛙跳算法雙目標綠色FJSP

考慮一種多學習對象的蛙跳算法（MLO-SFLA）用于求解該問題。算法改變了原有的單一學習對象的選擇策略，擴大的學習對象的選擇范圍，使得算法更容易找到更優(yōu)的可行解。

2.1 編碼和解碼

為了獨立地優(yōu)化和處理各子問題，采用調(diào)度串、機器分配串和速度選擇串分別地表示各子問題的解。對于具有個工件、臺機器的低碳FJSP，問題的解可由調(diào) 度 串[(，)，(，)，…，(θ，r)，…，(θ，r)]，機器分配串[，，…，，…，ρ]和速度選擇串[，，…，，…，u]表示，其中，串長均為=∑h。

調(diào)度串中，θ∈{1，2，…，}，1 ≤r≤h，二元組(θ，r)對應工序o，這樣整個串對應一個有序工序表[o，o，…，o，…，o]。機器分配串中，ρ∈S表示用于加工工序o的機器。第三個串中，u為ρ加工o時的速度。能耗子問題的解碼方法為優(yōu)先使用能耗低的機器加工，優(yōu)先安排能耗低的工序加工。

2.2 生成初始種群與模因組構建

提出一種多學習對象蛙跳算法，其模因組構建方法如下：在初始種群隨機產(chǎn)生后開始進行種群劃分，確定模因組的個數(shù)及模因組內(nèi)解的個數(shù)，=×。對種群中的解進行排序，根據(jù)其值，找到最好的個解，第一的解分配到模因組，第二的解分配到模因組，依次進行直到序列第的解分配到模因組，最后，采用二元錦標賽，選擇將剩余解依次分配到各模因組內(nèi)：隨機選擇兩個解x和x，如果x優(yōu)于x，那么x將分配到模因組，如果兩個解彼此非劣，則隨機選擇其中一個分配到模因組，另外一個解回到種群，重復執(zhí)行上述步驟，直至所有解分配完畢。

2.3 局部搜索策略

通常，模因組內(nèi)的搜索過程為首先利用模因組內(nèi)最好解x和模因組內(nèi)最差解x產(chǎn)生一個新解x，如果x優(yōu)于x，則替換最差解x；否則，利用種群內(nèi)的最好解x和x產(chǎn)生新解x，若x優(yōu)于x，則替換最差解x；否則，隨機產(chǎn)生一個解替換x，重復上述步驟，直到達到設定的迭代次數(shù)。

上述方法中，優(yōu)化對象學習的對象比較單一，通常為模因組內(nèi)最好解或種群內(nèi)的最好解。本文提出一種新的學習對象的選擇方法，具體過程如下。

（1）=1。

（2）=1。

（3）確定模因組內(nèi)的最差解x，每隔10 次更換x的學習對象，記為，優(yōu)于x或與x彼此非劣。

（4）對和x執(zhí)行全局搜索，產(chǎn)生新解x，產(chǎn)生隨機數(shù)。如果＜0.5，利用兩個解的調(diào)度串交叉產(chǎn)生新解；如果0.5 ≤＜0.7，則執(zhí)行機器分配串的交叉操作；如果≥0.7，則通過速度選擇串交叉獲得新解。如果x滿足替換條件，則用x替代x，更新外部檔案Ω并轉(zhuǎn)到（7）。

（5）從外部檔案Ω 中隨機選擇一個解≠x，對∈Ω 和x執(zhí)行全局搜索，產(chǎn)生隨機數(shù)，如果＜0.7，則對與x的調(diào)度串進行交叉，否則，對兩個解的機器分配串執(zhí)行交叉。否則，直接對x的速度選擇串執(zhí)行，產(chǎn)生新解x，如果x達到替換要求，則用x替代x，更新外部檔案并轉(zhuǎn)到（7）。

（6）產(chǎn)生新解x∈N()，ρ= ρ+1，若ρ=4，則令ρ=1。若x符合替換條件，則用x替代x，并更新外部檔案Ω。

（7）=+1，如果≤，則轉(zhuǎn)到（3）。

（8）=+1，如果≤，則轉(zhuǎn)到（2）。當x支配或者兩者彼此非劣時，稱x滿足替換條件。

3 實驗結(jié)果

為了驗證MLO-SFLA的性能，采用相關文獻中的算例，這些算例在Microsoft Visual Studio C++2019編程實現(xiàn)，并運行在12.0G RAM 2.50GHz CPU的PC機上。

機器在加工狀態(tài)下單位時間瞬時能耗為E∈[2，4]；空閑狀態(tài)下，單位時間瞬時能耗為E=1。加工機器有5 種速度可供選擇 ：={1.00，1.25，1.45，1.80，2.00}。

采用PSO 及變鄰域搜索（variable neighborhood search，VNS）作為對比算法。MLO-SFLA 參數(shù)設置為=60，=6，最大迭代次數(shù)為10；PSO 的加速參數(shù)=2，=2，慣性因子=1.2，n=200，=100，最大迭代次數(shù)為10；VNS中=350，最大迭代次數(shù)為10。

評價指標用來衡量算法所產(chǎn)生的解集Ω所提供的非劣解在整個參考集Ω中所占的比例。顯然，越大，說明算法的綜合性能越好。

表3記錄了3種算法關于指標的運算結(jié)果。表3表明，關于指標，MLO-SFLA 有17 個實例結(jié)果占優(yōu)，遠遠優(yōu)于PSO 及VNS 運算得到的結(jié)果，表明MLO-SFLA 產(chǎn)生了更多的優(yōu)質(zhì)可行解，增加了解決方案的多樣性。圖3、圖4反映了3種算法關于兩種實例的解的分布圖。從圖中也可以直觀反映出MLO-SFLA產(chǎn)生的解要優(yōu)于PSO 及VNS，證明MLO-SFLA 在求解FJSP-PE的優(yōu)越性。

表3 MLO-SFLA、PSO、VNS 關于指標ρ的運算結(jié)果

圖3 實例MK01 關于3 種算法的解的分布圖

圖4 實例MK05 關于3 種算法的解的分布圖

4 結(jié)語

本文在簡要介紹光伏輔助供能FJSP的原理之后，建立了該問題的數(shù)學模型；而后，從生成初始種群、模因組的構建、局部搜索策略等方面詳細描述了MLO-SFLA；最后，通過大量的實例驗證對比MLO-SFLA 和PSO、VNS的優(yōu)化性能，最終的實驗結(jié)果和分析表明，MLO-SFLA 對所研究的問題具有良好的優(yōu)化能力。