考慮關(guān)鍵件加工質(zhì)量的雙資源約束車間調(diào)度算法

孫愛紅 宋豫川 楊云帆 雷 琦

重慶大學(xué)機械傳動國家重點實驗室，重慶，400044

0 引言

產(chǎn)品質(zhì)量的形成過程中，某些關(guān)鍵件的加工質(zhì)量是影響產(chǎn)品質(zhì)量的重要因素，制造商在保證盈利水平的條件下，必須尋求切實可行的生產(chǎn)策略以盡可能地提高產(chǎn)品質(zhì)量。

近年來，資源約束型作業(yè)車間調(diào)度問題逐漸受到國內(nèi)外學(xué)者的廣泛關(guān)注。MONDHER等[1]從研究方法、機床柔性、工人柔性、優(yōu)化指標(biāo)、求解方法、方法框架等6個方面，對雙資源約束作業(yè)車間調(diào)度問題(dual-resource constrained job shop scheduling problem，DRCJSP)和雙資源約束柔性作業(yè)車間調(diào)度問題(dual-resource constrained flexible job shop scheduling problem，DRCFJSP)的部分工作進行了回顧，其中涉及到的優(yōu)化目標(biāo)有利潤、完工時間[2]、工人數(shù)、延遲訂單數(shù)、生產(chǎn)成本、生產(chǎn)效率、拖期[3]、能耗[4]、噪聲污染、工人調(diào)動次數(shù)等。WU等[5]針對DRCFJSP建立了以最小化最大完工時間和準(zhǔn)結(jié)時間為目標(biāo)的數(shù)學(xué)模型。孔繁森等[6]為獲得人機聯(lián)合任務(wù)分配問題的最優(yōu)資源利用方案，建立了以資源利用均衡率、工人任務(wù)復(fù)雜度均衡率、平均認知度為約束條件，以最小化平衡滯延時間為目標(biāo)的人機聯(lián)合任務(wù)分配模型。以上研究考慮的目標(biāo)多涉及資源(時間、人力、物力、財力、環(huán)境等)的有效利用，幾乎沒有考慮產(chǎn)品的加工質(zhì)量，可能導(dǎo)致相關(guān)目標(biāo)完成而加工質(zhì)量難以保障的問題，并且此類問題在資源有限的場景中更容易出現(xiàn)。

有研究從以下兩個方向來保障產(chǎn)品質(zhì)量。一是從整體的角度出發(fā)，以提高總體工件加工質(zhì)量為目標(biāo)來保障產(chǎn)品質(zhì)量[7-9]，這要求所有工件同等重要，工件之間不存在優(yōu)先等級。通常來說，不同工件的重要程度必然不同，因此，以整體加工質(zhì)量為優(yōu)化目標(biāo)可能造成部分非關(guān)鍵件搶占關(guān)鍵件的優(yōu)秀資源，導(dǎo)致非關(guān)鍵件加工質(zhì)量過剩，而關(guān)鍵件質(zhì)量未達到預(yù)定加工要求。二是從關(guān)鍵件/關(guān)鍵工序出發(fā)，對加工要求高的關(guān)鍵件或關(guān)鍵工序指定特定的工人/機床來加工，以保障其加工質(zhì)量[10-11]，這雖然在一定程度上滿足了關(guān)鍵件的加工質(zhì)量要求，但資源柔性降低，導(dǎo)致某些特定工人/機床的工作量過大，調(diào)度目標(biāo)優(yōu)化程度下降。

因此，為進一步完善產(chǎn)品加工質(zhì)量的保障策略，本文結(jié)合生產(chǎn)車間的實際情況，考慮關(guān)鍵件加工質(zhì)量、準(zhǔn)備時間、機床類型、人和機床加工異質(zhì)性等因素，建立了雙資源約束柔性作業(yè)車間調(diào)度問題模型，將關(guān)鍵件加工質(zhì)量閾值作為約束條件，在保障關(guān)鍵件加工質(zhì)量的同時提高總體工件的加工質(zhì)量，并以最小化最大完工時間為目標(biāo)，設(shè)計了基于時窗的活動調(diào)度策略的兩級嵌套蟻群算法進行求解，在實現(xiàn)優(yōu)化調(diào)度目標(biāo)的過程中，不斷提高關(guān)鍵件和整體工件的加工質(zhì)量。

