染缸排產(chǎn)建模及滑動時間窗啟發(fā)式調(diào)度算法

隗千千，董興業(yè)，王煥政

(北京交通大學 計算機與信息技術(shù)學院，北京100044)

0 引言

染缸排產(chǎn)是為多染缸、多訂單、分批次的染色任務制定生產(chǎn)計劃的問題，需要考慮生產(chǎn)訂單分配、工藝約束、訂單要求和客戶要求等限制因素，是一個組合優(yōu)化問題。由于缺乏可用的軟件工具，我國的印染車間制定染缸排產(chǎn)計劃時很大程度上還依賴于計劃人員的經(jīng)驗。其染色工藝約束復雜，生產(chǎn)任務規(guī)模大，給計劃人員帶來了巨大的壓力，排產(chǎn)方案的質(zhì)量也難以保證。

近年來，許多學者在染缸排產(chǎn)模型及調(diào)度算法方面作了許多研究。通常，染缸排產(chǎn)模型主要考慮完成時間、洗缸成本、染缸切換成本等。文獻[1]以最小化染色成本、洗缸成本、庫存成本、延誤代價為優(yōu)化目標，提出了一種基于啟發(fā)式規(guī)則的改進極值優(yōu)化算法用于求解小規(guī)模問題；文獻[2]考慮了產(chǎn)品拆分分批，最小化產(chǎn)品延誤代價和切換成本，使用遺傳算法求解；文獻[3]考慮了訂單的拆分和合并分批，以最小化延誤時間和最大化染缸利用率為目標，設計了構(gòu)造型啟發(fā)式方法；文獻[4]以延誤代價和染缸利用率為目標，考慮相容作業(yè)組的拼缸、與作業(yè)順序相關(guān)的設置時間，構(gòu)建了問題模型并提出了一種多目標人工蜂群算法；文獻[5]針對機器相同的排產(chǎn)調(diào)度問題，考慮產(chǎn)品分批、與作業(yè)順序相關(guān)的設置時間等因素，以最小化完工時間為目標，設計了混合整數(shù)線性規(guī)劃模型，將產(chǎn)品的調(diào)度過程分為批次構(gòu)建和批次調(diào)度兩個子問題，使用多種群遺傳算法求解；文獻[6]在染缸容量上限和下限約束、訂單優(yōu)先級約束、洗缸約束等約束條件下，使用量子遺傳算法，對訂單進行拆分與合并分批，可完成小規(guī)模問題的染缸排產(chǎn)調(diào)度。除了針對印染問題的研究，與之最相似的問題是批處理調(diào)度問題[7-10]。該類問題應用背景廣泛，包括半導體生產(chǎn)[11]、鋼鐵制造[12]、輪胎制造[13]、印刷線路板生產(chǎn)[14]等。若簡化約束條件，染缸排產(chǎn)調(diào)度問題屬于異構(gòu)并行機、作業(yè)大小不同、作業(yè)組不相容、設置時間與作業(yè)順序相關(guān)的批處理調(diào)度問題，是NP-難問題。

實際生產(chǎn)中問題的規(guī)模往往很大，約束條件和生產(chǎn)限制因素更加復雜，對排產(chǎn)效率要求也比較高。一般情況下，一個染紗車間的月訂單量至少有500個，染缸數(shù)量有幾十個，排產(chǎn)調(diào)度時需要考慮產(chǎn)品的特殊工藝(如熒光產(chǎn)品)、頭缸生產(chǎn)以及染缸的維護計劃等約束。此外，現(xiàn)有生產(chǎn)計劃對染缸排產(chǎn)還存在一定的限制。相比之下，上述對染缸排產(chǎn)問題的研究中所構(gòu)建的問題模型未考慮特殊工藝、頭缸生產(chǎn)、染缸維護計劃、進出缸并發(fā)約束，也未考慮增量調(diào)度，與實際生產(chǎn)條件相差較大，限制了算法的適用性；另外，雖然文獻中批處理調(diào)度問題的研究成果較多，但是這些算法不能用于本文所提出的問題模型。綜上所述，染缸排產(chǎn)模型及優(yōu)化算法在實用性和適用性方面亟待提高。

