何 天 行

(杭州電子科技大學(xué)信息與控制研究所 浙江 杭州 310018)

0 引 言

調(diào)度是生產(chǎn)過程中一個非常關(guān)鍵的問題，因為它對生產(chǎn)的效率和資源利用率起到非常重要的作用。在過去的二十多年里，生產(chǎn)過程調(diào)度模型優(yōu)化這一研究領(lǐng)域受到了相關(guān)科研人員的極大重視，一方面這是受來自提高效率、削減成本的壓力和刺激，另一方面則是由于相關(guān)建模與求解技術(shù)的重大進步和計算能力的迅速增強。

基于連續(xù)時間的批處理短期調(diào)度模型在實際生產(chǎn)過程中應(yīng)用更加廣泛，一直被科研人員所重視。Pinto和Grossmann(1995)[1]提出基于連續(xù)時間的MILP模型，該模型主要解決多工序批處理短期調(diào)度問題，解決方法主要思路為在兩個平行時間軸上分配訂單和設(shè)備單元，然后使用一組變量集合來進行匹配，該組變量集合由四個參數(shù)構(gòu)成，分別為工序、訂單、時間槽、設(shè)備。Pinto等[2]又提出一種改進模型，創(chuàng)新地將預(yù)排序約束加入到設(shè)備時間槽中，核心方法是利用訂單預(yù)排序，用包含更少參數(shù)的變量替代，以此減少所需的計算時間。但該模型存在很明顯的短板，它只能用于預(yù)排序的訂單，仍無法解決順序約束。文獻[3]提出的MILP模型，主要針對于單工序多產(chǎn)品可并行生產(chǎn)的批處理短期調(diào)度問題，重點解決了訂單的順序問題，所用的方法是使用了一組含三個參數(shù)(前序訂單、后續(xù)訂單、設(shè)備)的變量集合。文獻[4]提出了一種新的對于批處理過程短期調(diào)度的連續(xù)時間模型，該模型最大的優(yōu)點是極大地減少了決策變量的數(shù)量，所采用的方法是將訂單和設(shè)備分離，但仍無法處理預(yù)排序問題的限制。文獻[5]提出的連續(xù)時間MILP一般模型，是基于順序依賴約束的多工序、多產(chǎn)品批處理短期調(diào)度問題。此模型創(chuàng)新地將預(yù)排序約束解放出來，讓研究者可以自己選擇是否考慮，在有效減少了變量數(shù)量的同時仍可以兼顧訂單排序和訂單切換。

王凌等[6]論述了分布式制造環(huán)境下，生產(chǎn)過程調(diào)度研究現(xiàn)狀和相關(guān)成果。范華麗等[7]認為調(diào)度模型需要經(jīng)受多變環(huán)境的考驗，在靜態(tài)環(huán)境下研究出的模型無法在實際生產(chǎn)中應(yīng)用。其主要論述了實際生產(chǎn)過程中存在擾動的動態(tài)調(diào)度研究現(xiàn)狀以及未來方向。劉民[8]認為在生產(chǎn)過程中會產(chǎn)生大量數(shù)據(jù)，對這些數(shù)據(jù)的研究可以有效地提高調(diào)度效率,本文著重論述了基于生產(chǎn)數(shù)據(jù)的調(diào)度方法研究情況。

目前，印染生產(chǎn)過程方向的調(diào)度研究十分有限。周曉慧等[9]提出基于時間槽描述生產(chǎn)過程調(diào)度模型,使用預(yù)排序規(guī)則和一個三維約束變量實現(xiàn)印染車間的精確調(diào)度。胡穎等[10]考慮了染色設(shè)備清洗和更換染料所需的時間，在此基礎(chǔ)上建立坯布顏色相關(guān)的調(diào)度模型。文獻[11]針對印染生產(chǎn)過程中生產(chǎn)設(shè)備之間切換成本、生產(chǎn)設(shè)備負荷平衡的問題,分析生產(chǎn)過程中的瓶頸設(shè)備來優(yōu)化瓶頸設(shè)備使用、提高利用率,研究訂單式印染生產(chǎn)過程，采用分層賦時著色Petri網(wǎng)(H TCPN)技術(shù)建立生產(chǎn)過程的模型。胡新暉等[12]采用再調(diào)度策略，在靜態(tài)調(diào)度的基礎(chǔ)上，考慮新訂單的加入，將所有未完成調(diào)度任務(wù)重新整合后再分配到相關(guān)設(shè)備作業(yè)。

1 印染生產(chǎn)工藝