1 問題描述和數(shù)學(xué)模型

1.1 問題描述

考慮關(guān)鍵件加工質(zhì)量的雙資源約束柔性作業(yè)車間調(diào)度問題可以描述為：w個工人操縱m臺機床加工n個工件，工件中有nc個為關(guān)鍵件，各工件包含多道工序且每道工序有多臺可選加工機床，同一工序在不同機床上的加工時間可能不同。車間內(nèi)部的機床可分為普通機床和數(shù)控機床。對于數(shù)控機床，工人僅需負責(zé)工件的上下料、清洗等準(zhǔn)備工作，而普通機床工人則需參與準(zhǔn)備工作以及工件加工的全過程。若工件在某一機器上連續(xù)加工，則工人只需對連續(xù)工序的首道工序進行相應(yīng)的準(zhǔn)備工作。工人數(shù)目小于機床數(shù)目，每個工人具備操作一臺以上機床的能力，工人操作不同機床的加工合格率以及不同機床的加工合格率不一定相同。關(guān)鍵件的加工質(zhì)量(由工件各道工序的工人和機床的加工合格率來體現(xiàn))需在加工質(zhì)量閾值上。調(diào)度任務(wù)為每一道工序安排合適的機床、工人和順序，在滿足關(guān)鍵件加工質(zhì)量要求的前提下，使得工件的總完工時間最小、整體加工質(zhì)量水平更高。

為簡化問題，本文給出如下假設(shè)：①各工件的每道工序在不同機床上的加工時間已知；②同一時刻一臺機床只能加工一個零件；③每個工件在某一時刻只能在一臺機床上進行加工，不能中斷；④不同工件的工序之間沒有先后順序約束；⑤不同工件之間具有相同的加工優(yōu)先級；⑥工人可以操作的機床集合已知；⑦每個工人在任意時刻只能操作一臺機床；⑧在零時刻，所有工件均可被加工；⑨不同機床、工人的加工合格率是已知的。

1.2 數(shù)學(xué)模型

基于以上定義，給出調(diào)度目標(biāo)函數(shù)：

min(f1)=min(maxCk)

(1)

(2)

(3)

(4)

式中，f1為總完工時間；f2為總加工質(zhì)量水平。

(5)

TRijkl=Tijk(1-Hk)(2-elk)+TijkHk

(6)

(7)

(8)

STi(j+1)qr≥ETijkl

(9)

(10)

YijklYxyqr(ETijkl-STxyqr)(STijkl-ETxyqr)≥0

(11)

YijklYxykr(ETijkl-STxykr)(STijkl-ETxykr)≥0

(12)

(13)

(14)

STijkl≥0

(15)

式(5)表示關(guān)鍵件的加工質(zhì)量需滿足給定質(zhì)量要求；式(6)、式(7)分別表示機床和工人的實際加工時間；式(8)說明工序?qū)嶋H加工時間取決于機床、工人的選擇以及工序加工的排序情況；式(9)反映了工藝加工順序，每個任務(wù)必須按工序的先后順序完成；式(10)表示每道工序只能由單個工人操作一臺設(shè)備完成；式(11)表示每臺設(shè)備在任意時刻只能完成一道工序；式(12)表示每個工人任意時刻只能操作一臺機床；式(13)、式(14)分別表示設(shè)備為普通機床和數(shù)控機床時的工序可選完成時間；式(15)表示所有工序的開始加工時間都大于零。