本文根據(jù)印染企業(yè)的生產(chǎn)需求，以最小化延誤代價、染缸切換成本、洗缸成本為目標，在已有問題模型的基礎上，考慮產(chǎn)品頭缸、禁熒光、染缸維護、現(xiàn)有生產(chǎn)計劃安排等新的生產(chǎn)約束，建立更符合實際生產(chǎn)條件的染缸排產(chǎn)增量調(diào)度模型，并基于啟發(fā)式規(guī)則設計求解算法，提高排產(chǎn)效率，節(jié)約生產(chǎn)成本。

1 染缸排產(chǎn)調(diào)度問題模型

1.1 問題描述

染缸排產(chǎn)調(diào)度問題是通過對產(chǎn)品進行拆分分批或者合并分批將多個產(chǎn)品安排到多臺染缸中排產(chǎn)，需解決的問題是在不改變原生產(chǎn)計劃中產(chǎn)品批次劃分的情況下，對新增產(chǎn)品進行批次劃分，為各批次安排染缸，確定批次開始加工時間，在滿足各種約束條件的同時使調(diào)度目標最優(yōu)。

印染企業(yè)的生產(chǎn)訂單首先由銷售部門下發(fā)給計劃部門，然后計劃部門根據(jù)實際生產(chǎn)情況制定生產(chǎn)計劃，并傳達給生產(chǎn)車間。每個產(chǎn)品從進入企業(yè)資源計劃系統(tǒng)到包裝入庫的處理過程可表示為如圖1所示的頂點活動(Activity On Vertex，AOV)圖。產(chǎn)品調(diào)度僅需要確定C4和C5的開始時間；由于排產(chǎn)過程不涉及C0和C6，因此它們可看作虛節(jié)點，時長為0天，其他節(jié)點的時長與具體產(chǎn)品有關(guān)；當產(chǎn)品沒有頭缸時，不需要工序C4。

圖1 生產(chǎn)流程AOV圖Fig. 1 AOV diagram of production process

染缸排產(chǎn)調(diào)度問題的約束條件包括以下幾個方面：

1) 染缸容量限制約束。批次加工量必須在所選染缸容量上限和下限之間，相同的容量上限為同一缸型。

2) 染缸維護時間約束。染缸有多個維護時間段，維護期間染缸不可用。

3) 加工時間約束。圖1中各工序在執(zhí)行前，其前序工序必須完成，否則應延遲排產(chǎn)，延遲時間為其前序工序的最大準備時長。

4) 禁熒光約束。染缸加工熒光產(chǎn)品后需連續(xù)加工一定缸數(shù)的非熒光產(chǎn)品之后才能加工禁熒光產(chǎn)品。

5) 進出缸并發(fā)約束。批次在開始加工前和加工結(jié)束后有進缸和出缸操作，同一時刻執(zhí)行進缸和出缸操作的數(shù)量有一個上限，該限制和工人資源量有關(guān)。

6) 拼缸約束。幾個產(chǎn)品合并在一個批次加工時，稱為拼缸；拼缸批次的各產(chǎn)品必須來自同一產(chǎn)品組。

7) 拆缸約束。一個產(chǎn)品拆分成幾個小的批次加工以適應染缸容量，稱為拆缸。為了保證大貨產(chǎn)品的生產(chǎn)質(zhì)量，不同量級的產(chǎn)品的最小拆分閾值不同，拆分的各個批次中，最多有一個批次的生產(chǎn)量小于該拆分閾值，拆缸需盡可能拆分成大的批次；原生產(chǎn)計劃中已經(jīng)拆缸的批次不允許再次拼缸；頭缸不允許拆缸。

8) 原生產(chǎn)計劃中已經(jīng)拆缸或者拼缸的產(chǎn)品，再次調(diào)度時不再進行批次劃分。

本文首先對數(shù)據(jù)作了預處理：依次檢查產(chǎn)品的各項工序，計算產(chǎn)品的延遲排產(chǎn)時間，記為產(chǎn)品的釋放時間。例如，某產(chǎn)品的C1、C2、C3工序未完成，則其延遲排產(chǎn)天數(shù)為上述三工序的最大準備時長。由加工時間約束可知，產(chǎn)品的最早加工時間應不早于釋放時間。

1.2 模型構(gòu)建

1.2.1 符號定義

1)集合和索引。

M為染缸集合，索引m；J為產(chǎn)品集合，索引i、j；B為批次集合，索引b、c；Jb為批次b的產(chǎn)品集合，Bj為產(chǎn)品j的批次集合；F為產(chǎn)品分組集合，索引f，Jf為組f的產(chǎn)品集合；FL_J為熒光的產(chǎn)品集合，F(xiàn)L_B為熒光的批次集合，F(xiàn)L0_J為禁熒光的產(chǎn)品集合，F(xiàn)L0_B為禁熒光的批次集合；SP為并發(fā)時間段集合，SMm為染缸m的維護時間集合，索引sp。