建立生產(chǎn)過程優(yōu)化調(diào)度模型的前提是對相關(guān)生產(chǎn)工藝進行完備的描述和抽象。印染生產(chǎn)過程十分復(fù)雜，從坯布到成品要經(jīng)過很多道工序，如圖1所示，它描述了印染生產(chǎn)工藝與工序，包括燒毛、退漿、煮練、漂白、絲光、印花、染色、柔軟、拉幅、預(yù)縮、質(zhì)量檢測和產(chǎn)品包裝等。各工序內(nèi)的生產(chǎn)過程是連續(xù)的，但工序之間既有間斷也有連續(xù)，間斷時用小車把前道工序的半成品推到下道工序。把這些工序劃為三個階段：前處理工藝、印染工藝和后整理工藝。前處理主要有坯布的燒毛、退漿、煮練、漂白和絲光，其中煮練主要是去除布匹上的雜質(zhì)，絲光是增加布的光亮度；印染指染色和印花，是決定顏色的關(guān)鍵工序；后整理主要是印染后的柔軟、拉幅、預(yù)縮、質(zhì)量檢測和成品包裝。

圖1 印染生產(chǎn)工藝流程

不同產(chǎn)品在每一道工序的設(shè)備上加工速度是不同的，加工速度由車速來體現(xiàn)。同一產(chǎn)品在同一道工序的不同設(shè)備上加工速度也是不同的。

每一小車的布有幾百或幾千米，以一小車為單位安排一定的車速進行加工。兩道工序之間若是離散的，即用小車把半成品布推到下一道工序然后裝機生產(chǎn)，這一時間就是兩道工序之間的準備時間，這一時間與成品和設(shè)備無關(guān)，是固定的。

但染色機先染較深色的布，再染淺色的布，那么，染色機要清洗。而清洗的時間與兩個顏色的深、淺對比度有關(guān)，也就是說，染色機的切換生產(chǎn)的切換時間與產(chǎn)品有關(guān)。

印染車間總體上是一個訂單驅(qū)動的順序生產(chǎn)過程，其中單個工序內(nèi)是連續(xù)的，不同工序間既有連續(xù)也有間隙。

2 印染調(diào)度特征描述

從以上的工藝和生產(chǎn)流程看出，印染是順序生產(chǎn)過程，完成一個訂單需要經(jīng)過的工序多，但不同訂單所需經(jīng)過的工序不一定相同，工序內(nèi)是連續(xù)的，有的幾道工序連在一起也是連續(xù)的，如柔軟、拉幅和預(yù)縮一起是連續(xù)的，有的工序間是間隙的，如絲光到染色。因此，印染生產(chǎn)過程調(diào)度是Jop Shop問題，既有連續(xù)，又有間隙。

針對印染生產(chǎn)的特點和實際印染企業(yè)的經(jīng)營管理方式，在建立印染生產(chǎn)過程的優(yōu)化調(diào)度模型前，給出如下問題特征：

(1) 無材料等約束。在印染生產(chǎn)過程中，設(shè)備保持完好，不影響生產(chǎn)，原材料、工人和能源等都保證充足。

(2) 非搶占式生產(chǎn)。任何作業(yè)不能搶占已經(jīng)在加工作業(yè)的設(shè)備。因為，每一小車的布有幾百或幾千米，以一小車為單位安排一定的車速進行加工，不可能不加工完，布是連續(xù)的。

(3) 設(shè)備車速與產(chǎn)品和工序相關(guān)。產(chǎn)品在某道工序的加工車速只與設(shè)備相關(guān)，并且是固定的，因此，產(chǎn)品在每一工序的加工時間是可計算的。

(4) 設(shè)備準備時間和切換時間。染色機加工深淺對比度大的產(chǎn)品切換時間是不固定的，但可以給出切換時間表，工序間的坯布小車運輸加上設(shè)備開工準備時間是固定的。

(5) 24小時生產(chǎn)。有的印染企業(yè)兩班倒，有的三班倒，全天24小時生產(chǎn)。所以，每天按24小時調(diào)度。

(6) 為了表述簡單，假設(shè)一個訂單只有一個產(chǎn)品。

3 調(diào)度模型

數(shù)學(xué)模型由約束和調(diào)度目標組成，約束要求按一定的條件安排訂單在每一道工序的加工，而調(diào)度目標要求這種生產(chǎn)安排要最大程度地滿足調(diào)度目標。

3.1 模型約束描述

(1) 生產(chǎn)設(shè)備上相鄰加工訂單的約束。

(1)

式(1)表示：如果在同一工序l上存在兩個相鄰訂單i、j，并且使用工序l中的生產(chǎn)設(shè)備u來加工訂單i，那么訂單j就只能在生產(chǎn)設(shè)備u上進行加工。即在工序l上相鄰加工的訂單必須分配在同一臺生產(chǎn)設(shè)備上加工。

(2) 生產(chǎn)過程中任一工序上任一訂單最多存在一個唯一的直接后序加工訂單。

(2)

式(2)表示：任一臺生產(chǎn)設(shè)備一次只能加工一個訂單，被加工的訂單都有一個唯一的后續(xù)訂單，最后一個訂單除外。式(2)中不等號成立的條件：被加工的訂單是最后一個訂單。

(3) 生產(chǎn)過程中任一工序中任一訂單最多有一個前序訂單。

(3)

式(3)表示：任一臺生產(chǎn)設(shè)備上加工的訂單都有一個唯一的前序訂單，第一個加工訂單除外。