本文考慮的是完工時間f1和質(zhì)量f2的多目標(biāo)優(yōu)化問題。企業(yè)主要關(guān)注生產(chǎn)性能時，會更看重f1，而輕視f2。為處理這種情況，將f1設(shè)定為主要優(yōu)化目標(biāo)，將f2看做附帶優(yōu)化目標(biāo)。如果同等對待兩個目標(biāo)，則企業(yè)會忽略那些f2偏高的解，因為那些解不符合他們的偏好；相反，將附帶優(yōu)化目標(biāo)嵌入到優(yōu)化過程中，附帶優(yōu)化目標(biāo)也能得到充分優(yōu)化。

2 算法設(shè)計

蟻群算法因原理簡單、通用性好、條件約束少等特點而被廣泛用于求解組合優(yōu)化問題。針對考慮了關(guān)鍵件加工質(zhì)量的DRCFJSP，本文設(shè)計了一種兩級嵌套蟻群算法來進行求解，算法的第一級為工序排序?qū)樱诙墳橘Y源指派層。此外，根據(jù)問題的特點，設(shè)計了一種新型候選集來保證解的可行性，并提出了一種基于時窗的活動解碼來提高解的質(zhì)量。螞蟻尋優(yōu)過程可視為以最小化總完工時間為主要目標(biāo)的單目標(biāo)尋優(yōu)，使主要優(yōu)化目標(biāo)充分優(yōu)化，附帶優(yōu)化目標(biāo)通過保質(zhì)策略在尋優(yōu)過程中不斷優(yōu)化。

2.1 候選集設(shè)計

螞蟻在尋跡之前，要預(yù)先設(shè)置候選集D、禁忌集T。候選集D中存放螞蟻下一步可選的節(jié)點，即螞蟻的可選路徑集；禁忌集T中存放螞蟻已經(jīng)過的節(jié)點，不允許再次選擇。合適的候選集設(shè)計可以保證生成解的可行性以及尋優(yōu)效率。劉曉陽等[12]為保障裝配序列可行，根據(jù)干涉矩陣，以裝配域為單位進行干涉檢查，將具有可裝配性的裝配單元組成了候選集。黃學(xué)文等[13]用蟻群算法求解基于OR子圖(or-subgraph)描述的多加工路徑柔性作業(yè)車間調(diào)度問題時，結(jié)合OR子圖的Allowed列表生成算法(簡稱ORA算法)生成候選集。以上文獻設(shè)計的候選集未考慮螞蟻路徑的壓縮，只要螞蟻到達到這個節(jié)點，下一步的所有可選節(jié)點都加入候選集。張潔等[14]研究了螞蟻路徑的壓縮策略，針對螞蟻可選路徑在搜索過程中移動范圍固定、不利于保持群體多樣性等缺點，提出一種通過衡量螞蟻節(jié)點加權(quán)散度來確定候選集大小、進而提高搜索效率的路徑壓縮方法。本文設(shè)計了兩種候選集：可選加工工序候選集、工序?qū)?yīng)的資源組合候選集。對于資源組合候選集，如果工序?qū)?yīng)工件是關(guān)鍵件，則應(yīng)保證當(dāng)前所選資源組合不會導(dǎo)致目前及以后的加工質(zhì)量低于閾值。

2.1.1工序候選集

工序選擇的螞蟻地圖是(N+1)×N(N為總工序數(shù))節(jié)點的網(wǎng)絡(luò)。由于工藝約束限制，每個工件在任意時刻至多有一道工序等待加工，因此每只螞蟻的實際可轉(zhuǎn)移個數(shù)不多于工件數(shù)n。候選集確定為n個工件未加工工序的第一道工序。例如，若有5個待加工工件，它們的總工序數(shù)分別為3、4、4、3、4，已加工工序數(shù)分別為1、1、4、3、1，則工序候選集S={O12，O22，O44，O52}。

2.1.2資源組合候選集