2)變量。

mb表示批次b使用的染缸，sb為批次b的開始加工時間，eb為批次b的結(jié)束加工時間，tb為批次b的染色類型；qjb表示產(chǎn)品j在批次b中的加工數(shù)量，hjb表示產(chǎn)品在批次中的生產(chǎn)狀態(tài)(若產(chǎn)品j在批次b中為頭缸，則值為1，否則為0)。

Stt′為從染色類型為t到染色類型為t′的洗缸時間；Pju為產(chǎn)品j在缸型為u的染缸的加工時長；ssp為時間段sp的開始時間，esp為時間段sp的結(jié)束時間，nsp為時間段sp的進出缸并發(fā)數(shù)量。

3)參數(shù)。

Z表示頭缸未確認時延遲排產(chǎn)時長，U表示批次任務的出缸時長，L表示批次任務的進缸時長，V表示熒光批次和禁熒光批次間隔序列長度，P表示進出缸最大并發(fā)數(shù)目。

1.2.2 模型表示

在染缸排產(chǎn)建模時，目標函數(shù)中主要考慮排產(chǎn)延誤、洗缸成本、染缸切換，而模型實用性主要體現(xiàn)在約束條件中。

用S表示一個可行解，則每個染缸的執(zhí)行序列為一個部分解，染缸m部分序列可表示為Sm=(b1,b2,…,bk)。同一產(chǎn)品的不同批次之間更換染缸會造成批次的質(zhì)量差異，產(chǎn)生染缸切換成本，染缸m上的批次序列的染缸切換成本為：

(1)

其中：

(2)

同一染缸的相鄰批次之間需要洗缸，洗缸時間與相鄰批次的染色類型有關(guān)，染色類型有白、淺、中、深四種，一般來說，淺色批次到深色批次的洗缸時間小于深色到淺色批次的洗缸時間。Stt′表示加工完染色類型為t的批次后，在加工染色類型為t′的批次之前的洗缸時間。染缸m上的批次序列的洗缸成本為：

(3)

每個產(chǎn)品都有交貨日期，延期交貨會有一定的懲罰，懲罰大小取決于產(chǎn)品的優(yōu)先級權(quán)重和延誤時長，產(chǎn)品j的延誤代價可表示如下：

(4)

其中：

cj=max{eb|b∈Bj}

(5)

目標函數(shù)及約束條件如下：

(6)

s.t.

(7)

lap(sp,b)=0； ?m∈M,sp∈SMm,b∈Sm

(8)

(9)

min {sb}≥rj;?j∈J，b∈Bj

(10)

In(f0(b,Sm),Sm)-In(b,Sm)≥V;

?m∈M,b,b0∈Sm,b∈FL_B

(11)

nsp≤P;?sp∈SP

(12)

fj1=fj2;?b∈B,j1,j2∈Jb

(13)

|MBj|≤1;?j∈J,b∈Bj,MBj={b|qjb≤thj}

(14)

(15)

(16)

qjb,sb,eb∈N

(17)

式(6)定義了調(diào)度目標，是染缸切換成本、洗缸成本和延誤代價三項成本的線性和。

式(7)表示染缸容量約束，批次加工量(各產(chǎn)品在該批次中加工量之和)應在染缸容量上限和下限之間；式(8)和式(9)表示染缸維護時間約束，任意批次的加工時間都不與染缸維護時間重疊；式(10)表示加工時間約束，產(chǎn)品的任意批次開始加工時間都晚于釋放時間；式(11)表示禁熒光約束，熒光批次b與其之后的第一個禁熒光批次之間至少間隔V個批次；式(12)表示進出缸并發(fā)約束，任意時間段sp執(zhí)行進出缸操作的數(shù)量少于P；式(13)為產(chǎn)品的拼缸約束，批次中加工的產(chǎn)品都屬于同一產(chǎn)品組；式(14)為產(chǎn)品的拆缸約束，產(chǎn)品最多有一個批次加工數(shù)量小于拆缸閾值；式(15)為頭缸拆缸約束，若在批次中加工頭缸，則加工量為全部頭缸數(shù)量，即頭缸不允許拆分；式(16)為產(chǎn)品加工數(shù)量約束，產(chǎn)品總量等于已完成數(shù)量與各個批次加工數(shù)量之和；式(17)為變量的整數(shù)約束，即時間變量、批次數(shù)量均為整數(shù)。