(4) 主要決策變量Wiu和Siu的關(guān)系。

Wiu≥Siu?i∈I,u∈U

(4)

式(4)描述的邏輯是：訂單i在生產(chǎn)設(shè)備u上的分配變量大于等于表示訂單i是否為生產(chǎn)設(shè)備u上第一個加工訂單的變量。如果訂單i是生產(chǎn)設(shè)備u上的第一個被加工的訂單，則此時變量Wiu和Siu的值都將等于1，等號成立。而如果訂單i是分配在生產(chǎn)設(shè)備u上加工但卻不是第一個被加工的訂單時，則Wiu>Siu，不等號成立，即Wiu=1，Siu=0。剩下最后一種情況是訂單i不在生產(chǎn)設(shè)備u上加工的情況，則兩個變量的值都為零，等號成立。

(5) 生產(chǎn)過程中在每臺生產(chǎn)設(shè)備上最多有一個初始訂單。

(5)

(6) 生產(chǎn)過程中任一工序中任一訂單必須由唯一一臺生產(chǎn)設(shè)備加工。

(6)

式(6)表示：在所有工序中任一訂單必須由唯一一臺生產(chǎn)設(shè)備進行加工。

(7) 工序中訂單起始時間和完成時間的關(guān)系。

?l,m∈Li,m>l,i,j∈I

(7)

(8) 同一道工序上兩個相鄰訂單的起始時間關(guān)系。

(Tiu+CTiu+Xijl×Ciju)

?i,j∈I,i≠j,l∈L

(8)

式(8)描述了：任一工序，排位靠后的訂單必須等前加工訂單完成，才能開始啟動加工。

(9) 訂單延期。

?i∈I,li∈L

(9)

3.2 模型目標函數(shù)

調(diào)度模型的目標函數(shù)定義為：在保證能按時完成訂單的前提下，使得訂單完成的提前期最小。

?i∈I

(10)

式中：Li是加工訂單i要經(jīng)過的工序。

4 實例分析

本案例要調(diào)度的訂單共5個，這些訂單涉及的工藝和工藝路線如圖2所示，共9道工序。

圖2 案例訂單涉及的印染生產(chǎn)工藝流程

表1給出了這些訂單要經(jīng)過的工序和每一工序上的加工設(shè)備。

表1 訂單涉及的工序和設(shè)備

表2給出了5個訂單的產(chǎn)品信息，包括訂單名稱、產(chǎn)品名稱、產(chǎn)品顏色、產(chǎn)品生產(chǎn)數(shù)量、客戶要求的交貨期和產(chǎn)品加工的工藝路線。

表2 訂單的相關(guān)數(shù)據(jù)

印染產(chǎn)品的加工從翻縫開始到包裝結(jié)束要經(jīng)過近20道工序，但不是所有的產(chǎn)品都要經(jīng)過所有這些工序。如，表2中的全棉彈力帆布要經(jīng)過9道工序，而全棉斜紋只經(jīng)過6道工序，這是因為不同的產(chǎn)品對工藝有不同的要求，包括坯布質(zhì)地和產(chǎn)品的顏色，如燈芯絨和平布對加工工藝的要求就不同，這也是印染調(diào)度是 Job Shop 問題的原因。

根據(jù)案例的求解結(jié)果，畫出如圖3所示的甘特圖，圖3中的U1表示設(shè)備1，I1表示訂單1，如，訂單1(I1)經(jīng)過9道工序，在每一道工序使用的設(shè)備分別是U1、U2、U3、U4、U5、U6、U7、U8、U9。虛線和實線之間的時間間隔表示二道工序之間的推小車時間與設(shè)備準備時間之和。

圖3 考慮工序間隙和染色機清洗的案例甘特圖

工序7是染色工藝，訂單2在完成絲光工序后進行染色，從圖3看出，在染色時要清洗機器。這是因為，訂單1產(chǎn)品的顏色是黑色的，而訂單2產(chǎn)品的顏色是灰色的，圖3指出，染色機U7是先加工訂單1的，然后再加工訂單2，黑比石頭色要深的多，所以要清洗。

從圖3還可以看出，調(diào)度結(jié)果染色機只清洗了一次。這是因為訂單1、2、3、4和5產(chǎn)品的顏色分別是黑色、石頭色、淡黃、駱黃色和橙色，后面四種顏色差別較小，而從圖3看出，染色機加工的順序是訂單1、2、3、4和5，所以后面染色機就不需要再清洗。

5 結(jié) 語

本文通過對生產(chǎn)過程優(yōu)化調(diào)度模型和印染生產(chǎn)工藝的研究，在現(xiàn)有模型的基礎(chǔ)上，充分考慮了染色生產(chǎn)過程各工序間隙和染色機清洗兩大主要影響因素，制定了相關(guān)調(diào)度規(guī)則。通過案例仿真，獲得調(diào)度結(jié)果并以甘特圖的形式展現(xiàn)，驗證了考慮工序間隙和染色劑清洗調(diào)度模型的有效性和可行性。