資源組合選擇的螞蟻地圖由總工序數(shù)N和總資源組合數(shù)Npair組成的N×Npair網(wǎng)絡(luò)構(gòu)成。對于給定的工序Oij，首先確定可完成Oij的工人、機床組合；接著判斷該工件是否為關(guān)鍵件。若為非關(guān)鍵件，則所有工人、機床組合即為候選集；否則，需確保關(guān)鍵件滿足閾值條件。資源候選集的確定步驟如下：

(1)找出加工該工件每道工序的最好資源組合Mijb和Wijb，得到該工件i可達到的最好加工質(zhì)量：

(16)

式中，ρMijb為機器Mijb的加工合格率；ρWijbMijb為工人Wijb操作機器Mijb的加工合格率。

(2)記初始加工質(zhì)量Qi=1。根據(jù)已完成工序所選的資源組合確定當(dāng)前工件能達到的最好加工質(zhì)量Qibn，找出加工該工序的全部資源組合B，由Qi和Qib得出全部資源組合中能使工件的加工質(zhì)量得以保證的加工該道工序的資源組合：

(17)

(18)

(3)確定該工序的加工資源[k，l]后，更新Qi：

Qi←Qiρkρlk

(19)

2.2 基于時窗的活動調(diào)度策略

調(diào)度策略的不同決定了調(diào)度結(jié)果的好壞。為此，MENG等[15]針對考慮能耗的DRCFJSP，給出了半主動解碼、主動解碼、貪婪解碼和考慮能耗解碼的4種調(diào)度策略。李兢堯等[16-17]對時窗、時窗操作做了詳細介紹，針對復(fù)雜制造環(huán)境下DRCFJSP的機床時窗與工人時窗的不同，提出了時間比較策略，為每道工序快速選擇滿足其工藝約束的最早調(diào)度時窗。除半主動解碼方法外，上述調(diào)度策略均可總結(jié)為：當(dāng)前工序的開工時間為所選資源約束下第一個可用時窗的最早開始時間或該工序前序工序的完工時間。實際調(diào)度中，雖然這種貪婪的思想能充分利用空閑時間，但所有的工序的調(diào)度都取可用時窗的最早可加工時間不一定會得到滿意的調(diào)度結(jié)果。圖1中，實線方框表示已加工工序，虛線方框表示待調(diào)度工序，虛箭線箭頭所指為調(diào)度結(jié)果工序，方框中的“2-1”表示工件2的第一道工序。圖1a、圖1b給出了在機床M1上使用基于貪婪思想的主動調(diào)度下的工序“2-2”和“4-1”的調(diào)度過程。時間窗[2，5]是工序“2-2”的第一個可插入的時間窗，其中，工序“2-2”于時間窗[2，5]的最早可開始時間2開始后，工序“4-1”不能再次插入時間窗[2，5]。為彌補基于貪婪思想方法的缺陷，本文改進了貪婪思想的解碼方式，提出一種基于時窗的活動調(diào)度策略。這兩種策略的差異體現(xiàn)在工序的開始時間是否為最早可用時窗的最早可開工時間。圖1c、圖1d所示的調(diào)度過程中，工序“2-2”的完工時間與第一個可用時間窗[2，5]的后序工序的開始時間相同，但開始時間不再是該工序在時間窗上的最早可開始時間，于是工序“4-1”在調(diào)度時可插入該時間窗，使得調(diào)度結(jié)果比前者更優(yōu)。

(a)工序插入時窗的最早可開始時間調(diào)度圖

若第一個可用時窗的開始時間WST晚于其前序工序的完工時間ETOi(j-1)，則該工序的開始時間STOij為WST。若第一個可用時窗i的開始時間WST早于其前序工序完工時間ETOi(j-1)，則需判斷其前序工序的完工時間是否為該工序的開始時間。于是，該工序的開始時間為

STOij=

(20)

(21)

其中，LenWi為時間窗i的時窗長度；AveTk為所有可在機床k上加工的全部工序的平均完成時間；Kijk表示工序Oij是否能在機床k上加工，若是，Kijk=1，否則，Kijk=0。