問題模型中已知染缸數(shù)據(jù)、產(chǎn)品數(shù)據(jù)、現(xiàn)有生產(chǎn)計劃、排產(chǎn)參數(shù)等數(shù)據(jù)，求解產(chǎn)品的分批方案和新的排產(chǎn)計劃，其基本問題是并行批處理調(diào)度問題，已被證明是一個NP-難問題[15]，因此其衍生問題也是一個NP-難問題，采用傳統(tǒng)的數(shù)學規(guī)劃方法無法有效求解。染缸排產(chǎn)調(diào)度問題約束條件復雜，批次劃分和調(diào)度時間都是離散的，時間跨度較長，染缸和產(chǎn)品的數(shù)據(jù)規(guī)模較大，因此依據(jù)問題特點和模型約束，設計構(gòu)造型啟發(fā)式方法快速求解是實際生產(chǎn)的迫切要求。

2 染缸排產(chǎn)調(diào)度優(yōu)化算法

為簡化問題，作出如下假設：圖1中工序C1(向客戶確認顏色)、C2(原料備庫)、C3(生產(chǎn)復樣并確定復樣配方卡)的狀態(tài)隨調(diào)度日期更新，產(chǎn)品的釋放時間也隨之更新；批次一旦開始加工，就不能被中斷；當一個批次加工完成后，就從產(chǎn)品的原計劃生產(chǎn)列表中刪除，不再對下次調(diào)度產(chǎn)生影響；由于產(chǎn)品的頭缸不能拆缸，因此假設所有頭缸均存在單獨加工的缸型；缸型相同的染缸，其容量下限也相同；批次加工時間精確到分鐘，釋放日期、交貨日期精確到天。

圖2中所述產(chǎn)品調(diào)度算法是根據(jù)染缸的可用狀態(tài)和當前進出缸并發(fā)狀態(tài)，計算產(chǎn)品j最佳的分批方案和批次加工時間，基本步驟如下：

圖2 STWS算法流程Fig. 2 Flowchart of STWS algorithm

步驟1 若產(chǎn)品j的原計劃批次集合Bj不為空，則轉(zhuǎn)至步驟6；否則生成拼缸調(diào)度計劃PlanCj(動態(tài)拼缸算法)，即拼缸批次bj。

步驟2 若PlanCj不存在，則轉(zhuǎn)至步驟5；否則若PlanCj加工開始時間在workT內(nèi)，Planj←PlanCj，算法結(jié)束。

步驟3 若|Jbj|>1，則生成|Jbj|≤1的計劃PlanC0j(動態(tài)拼缸算法)；否則轉(zhuǎn)至步驟5。

步驟4 若PlanC0j存在且不會發(fā)生延誤，則Planj←PlanCj，算法結(jié)束；否則若產(chǎn)品當前加工部分不可拆缸，則算法結(jié)束。

步驟5 生成拆缸計劃PlanSj(拆缸算法)，令Planj←PlanSj。

步驟6 調(diào)整PlanSj批次，選擇合適的染缸和加工時間(批次最佳排序算法)，優(yōu)化延誤代價、換缸成本、洗缸成本，算法結(jié)束。

在使用動態(tài)拼缸算法和基于回溯搜索的拆缸算法對產(chǎn)品進行調(diào)度時，需要確定產(chǎn)品的待調(diào)度數(shù)量和產(chǎn)品的最晚加工完成日期。不同狀態(tài)下的產(chǎn)品調(diào)度數(shù)量不同，主要和頭缸有關(guān)，根據(jù)約束條件(15)和(16)，可得產(chǎn)品j的待調(diào)度數(shù)量qj′的計算方法為：

(18)

為降低延誤代價，產(chǎn)品發(fā)生延誤時，應該保證延誤最短，因此，在產(chǎn)品調(diào)度過程中，初次調(diào)度最晚加工完成日期(截止日期)均為交貨期，在不能成功調(diào)度時，最晚加工完成日期每次延后一天，進行迭代調(diào)度。

2.1 動態(tài)拼缸算法

