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

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

0 引言

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

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

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

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

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

1.1 問(wèn)題描述

染缸排產(chǎn)調(diào)度問(wèn)題是通過(guò)對(duì)產(chǎn)品進(jìn)行拆分分批或者合并分批將多個(gè)產(chǎn)品安排到多臺(tái)染缸中排產(chǎn)，需解決的問(wèn)題是在不改變?cè)a(chǎn)計(jì)劃中產(chǎn)品批次劃分的情況下，對(duì)新增產(chǎn)品進(jìn)行批次劃分，為各批次安排染缸，確定批次開始加工時(shí)間，在滿足各種約束條件的同時(shí)使調(diào)度目標(biāo)最優(yōu)。

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

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

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

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

2) 染缸維護(hù)時(shí)間約束。染缸有多個(gè)維護(hù)時(shí)間段，維護(hù)期間染缸不可用。

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

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

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

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

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

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

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

1.2 模型構(gòu)建

1.2.1 符號(hào)定義

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ā)時(shí)間段集合，SMm為染缸m的維護(hù)時(shí)間集合，索引sp。

2)變量。

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

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

3)參數(shù)。

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

1.2.2 模型表示

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

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

(1)

其中：

(2)

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

(3)

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

(4)

其中：

cj=max{eb|b∈Bj}

(5)

目標(biāo)函數(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)度目標(biāo)，是染缸切換成本、洗缸成本和延誤代價(jià)三項(xiàng)成本的線性和。

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

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

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

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

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

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

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

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

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

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

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

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

在使用動(dòng)態(tài)拼缸算法和基于回溯搜索的拆缸算法對(duì)產(chǎn)品進(jìn)行調(diào)度時(shí)，需要確定產(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′的計(jì)算方法為：

(18)

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

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

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

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

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

輸出：拼缸批次b。

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

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

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

IF(workM為空) RETURN NULL

初始化最晚加工完成日期combD←dj，拼缸標(biāo)記combF← false，染缸訪問(wèn)序號(hào)i← 0

WHILE (true)

WHILE (i<|workM|)

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

IF (combJmi為空)i←i+1

ELSE

計(jì)算b在mi的加工時(shí)間，令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容量約束的染缸，計(jì)算b在workM′中各個(gè)染缸mi的加工時(shí)間，得到新的批次bi，則可行批次集合comB={bi|ebi≤combD}

計(jì)算bi∈comB所用利用率prbi和洗缸代價(jià)csbi，選擇拼缸批次評(píng)價(jià)指標(biāo)Cbi最小的批次b；RETURNb

上述染缸利用率和缸批次評(píng)價(jià)指標(biāo)的計(jì)算方式為：

(19)

Cbi=umi(1-prbi)+csbi

(20)

2.2 拆缸算法

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

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

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

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

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

輸出：拆缸方案PlanSj。

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

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

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

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

WHILE (true)

從i開始順次查找第一個(gè)滿足式(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)

//可通過(guò)延期拆缸

更新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開始順次查找第一個(gè)比newb所用缸型小且滿足式(21)或式(22)的染缸mi。

染缸可用條件判斷式：

lmi+lC≤qj′≤umi+uC

(21)

lmi≥thj并且lmi+lC≤qj′

(22)

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

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

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

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

輸入：基礎(chǔ)拆缸方案PlanSj；

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

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

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

根據(jù)PlanSj計(jì)算最晚加工完成日期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個(gè)批次，加入集合OPlanSj中

END WHILE

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

RETURNOPlanSj

2.3 批次最佳排序算法

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

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

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

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

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

步驟3 對(duì)染缸進(jìn)行篩選，獲得指定缸型染缸workM。

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

(23)

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

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

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

3 實(shí)驗(yàn)評(píng)測(cè)

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

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

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

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

表2列出了實(shí)驗(yàn)中使用的測(cè)試數(shù)據(jù)集，其初始調(diào)度計(jì)劃均為空。其中第6組數(shù)據(jù)是第3組數(shù)據(jù)的各個(gè)產(chǎn)品的交貨期整體提前1～5天所得，其他數(shù)據(jù)與3號(hào)相同，第7、8、9組數(shù)據(jù)是對(duì)第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í)驗(yàn)中使用的數(shù)據(jù)集 Tab. 2 Dataset used in the experiment

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

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

使用STWS進(jìn)行調(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)給出可行方案。相對(duì)于GR算法，STWS算法的染缸切換成本、洗缸成本明顯減小，批次數(shù)量有所減少、拼缸批次有所增加，染缸利用率明顯提高，以上結(jié)果說(shuō)明動(dòng)態(tài)拼缸算法和拆缸算法有利于更好地利用染缸的生產(chǎn)能力；在延誤代價(jià)方面，當(dāng)數(shù)據(jù)規(guī)模較大時(shí)，STWS算法優(yōu)化效果顯著，最高可優(yōu)化50%以上，數(shù)據(jù)規(guī)模較小時(shí)，優(yōu)化不明顯，這是因?yàn)楫a(chǎn)品數(shù)據(jù)較少時(shí)，可優(yōu)化空間也有限；除第0組數(shù)據(jù)外，洗缸成本均有大幅度降低，說(shuō)明批次最佳排序算法能有效安排同一產(chǎn)品的不同批次進(jìn)行續(xù)缸生產(chǎn)，從而節(jié)約了洗缸成本；對(duì)于第0組數(shù)據(jù)，洗缸成本上升的主要原因是批次調(diào)度時(shí)為增加續(xù)缸而選擇了首次洗缸成本較高的染缸。綜合以上幾個(gè)方面，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í)，無(wú)論什么特點(diǎn)的數(shù)據(jù)，STWS算法性能都比較穩(wěn)定，延誤代價(jià)優(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ǔ)上加入了一些新的產(chǎn)品得到的，因此將第3組數(shù)據(jù)的調(diào)度計(jì)劃作為第4組數(shù)據(jù)初始計(jì)劃用于增量調(diào)度測(cè)試，表5為增量調(diào)度結(jié)果。相對(duì)于第4組數(shù)據(jù)的無(wú)初始調(diào)度計(jì)劃的調(diào)度結(jié)果，增量調(diào)度的消耗時(shí)間短，這是由于增量調(diào)度時(shí)調(diào)度計(jì)劃中已經(jīng)分批的產(chǎn)品不再經(jīng)過(guò)分批過(guò)程，從而節(jié)約了調(diào)度時(shí)間。不過(guò)，由于已調(diào)度過(guò)的產(chǎn)品的批次劃分不能改變，減小了優(yōu)化空間，因此各項(xiàng)成本值均有所增加，拼缸批次數(shù)量減少，染缸利用率有所降低。

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

4 結(jié)語(yǔ)

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

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