于是，在基于時窗的活動調(diào)度策略上，考慮人員柔性、設(shè)備屬性，設(shè)計了一種基于時窗的活動調(diào)度策略的DRCFJSP調(diào)度策略，時窗可分為工人加工時窗(工人參與加工的連續(xù)時間段)/空閑時窗(工人空閑的連續(xù)時間段)和機床加工時窗(機床加工的連續(xù)時間段)/空閑時窗(機床空閑的連續(xù)時間段)，如圖2所示，可以看出加工時間的確定需要使用2種規(guī)則。

圖2 考慮人員柔性和機床類型的DRCFJSP調(diào)度流程圖

規(guī)則1當(dāng)所選機床為普通機床或工人加工時間為零時，工序Oij的開工時間與Oi(j-1)結(jié)束時間、工人或機床可用空閑時窗的形式開工時間、完工時間有關(guān)，工序Oij的開始時間STijkl=min(STi(j-1)，Tws，Tms)，其中，Tws、Tms分別為工人l和機器k的可用時窗的開始時間。

規(guī)則2當(dāng)所選機床為數(shù)控機床且工人加工時間不為零時，工序Oij的開工時間不僅與Oi(j-1)的結(jié)束時間及機床可用時窗的開始結(jié)束時間有關(guān)，還與工人的時窗有關(guān)，如圖3所示。圖3描述了所選機床為數(shù)控機床、機床空閑時窗可用的情況下，工人空閑時窗也可用的4種情況，圖中符號Tws、Twe分別為工人l的可用時窗的開始時間和結(jié)束時間；Tms、Tme分別為機器k的可用時窗開始時間和結(jié)束時間，Tle為工序Oij的前序工序的完成時間。工序Oij的開始時間為

(a)情況1

STijkl=

(22)

(23)

式中，Tp為工人l加工時間的最晚結(jié)束時間。

2.3 考慮關(guān)鍵件加工質(zhì)量的保質(zhì)策略

有別于將加工質(zhì)量當(dāng)作多目標(biāo)中的一個指標(biāo)進行優(yōu)化和指定特定工人和機床處理關(guān)鍵件/關(guān)鍵工序的方法，本文提出的策略是將加工質(zhì)量f2看作附帶優(yōu)化目標(biāo)，即在關(guān)鍵件加工質(zhì)量得到保證的前提下，不斷提高關(guān)鍵件加工合格率閾值和總體加工質(zhì)量水平閾值。目標(biāo)f2的優(yōu)化策略的具體步驟如下：

(1)記螞蟻總數(shù)為Anum，初始滿足關(guān)鍵件加工合格率閾值的完工時間為C0、總體加工質(zhì)量水平為Q0。對所有解的加工質(zhì)量水平f2降序排序，若排在第μAnum位的f2μ>Q0，則更新Q0；否則，Q0不變，其中，μ的取值通常為0.1～0.2。

(2)在每次迭代過程中，將不滿足總體質(zhì)量閾值條件的解淘汰。

(3)判斷排在第μAnum位調(diào)度解的關(guān)鍵件加工合格率和完工時間f1μ，若f1μ>C0且關(guān)鍵件的加工合格率大于關(guān)鍵件質(zhì)量加工合格率閾值，則更新Q0和C0。

(4)以f1為目標(biāo)不斷進行優(yōu)化迭代直至達到終止條件。

對于關(guān)鍵件加工質(zhì)量閾值，由于生成解的過程保證了可行解始終滿足關(guān)鍵件的加工質(zhì)量閾值條件，所以本文的保質(zhì)策略無需考慮每個調(diào)度解各關(guān)鍵件是否滿足閾值條件。隨著總體加工質(zhì)量水平閾值的不斷提高，最終解的加工質(zhì)量將處于一個比較高的水平。

2.4 局部搜索