動態(tài)拼缸(Dynamic Combination Batch，DCB)算法首先根據(jù)當前調(diào)度時間workT選擇滿足并發(fā)約束(12)的染缸集合。然后在同一最晚加工時間之前，對于集合中的每個染缸上，計算拼缸方案，將該組合問題轉(zhuǎn)化為一維背包問題，使用動態(tài)規(guī)劃算法計算產(chǎn)品j的最佳拼缸產(chǎn)品集合，并確定拼缸批次的加工時間，選擇第一個可行的拼缸批次返回。若所有拼缸批次都晚于最晚加工時間，則推遲該時間點，重新查找拼缸方案。最后是優(yōu)化階段，在可用染缸集合中查找拼缸批次評價指標最小的染缸，確定批次所用染缸及開始加工時間。以下是DCB算法偽代碼描述。

算法1 動態(tài)拼缸算法。

輸入：待調(diào)度產(chǎn)品j；

輸出：拼缸批次b。

計算產(chǎn)品j的可拼缸產(chǎn)品集合combJ：

combJ={j′|j′∈J,j′∈Jfj,rj′≤workT}

計算產(chǎn)品j和combJ中產(chǎn)品的待調(diào)度數(shù)量

IF(workM為空) RETURN NULL

初始化最晚加工完成日期combD←dj，拼缸標記combF← false，染缸訪問序號i← 0

WHILE (true)

WHILE (i<|workM|)

計算滿足容量約束(7)的拼缸產(chǎn)品組合combJmi

IF (combJmi為空)i←i+1

ELSE

計算b在mi的加工時間，令combF← true

IF (eb≤combD) BREAK

ELSEi←i+1

END WHILE

IF(combF==false) RETURN NULL

ELSE

IF (eb≤combD) BREAK

ELSE 更新combD←combD+1，i← 0

END WHILE

workM′為workM中滿足批次b容量約束的染缸，計算b在workM′中各個染缸mi的加工時間，得到新的批次bi，則可行批次集合comB={bi|ebi≤combD}

計算bi∈comB所用利用率prbi和洗缸代價csbi，選擇拼缸批次評價指標Cbi最小的批次b；RETURNb

上述染缸利用率和缸批次評價指標的計算方式為：

(19)

Cbi=umi(1-prbi)+csbi

(20)

2.2 拆缸算法

2.2.1 基于回溯搜索的拆缸算法

由于產(chǎn)品拆缸有最小閾值限制，并且產(chǎn)品拆分時盡可能拆分為大的批次，若使用簡單貪心算法直接選擇最大容量的染缸進行拆分，會產(chǎn)生很多拆缸方案不可行的情況，因此本文提出基于回溯搜索的拆缸算法(Batch split Algorithm based on Backtracking Search， BABS)。

BABS是一種隱枚舉算法，計算滿足約束條件最佳拆缸方案，由大到小選擇染缸，在每個染缸上盡可能地續(xù)缸生產(chǎn)，直至拆缸不可行，此時刪除當前方案中已安排的最小染缸，回溯查找可用染缸，然后繼續(xù)分批，其偽代碼描述如下。

算法2 基于回溯搜索的拆缸算法。

輸入：待調(diào)度產(chǎn)品j；

輸出：拆缸方案PlanSj。

計算產(chǎn)品j的待調(diào)度數(shù)量qj′

獲得可用染缸workM，按缸型降序、可用時間升序排序

初始化最晚加工完成日期splitD←dj

初始化基本變量：可延誤拆缸標記splitF← false，拆分批次集合PlanSj← NULL，所用染缸的可加工最大量uC← 0、最小量lC← 0，染缸訪問序號i← 0

WHILE (true)

從i開始順次查找第一個滿足式(21)或(22)的染缸mi

IF (mi不存在)

WHILE (PlanSj!=NULL)

回溯查找新的可用染缸mi；BREAK

END WHILE

IF (mi不存在)

IF (splitF==true)

//可延期拆缸

splitD←splitD+1，重新初始化基本變量

CONTINUE

ELSE 產(chǎn)品拆缸失敗，算法異常結(jié)束

WHILE (true)

IF (mi滿足式(21)或(22))

在染缸mi上生成新的批次b

ELSE BREAK

IF (eb>splitD)

//可通過延期拆缸

更新splitF← true，i←i+1；BREAK

ELSE

lC←lmi+lC，uC←umi+uC

PlanSj←PlanSj∪b

END WHILE

IF (lC≤qj′≤umi) BREAK

END WHILE

調(diào)整PlanSj批次的加工數(shù)量，使相同缸型的批次加工數(shù)量盡可能均勻；RETURNPlanSj

回溯查找染缸的方法：首先刪除PlanSj最后加入的批次newb，然后令i← 0，從i開始順次查找第一個比newb所用缸型小且滿足式(21)或式(22)的染缸mi。

染缸可用條件判斷式：

lmi+lC≤qj′≤umi+uC

(21)

lmi≥thj并且lmi+lC≤qj′

(22)

2.2.2 拆缸優(yōu)化算法

上述基于回溯搜索的拆缸算法中的基本準則是優(yōu)先選擇大缸，查找滿足染缸容量約束和產(chǎn)品拆缸約束的拆缸組合方案，這種方式得到的拆缸方案大多使用染缸的缸型種類比較多，一個產(chǎn)品需要在多個染缸上生產(chǎn)，染缸切換成本比較高，產(chǎn)品質(zhì)量穩(wěn)定性也變差，因此最佳的拆缸方案是在較大的缸中續(xù)缸(而不是選擇最大的染缸和較小的染缸拆缸)。

拆缸優(yōu)化(Batch Split Optimization，BSO)算法是在基本拆缸方案的基礎上，保證最晚加工完成時間相同、使用拆缸批次數(shù)量相同和優(yōu)先選用大缸的準則，優(yōu)化洗缸成本和染缸切換成本。每一輪優(yōu)化都是在同一個最晚加工完成時間前，將生產(chǎn)量均分到較小的染缸中，如果不可行，則保留最大的一個批次，均分剩余加工部分，直到所有批次都被保留或者得到可行方案。以下是算法的偽代碼描述。

算法3 拆缸優(yōu)化算法。

輸入：基礎拆缸方案PlanSj；

輸出：優(yōu)化拆缸方案OPlanSj。

根據(jù)計算產(chǎn)品j的待調(diào)度數(shù)量qj′

獲得可用染缸workM，可用缸型typeM，按缸型降序、可用時間升序排序

根據(jù)PlanSj計算最晚加工完成日期splitD=max {eb|∈PlanSj}

初始化待拆缸數(shù)量n← |PlanSj|，所用染缸的可加工最大量uC← 0、最小量lC← 0；將PlanSj按照缸型從大到小排序

IF (n==1) RETURNPlanSj

WHILE (|PlanSj|>1且n>1)

在typeM中查找n缸可加工qj′的染缸m：

n*lm+lC≤qj′≤n*um+uC

IF (染缸m不存在)

刪除PlanSj中使用染缸缸型最大的批次bmax，

OPlanSj←OPlanSj∪bmax

ELSE

在splitD之前，在所有缸型為um的可用染缸中優(yōu)先續(xù)缸加工n個批次，加入集合OPlanSj中

END WHILE

調(diào)整OPlanSj批次的加工數(shù)量，使相同缸型的批次加工數(shù)量盡可能均勻；

RETURNOPlanSj

2.3 批次最佳排序算法

使用BABS計算產(chǎn)品j的拆缸方案PlanSj(|PlanSj|>1)時，僅考慮交貨日期之前每個染缸上的最大加工能力，優(yōu)先選擇了開始可用時間最早的染缸。由于染缸有維護計劃，可能發(fā)生這種情況：可用時間最早的染缸，其維護時段很長且開始時間很早，進而可用時間段相對其他同缸型的染缸較短，批次選擇染缸數(shù)目較多。一方面會增加洗缸成本，另一方面也會增加切換成本，導致產(chǎn)品質(zhì)量不穩(wěn)定。

在原生產(chǎn)計劃中已經(jīng)拆缸或者拼缸的產(chǎn)品，產(chǎn)品的批次劃分已經(jīng)確定，但是具體的染缸未確定，因此需要確定合適的染缸以及加工時間。

以上兩種場景都需要進行批次調(diào)度，本文設計了批次最佳排序(Batch Optimal Sorting，BOS)算法，調(diào)整批次在各個染缸上的生產(chǎn)順序，使得產(chǎn)品j的延誤時間最短，染缸切換成本、洗缸成本最小。將產(chǎn)品的各個批次按照缸型分組，對使用同一種染缸缸型的批次，統(tǒng)一在指定缸型的染缸上調(diào)度，每一組都搜索一個最長續(xù)缸方案。以下是算法步驟描述：

步驟1 設置最佳方案最晚加工完成日期combD為max{eb|b∈PlanSj}。