蟻群算法通過信息素和啟發(fā)式信息引導(dǎo)螞蟻從候選表中選擇作業(yè)，對于本文設(shè)計的兩級嵌套蟻群算法，螞蟻要經(jīng)過工序選擇和資源選擇兩個階段的狀態(tài)轉(zhuǎn)移過程。偽隨機比例狀態(tài)轉(zhuǎn)移規(guī)則既可以避免陷入局部極小值，又可避免因隨機造成的概率性劣向轉(zhuǎn)移，常能取得較好的全局優(yōu)化性能。工序選擇的狀態(tài)轉(zhuǎn)移規(guī)則如下：

POijOxy=

(24)

(25)

資源選擇的狀態(tài)轉(zhuǎn)移規(guī)則如下：

(26)

(27)

2.5 信息素更新

第i只螞蟻anti在搜索后，需要更新螞蟻地圖中所遍歷路徑的信息素。精英蟻群策略能使算法在收斂的同時具有較好的全局搜索能力和較高的搜索效率。工序選擇和資源選擇的信息素更新規(guī)則分別為

(28)

(29)

(30)

(31)

式中，Q為常數(shù)；ρ為信息素揮發(fā)系數(shù)；p為精英螞蟻路徑組合；t表示第t次迭代。

求解考慮關(guān)鍵件加工質(zhì)量的雙資源約束的柔性作業(yè)車間調(diào)度問題的兩級嵌套蟻群算法的流程如圖4所示。

圖4 算法流程圖

3 實驗

為測試本文設(shè)計的兩級嵌套蟻群算法在求解考慮關(guān)鍵件加工質(zhì)量DRCFJSP的性能，在CPU-I5 1.19 GHz、內(nèi)存8.00 GB的PC機上使用Python 3.7.0編程運行和實現(xiàn)。算法參數(shù)設(shè)置如下：循環(huán)次數(shù)K=200，螞蟻總數(shù)Anum=30，信息揮發(fā)數(shù)ρ=0.1，初始信息素τ0=1，信息素啟發(fā)因子α=1，期望啟發(fā)因子β=5，P0=0.8，P1=0.8，P2=0.5，信息素增強系數(shù)Q=1。每個算例求解20次，每次求解過程中，當(dāng)最優(yōu)解連續(xù)10代不更新時，結(jié)束運行。

3.1 算例1

將文獻[11]給出的DRCFJSP實際應(yīng)用案例作為算例1，在不改變原問題的基礎(chǔ)上，為保證算例符合本文問題，對算例重新進行描述，即將非機加工工序(鉗、熱處理、檢驗等)時間看作是后道機加工工序的準(zhǔn)備時間，其余描述不變。

文獻[11]只考慮工人操作效率的異質(zhì)性，未考慮工人操作每臺機床的實際合格率不同，于是，本文在原始算例的基礎(chǔ)上，增加了機床和工人操作某道工序的加工合格率(機床k加工合格率ρk、工人l操作機床k的熟練度ρlk)，工序加工時間、各工件的工序數(shù)量與原算例一致。數(shù)控機床(機床1、2)的加工合格率高于普通機床(機床3～8)，設(shè)機床1～8的加工合格率為(0.996，0.992，0.984，0.985，0.986，0.983，0.985，0.982)；工人需參與普通機床的整個加工過程，對工序的實際加工質(zhì)量產(chǎn)生影響；工人只需參與數(shù)控機床的準(zhǔn)備工作，對實際加工質(zhì)量不產(chǎn)生影響，因此，根據(jù)文獻[11]對工人能力級別的區(qū)別系數(shù)，得到工人在各機床上的加工合格率矩陣：

E=[eij]8×8=

其中，elk為工人l操作機床k的加工合格率，elk=0表示工人l不可操作機床k。文獻[11]中，指定人員加工工件3、4、7、8的關(guān)鍵工序，于是本文選擇工件3、4、7、8為關(guān)鍵件。文獻[11]中關(guān)鍵工序指定特定工人加工，本文根據(jù)所給工人在各機床上的加工合格率矩陣，設(shè)定關(guān)鍵件3、4、7、8對應(yīng)的工件加工質(zhì)量閾值為(0.945，0.935，0.935，0.936)。