步驟2 將PlanSj中的批次按照批次所使用缸型降序排序，計算PlanSj使用的所有染缸缸型集合MType，設置MType訪問序號i為0，最佳調(diào)整方案為OPlanSj。

步驟3 對染缸進行篩選，獲得指定缸型染缸workM。

步驟4 若訪問序號i≥|PlanSj|，則批次調(diào)整完成，算法結(jié)束；否則，獲得PlanSj中使用染缸缸型為tyi的批次Btyi，獲得workM中缸型為tyi的染缸Mtyi。

(23)

2.4 進出缸并發(fā)控制策略

由于整個調(diào)度過程是按照時間先后順序進行的，并發(fā)時間段的占用不可逆，調(diào)度時每個批次可用時間段僅和當前并發(fā)狀態(tài)和染缸狀態(tài)相關(guān)。

上述DCB算法、BABS、BSO算法和BOS算法在查找批次在染缸上的可用時間段時，需要嚴格滿足染缸的維護時間約束和并發(fā)時間段約束(進出缸時間段同時滿足并發(fā)約束)；產(chǎn)品生成可行計劃后，按照批次的時間先后順序，依次分配到指定染缸上，每分配一個批次，都重新劃分時間段，更新集合SP以及各時間段的并發(fā)數(shù)量nsp。

3 實驗評測

本章首先給出了實驗所用的參數(shù)和數(shù)據(jù)集，然后將STWS算法與人工排產(chǎn)方案進行對比，最后對算法的增量調(diào)度進行評測。

本文所使用的產(chǎn)品和染缸數(shù)據(jù)均從真實數(shù)據(jù)集中隨機抽取，調(diào)度日期為2018年4月1日，染色類型均勻分布。