使用文獻[11]的保質(zhì)策略，即不考慮工件的整體加工質(zhì)量，只將關(guān)鍵工序指派給加工合格率較高的工人和機床組合進行生產(chǎn)，利用本文設(shè)計的兩級嵌套蟻群算法求解算例1，得到甘特圖(圖5)。圖5中，黑框表示準(zhǔn)備時間，例如，機床1上工件8的第一道工序的準(zhǔn)備時間為文獻[1]中工序1(鉗)的時間；彩色框和灰框為機加工工序，其中，灰框表示關(guān)鍵工序，虛線框①中的關(guān)鍵工序指派給工人8完成，虛線框②中的關(guān)鍵工序指派給工人2完成。最優(yōu)調(diào)度解的完工時間為40.60，優(yōu)于文獻[1]中的總完工時間42.62。本文增加的合格率評價僅用作工件加工質(zhì)量的衡量，并未實際改變加工時間以及加工過程，且本文算法得到的最優(yōu)解優(yōu)于文獻[11]的最優(yōu)解，因此本文提出的兩級嵌套蟻群算法在求解DRCFJSP上有更好的性能。

圖5 算例1的調(diào)度甘特圖

為進一步驗證考慮關(guān)鍵件加工質(zhì)量的策略，將策略1(將關(guān)鍵工序指派給特定工人進行加工的保質(zhì)策略[1])、策略2(整體保質(zhì)策略[9])和本文策略進行對比，迭代結(jié)果如圖6所示，可以看出，在主要優(yōu)化目標(biāo)完工時間相同的條件下，策略2與本文策略的總體加工質(zhì)量水平和關(guān)鍵件加工質(zhì)量水平具有一定優(yōu)勢，可見指派關(guān)鍵件/關(guān)鍵工序給特定工人進行加工并不能保證很高的整體加工質(zhì)量和關(guān)鍵件加工質(zhì)量；但策略2的總體加工質(zhì)量水平高于本文策略，但策略2的關(guān)鍵件加工質(zhì)量水平低于本文策略，可見本文所提策略在一定程度上能防止加工質(zhì)量向非關(guān)鍵件偏移。

(a)完工時間 (b)總體加工質(zhì)量水平 (c)關(guān)鍵件加工質(zhì)量水平

各工件的加工合格率情況如圖7所示，策略2的一些非關(guān)鍵件如J1、J2、J5、J6的加工質(zhì)量均高于本文策略最優(yōu)解的加工質(zhì)量，但關(guān)鍵件J3、J7的加工質(zhì)量并沒有達到質(zhì)量閾值，導(dǎo)致關(guān)鍵件加工質(zhì)量得不到保障，可見只考慮整體加工質(zhì)量會導(dǎo)致部分非關(guān)鍵件搶占關(guān)鍵件的優(yōu)秀加工資源。本文策略得到的最優(yōu)解中，所有關(guān)鍵件均能滿足加工質(zhì)量的要求，因此本文策略有效。

圖7 不同策略對應(yīng)各工件加工質(zhì)量柱狀圖

3.2 算例2