根據(jù)產(chǎn)品生產(chǎn)量將產(chǎn)品分為4類：小(1≤qj≤100)、中(100

表1列出了算法需要的參數(shù)取值列表。

表2列出了實驗中使用的測試數(shù)據(jù)集，其初始調(diào)度計劃均為空。其中第6組數(shù)據(jù)是第3組數(shù)據(jù)的各個產(chǎn)品的交貨期整體提前1～5天所得，其他數(shù)據(jù)與3號相同，第7、8、9組數(shù)據(jù)是對第4組數(shù)據(jù)部分處理得到的：第7組數(shù)據(jù)延遲了產(chǎn)品的釋放日期；第8組數(shù)據(jù)減小了可拼缸數(shù)目，即在產(chǎn)品數(shù)量相同的情況下增加了分組數(shù)目；第9組數(shù)據(jù)增加了熒光產(chǎn)品所占比例。

表1 參數(shù)取值列表 Tab. 1 List of parameter values

表2 實驗中使用的數(shù)據(jù)集 Tab. 2 Dataset used in the experiment

人工排缸方案一般是由經(jīng)驗豐富的計劃員完成，約束執(zhí)行往往不是很嚴格，當實際排產(chǎn)發(fā)生約束沖突時，只能通過延遲染缸的后續(xù)批次或者取消某些批次來緩解，使得排產(chǎn)不能按照原計劃實施。這里使用普通規(guī)則(General Rule，GR)算法來模擬人工排缸過程，并與STWS算法對比。與STWS類似，GR算法是按照產(chǎn)品的優(yōu)先級順序(交貨日期升序、產(chǎn)品優(yōu)先級權(quán)重降序、釋放日期升序排序)，依次對產(chǎn)品進行調(diào)度；但是GR算法在產(chǎn)品調(diào)度時沒有使用最優(yōu)調(diào)度策略，而是使用貪心方法對產(chǎn)品進行拆缸和拼缸；批次調(diào)度時，選擇洗缸時間最短的染缸依次調(diào)度，不再進行迭代優(yōu)化。表3為GR算法的調(diào)度結(jié)果。

表3 GR算法調(diào)度結(jié)果 Tab. 3 Scheduling results using GR algorithm

使用STWS進行調(diào)度，可得到如表4所示的調(diào)度結(jié)果，其中，延誤成本優(yōu)化比例=(GR算法延誤成-STWS算法延誤成本)/GR算法延誤成本，同理可得切換成本優(yōu)化比例、洗缸成本優(yōu)化比例。從調(diào)度結(jié)果可以看到，在數(shù)據(jù)規(guī)模適中(產(chǎn)品數(shù)量在100到500左右)的情況下，該算法可在10 s內(nèi)給出可行方案。相對于GR算法，STWS算法的染缸切換成本、洗缸成本明顯減小，批次數(shù)量有所減少、拼缸批次有所增加，染缸利用率明顯提高，以上結(jié)果說明動態(tài)拼缸算法和拆缸算法有利于更好地利用染缸的生產(chǎn)能力；在延誤代價方面，當數(shù)據(jù)規(guī)模較大時，STWS算法優(yōu)化效果顯著，最高可優(yōu)化50%以上，數(shù)據(jù)規(guī)模較小時，優(yōu)化不明顯，這是因為產(chǎn)品數(shù)據(jù)較少時，可優(yōu)化空間也有限；除第0組數(shù)據(jù)外，洗缸成本均有大幅度降低，說明批次最佳排序算法能有效安排同一產(chǎn)品的不同批次進行續(xù)缸生產(chǎn)，從而節(jié)約了洗缸成本；對于第0組數(shù)據(jù)，洗缸成本上升的主要原因是批次調(diào)度時為增加續(xù)缸而選擇了首次洗缸成本較高的染缸。綜合以上幾個方面，STWS算法性能優(yōu)于GR算法。

表4 STWS算法相比GR算法的優(yōu)化結(jié)果 Tab. 4 Optimization results of STWS algorithm compared to GR algorithm

從表4的第4、7、8、9組數(shù)據(jù)的調(diào)度結(jié)果可以看到，在數(shù)據(jù)規(guī)模適中時，無論什么特點的數(shù)據(jù)，STWS算法性能都比較穩(wěn)定，延誤代價優(yōu)化程度穩(wěn)定在20%～30%，切換成本優(yōu)化程度在10%～20%，洗缸成本優(yōu)化程度在30%～50%，總體優(yōu)化效果都較為明顯。

第4組數(shù)據(jù)的產(chǎn)品數(shù)據(jù)是在第3組數(shù)據(jù)的產(chǎn)品數(shù)據(jù)的基礎上加入了一些新的產(chǎn)品得到的，因此將第3組數(shù)據(jù)的調(diào)度計劃作為第4組數(shù)據(jù)初始計劃用于增量調(diào)度測試，表5為增量調(diào)度結(jié)果。相對于第4組數(shù)據(jù)的無初始調(diào)度計劃的調(diào)度結(jié)果，增量調(diào)度的消耗時間短，這是由于增量調(diào)度時調(diào)度計劃中已經(jīng)分批的產(chǎn)品不再經(jīng)過分批過程，從而節(jié)約了調(diào)度時間。不過，由于已調(diào)度過的產(chǎn)品的批次劃分不能改變，減小了優(yōu)化空間，因此各項成本值均有所增加，拼缸批次數(shù)量減少，染缸利用率有所降低。

表5 STWS算法在第4組數(shù)據(jù)上的增量調(diào)度比較 Tab. 5 Incremental scheduling of STWS algorithm on the 4th data

4 結(jié)語

根據(jù)印染車間的生產(chǎn)需求，考慮產(chǎn)品的多樣化、異構(gòu)并行機、批次劃分約束、頭缸約束、禁熒光約束、染缸維護計劃等實際場景，建立了染缸排產(chǎn)增量調(diào)度模型。本文提出了構(gòu)造型啟發(fā)式算法——滑動時間窗調(diào)度(STWS)算法，按照一定的規(guī)則和邏輯對產(chǎn)品進行調(diào)度，最小化延誤代價、洗缸成本、染缸切換成本。產(chǎn)品調(diào)度過程中，設計了動態(tài)拼缸(DCB)算法和拆缸算法(BABS、BSO)進行批次劃分，使用批次最佳排序算法調(diào)度批次。通過實驗對比，檢驗了STWS算法增量調(diào)度的性能，在數(shù)據(jù)規(guī)模適中時，STWS算法能夠在10 s內(nèi)給出可行方案，相比人工排產(chǎn)方案，該算法顯著地降低了生產(chǎn)成本和延誤代價，目前已在某企業(yè)的生產(chǎn)系統(tǒng)中上線運營。

由于算法大多數(shù)場景都是增量調(diào)度模式，批次劃分僅限于第一次調(diào)度的產(chǎn)品，批次劃分確定后，批次的調(diào)度是影響生產(chǎn)代價的重要因素，因此批次調(diào)度的全局優(yōu)化是接下來的研究重點。