算例1規(guī)模太小，僅需很少的迭代就能收斂，且沒有考慮準(zhǔn)備時間。為進一步驗證本文所提保質(zhì)策略和兩級嵌套蟻群算法的可行性，在BRANDIMARTE[18]設(shè)計的FJSP算例mk01～mk10上增加了工人數(shù)量及各工人對應(yīng)的可操作機器集[19]，形成算例2。根據(jù)本文問題的特點，增加以下條件：任選全部機床的30%為數(shù)控車床，工序準(zhǔn)備時間服從U[2，8]的均勻分布；任選20%的工件為關(guān)鍵件，關(guān)鍵件加工質(zhì)量服從U[0.93，0.95]的均勻分布；普通機床和工人的加工合格率服從U[0.98，1.00]的均勻分布，數(shù)控機床的加工合格率服從U[0.994，1.000]的均勻分布，以驗證算法的可行性。表1給出了mk01～mk10的具體延伸情況和算例的測試結(jié)果(含對應(yīng)的關(guān)鍵件及其加工質(zhì)量要求)。算例mk01的規(guī)模為10×6，即工件數(shù)n=10，機器數(shù)m=6，工人數(shù)為4，數(shù)控機床的機器編號為2和4，關(guān)鍵件的編號為1和4，對應(yīng)的關(guān)鍵件加工質(zhì)量要求分別為0.934和0.943，最優(yōu)解的完工時間Cmax為56，整體加工質(zhì)量水平Q為10.591，工件1～10的加工質(zhì)量水平分別為0.946、0.957、0.947、0.947、0.949、0.950、0.933、0.945、0.951、0.942，關(guān)鍵件1的加工質(zhì)量水平為0.946，關(guān)鍵件4的加工質(zhì)量水平為0.947，均滿足對應(yīng)的關(guān)鍵件加工質(zhì)量要求。

表1 算例2測試結(jié)果

由表1可以看出，各算例最優(yōu)解得到的關(guān)鍵件的加工質(zhì)量均能滿足其加工質(zhì)量要求。圖8為算例2中mk01的迭代收斂圖，可以看出，隨著總完工時間的縮短，加工質(zhì)量閾值一直上升，平均加工質(zhì)量及最優(yōu)解的加工質(zhì)量都不斷上升并最終收斂，總完工時間的最優(yōu)解為56，加工質(zhì)量水平為22 369 740。由圖9(算例mk01的最優(yōu)解的甘特圖)可以看出工人操作普通機床和數(shù)控機床在加工時間的差異。數(shù)控機床2加工工件2的第一道工序時，工人僅負責(zé)加工的準(zhǔn)備工作外；普通機床3加工工件1時，工人除需完成準(zhǔn)備工作，還需參與整個工件加工的過程。機器連續(xù)加工同一工件時，后道工序的準(zhǔn)備工作可以省略，如機床2上工件8的最后兩道工序、機床1上工件6的相鄰兩工序。本文設(shè)計的兩級嵌套蟻群算法不僅可以解決考慮關(guān)鍵件加工質(zhì)量的相關(guān)問題，還能避免工序間準(zhǔn)備時間的冗余，以及人員在普通機床和數(shù)控機床之間的差異問題。

圖8 算例mk01迭代收斂圖

圖9 mk01調(diào)度甘特圖

4 結(jié)論

為解決雙資源約束柔性作業(yè)車間調(diào)度問題，本文考慮關(guān)鍵件的加工質(zhì)量及整體工件加工質(zhì)量，設(shè)計了帶保質(zhì)策略的兩級嵌套蟻群算法。針對工人、機床時窗差異，以及工人操作普通機床和數(shù)控機床之間的差異，提出了一種基于時窗的活動調(diào)度策略。實驗分析了2種保質(zhì)策略和考慮關(guān)鍵件的保質(zhì)策略的整體加工質(zhì)量水平與關(guān)鍵件加工質(zhì)量水平的差異，發(fā)現(xiàn)在資源有限型車間內(nèi)，考慮關(guān)鍵件的保質(zhì)策略能夠更好地解決非關(guān)鍵件搶占關(guān)鍵件加工資源的問題。

加工質(zhì)量問題是實際制造系統(tǒng)亟待解決的問題之一，本文目前解決的是靜態(tài)調(diào)度問題，后續(xù)將研究加工質(zhì)量的動態(tài)調(diào)度問題，包括在動態(tài)加工的場景中如何實時跟蹤工件的加工質(zhì)量，以及快速響應(yīng)因加工質(zhì)量變化帶來的調(diào)度決策，嘗試設(shè)計實時性和準(zhǔn)確性更高的資源約束型生產(chǎn)調(diào)度算法。