楊 偉，曾雋芳，2

（1.中國科學(xué)院自動化研究所，北京 100190；2.北京三博中自有限公司，北京 100190）

國內(nèi)鞋底企業(yè)生產(chǎn)計(jì)劃的制定和排產(chǎn)主要靠人工來完成，大部分企業(yè)將能在規(guī)定的時(shí)間內(nèi)完成相應(yīng)的生產(chǎn)任務(wù)視為合格的生產(chǎn)計(jì)劃，生產(chǎn)設(shè)備使用率、生產(chǎn)率低，生產(chǎn)成本居高不下，既沒有最大程度地凸顯生產(chǎn)設(shè)備的先進(jìn)性，同時(shí)也難以在激烈的市場競爭中取勝。少數(shù)企業(yè)則采用了ERP（enterprise resource planning）系統(tǒng)[1]。ERP系統(tǒng)支持和加快了訂單的整個(gè)處理過程，使業(yè)務(wù)和生產(chǎn)過程管理實(shí)現(xiàn)數(shù)據(jù)共享和集成，實(shí)現(xiàn)事務(wù)處理自動化和對財(cái)務(wù)、生產(chǎn)和分銷資源進(jìn)行跟蹤，改進(jìn)企業(yè)的靈活性和提高應(yīng)變能力。但是ERP系統(tǒng)有其局限性，不容易適應(yīng)訂單需求調(diào)整、資源容量、原材料可用性等變化，使得生產(chǎn)車間出現(xiàn)了許多問題，為了克服這些缺點(diǎn)，使用先進(jìn)生產(chǎn)計(jì)劃與調(diào)度系統(tǒng)[2]就非常必要。它是對生產(chǎn)過程進(jìn)行規(guī)劃與控制，合理安排企業(yè)的生產(chǎn)執(zhí)行路線、任務(wù)執(zhí)行的起止時(shí)間和對各種資源的調(diào)配等，先進(jìn)的排產(chǎn)調(diào)度算法對生產(chǎn)過程運(yùn)行的結(jié)果和經(jīng)濟(jì)效益起著決定性的作用。

對于鞋底生產(chǎn)企業(yè)，這是面向訂單的多工序的生產(chǎn)方式，就是按照客戶訂單來安排生產(chǎn)，確定訂單執(zhí)行順序后，再分解訂單到各個(gè)車間進(jìn)行生產(chǎn)，該生產(chǎn)方式對企業(yè)生產(chǎn)排產(chǎn)能力有較高要求，文獻(xiàn)[3]對此類問題進(jìn)行了分析。由于訂單生產(chǎn)排序計(jì)劃問題（簡稱排序）具有NP-HARD計(jì)算復(fù)雜性[4]，常規(guī)方法需耗費(fèi)很大的計(jì)算量，近年來，一些新的啟發(fā)式算法如遺傳算法[5]、神經(jīng)網(wǎng)絡(luò)[6]、禁忌搜索[7]、粒子群算法[8]以及蟻群算法[9]也常用來解決這類調(diào)度問題。蟻群算法是由Dorigo[10]在1992年提出的一種模擬進(jìn)化算法，在解決組合優(yōu)化問題上有非常好的效果。由于鞋底生產(chǎn)過程也是一個(gè)多工序的車間調(diào)度問題，此類問題可以看做一個(gè)圖模型的組合優(yōu)化問題，圖上每個(gè)節(jié)點(diǎn)代表一道生產(chǎn)工序，這使得使用蟻群算法非常適合解決此類問題。

本文對鞋底生產(chǎn)工藝進(jìn)行分析，建立鞋底的生產(chǎn)計(jì)劃與調(diào)度框架，提出基于多工序訂單排序模型，應(yīng)用蟻群算法進(jìn)行求解，獲得了優(yōu)化后的排產(chǎn)計(jì)劃，指導(dǎo)企業(yè)進(jìn)行生產(chǎn)。

1 鞋底生產(chǎn)工藝

鞋底生產(chǎn)主要分為3個(gè)流程。大底生產(chǎn)和中底生產(chǎn)分別在大底車間以及中底車間中生產(chǎn)，這兩者可以并行生產(chǎn)而不受工藝順序影響，而貼合工藝就是將前兩者的半成品進(jìn)行加工貼合形成鞋底成品的過程，其工藝流程如圖1所示，下面對工藝流程進(jìn)行詳細(xì)分析。

圖1 鞋底生產(chǎn)工藝流程Fig.1 Flow chart of sole production

鞋子主要是由幫面、內(nèi)襯（里子）、前后燙底、前后包頭、中底（也叫寸底）、大底（鞋底）等部分組成，本文主要就鞋底生產(chǎn)中的中底、大底及其貼合工藝進(jìn)行分析。

生產(chǎn)訂單下達(dá)后，根據(jù)生產(chǎn)排產(chǎn)的計(jì)劃，分別生成大底車間計(jì)劃、中低車間計(jì)劃和貼合車間計(jì)劃，并分配相應(yīng)的物料進(jìn)行生產(chǎn)。大底車間的工藝流程包括前期對原材料進(jìn)行預(yù)處理、截?cái)嗟炔僮鳎缓笤龠M(jìn)行硫化、修邊，生產(chǎn)完成后要清點(diǎn)統(tǒng)計(jì)數(shù)量再運(yùn)往中倉等待下一步工藝處理。

中底車間主要針對EVA（醋酸乙烯共聚物）鞋中底，也稱為一次發(fā)泡中底，是利用一次射出成型機(jī)來進(jìn)行生產(chǎn)，該射出機(jī)將EVA樹脂顆粒直接射入機(jī)臺模具里面，真空加硫大約400 s后模具打開，模內(nèi)鞋底發(fā)泡成型，再經(jīng)過熱、冷定型定。經(jīng)過修邊、分碼、清點(diǎn)操作后運(yùn)往中倉等待下一步工藝。該中底生產(chǎn)方法最大特點(diǎn)是產(chǎn)量高、一次成型，這也是目前最先進(jìn)的EVA底生產(chǎn)技術(shù)。

貼合車間生產(chǎn)主要將中倉里的大底和中底進(jìn)行貼合操作。經(jīng)過打磨、水洗最后按訂單碼放并貼上標(biāo)簽運(yùn)往成品庫，完成該訂單生產(chǎn)。

2 鞋底優(yōu)化排產(chǎn)三級框架

優(yōu)化排產(chǎn)是在考慮能力和設(shè)備的前提下，安排各生產(chǎn)任務(wù)的生產(chǎn)順序，優(yōu)化生產(chǎn)順序，優(yōu)化選擇生產(chǎn)設(shè)備，以減少等待時(shí)間，平衡各機(jī)器和工人的生產(chǎn)負(fù)荷，從而優(yōu)化產(chǎn)能，提高生產(chǎn)效率，縮短生產(chǎn)周期。根據(jù)企業(yè)生產(chǎn)實(shí)際情況，企業(yè)先得到銷售合同訂單，并將其訂單信息錄入ERP系統(tǒng)中，包括交貨日期、所需模具、預(yù)期收益等，然后合理安排訂單生產(chǎn)順序使得企業(yè)收益最大。在企業(yè)MES（manufacturing execution system）系統(tǒng)中保存著車間生產(chǎn)約束如設(shè)備數(shù)量、模具數(shù)量、人工日歷等約束信息，在將訂單分解下達(dá)到車間后根據(jù)生產(chǎn)約束制定合理的車間生產(chǎn)計(jì)劃，并通過車間看板、條碼等信息進(jìn)行反饋從而修正排產(chǎn)計(jì)劃。

根據(jù)流程，本文將鞋底的排產(chǎn)分為3個(gè)等級，即訂單計(jì)劃系統(tǒng)、訂單排產(chǎn)系統(tǒng)以及車間生產(chǎn)調(diào)度系統(tǒng)，圖2所示為設(shè)計(jì)的鞋底三級排產(chǎn)框架。在排產(chǎn)中，還需要考慮緊急訂單插入、質(zhì)量問題以及設(shè)備故障等突發(fā)事件的處理，要根據(jù)實(shí)際生產(chǎn)狀況調(diào)整生產(chǎn)調(diào)度計(jì)劃。

圖2 鞋底排產(chǎn)的三級框架Fig.2 Planning and scheduling structure design of sole production

2.1 訂單計(jì)劃系統(tǒng)

鞋底的訂單主要是根據(jù)企業(yè)的銷售合同、銷售預(yù)測，為了減少庫存以及排產(chǎn)難度，平衡所有生產(chǎn)能力，選擇生產(chǎn)計(jì)劃的時(shí)間跨度為一個(gè)季度，即需要給出企業(yè)一個(gè)季度的生產(chǎn)排產(chǎn)計(jì)劃，指導(dǎo)企業(yè)進(jìn)行生產(chǎn)，并在有新訂單需要生產(chǎn)時(shí)，重新進(jìn)行排產(chǎn)得到新的排產(chǎn)計(jì)劃，當(dāng)把訂單計(jì)劃下達(dá)給訂單計(jì)劃系統(tǒng)后，訂單計(jì)劃系統(tǒng)還需根據(jù)訂單量采購需要的原料以及安排生產(chǎn)所需要的模具。

2.2 訂單排產(chǎn)系統(tǒng)

鞋底排產(chǎn)主要是基于訂單進(jìn)行生產(chǎn)，是由訂單驅(qū)動的生產(chǎn)方式。如何合理安排訂單的生產(chǎn)順序是訂單排產(chǎn)的關(guān)鍵問題，本節(jié)將對訂單排產(chǎn)問題進(jìn)行分析。

在訂單排產(chǎn)過程中，還需要考慮到相同訂單以及緊急訂單插入時(shí)的處理方法，相同訂單是指雖然訂單來自不同的公司，但是他們需要的鞋底都使用相同模具進(jìn)行生產(chǎn)，那么當(dāng)兩者的交貨期相差不遠(yuǎn)時(shí)，可以對這2個(gè)訂單進(jìn)行合并當(dāng)作1個(gè)訂單來進(jìn)行生產(chǎn)。緊急插單是指當(dāng)一個(gè)交貨時(shí)間短并且訂單優(yōu)先級比較高時(shí)我們需要優(yōu)先安排該訂單生產(chǎn)。

由于鞋底生產(chǎn)需要經(jīng)過大底、中底、貼合3個(gè)工序，所以訂單需要在這3道工序中處理完成后才能交給客戶，每個(gè)工序的設(shè)備在同一時(shí)刻只能生產(chǎn)同一訂單，每個(gè)訂單包含交貨期、訂單量、收益以及生產(chǎn)量，每道工序的處理時(shí)間可由車間調(diào)度系統(tǒng)反饋得到。當(dāng)訂單的完工時(shí)間晚于交貨期時(shí)，企業(yè)需要承擔(dān)延遲處罰，不同訂單根據(jù)重要程度有不同的延遲懲罰系數(shù)。

2.3 車間生產(chǎn)調(diào)度系統(tǒng)

地方車間生產(chǎn)調(diào)度系統(tǒng)根據(jù)訂單信息將訂單分解得到需要生產(chǎn)的中底以及大底數(shù)量。由車間模具數(shù)量、設(shè)備數(shù)量等約束信息可以求得各個(gè)工序生產(chǎn)所需要的時(shí)間，結(jié)合訂單調(diào)度系統(tǒng)，就可以得到各個(gè)生產(chǎn)車間的排產(chǎn)甘特圖，指導(dǎo)生產(chǎn)。由于在生產(chǎn)過程中難免會出現(xiàn)一定的廢品率，所以需要將信息反饋給訂單計(jì)劃系統(tǒng)，讓其修正生產(chǎn)計(jì)劃，重新排產(chǎn)。

從鞋底的生產(chǎn)工藝中可以看出，在大底車間和中底車間分別生產(chǎn)完成大底、中底半成品后，將產(chǎn)品運(yùn)往中倉庫進(jìn)行存儲，然后再運(yùn)往貼合車間進(jìn)行貼合工藝得到成品鞋底，最后再運(yùn)往成品庫中進(jìn)行存儲。中倉將大底、中底的生產(chǎn)和貼合工藝進(jìn)行分開，減少了和貼合工藝之間的耦合。并且在這3道工序中，大底、中底生產(chǎn)可以并行執(zhí)行，2個(gè)工序之間沒有前后順序約束，而貼合工序需要在大底中底生產(chǎn)完成后才能進(jìn)行。車間調(diào)度系統(tǒng)的難點(diǎn)主要在于合理安排大底、中底以及貼合車間的生產(chǎn)。

由訂單調(diào)度系統(tǒng)得到所要生產(chǎn)的訂單順序后，將訂單生產(chǎn)計(jì)劃具體細(xì)化到每一道工序，得到各個(gè)工序的起始時(shí)間和結(jié)束時(shí)間。在車間調(diào)度系統(tǒng)中，主要的約束有如下3個(gè)方面：

模具生產(chǎn)約束由于中底生產(chǎn)采用一次射出成型機(jī)，射出機(jī)配上不同模具才能生產(chǎn)各種中底，模具數(shù)影響了生產(chǎn)產(chǎn)能。所以該過程中使用的模型信息量非常重要，模具通過其型體編號和號碼來進(jìn)行分類，不同的訂單所需要的模具并不相同，在該企業(yè)中，通過記錄模具庫存與模具計(jì)劃數(shù)就可以得到每天可用的模具數(shù)。

設(shè)備使用約束在車間中一共有n條生產(chǎn)線，每條生產(chǎn)線2臺射出機(jī)設(shè)備，每個(gè)設(shè)備都需要配備1個(gè)模具進(jìn)行生產(chǎn)，設(shè)備數(shù)與模具共同決定了當(dāng)天鞋底的產(chǎn)能。

工廠日歷約束車間生產(chǎn)需要考慮工廠人員的可使用情況，該鞋底生產(chǎn)車間中，員工休息日將不進(jìn)行生產(chǎn)，生產(chǎn)計(jì)劃將按順序延后生產(chǎn)。

3 基于蟻群算法的模型求解

3.1 訂單計(jì)劃系統(tǒng)

根據(jù)第3節(jié)中對鞋底生產(chǎn)排產(chǎn)框架的描述，以最大化企業(yè)收益為目標(biāo)函數(shù)，則鞋底生產(chǎn)優(yōu)化排產(chǎn)的數(shù)學(xué)模型為

目標(biāo)函數(shù)：

約束條件：

式中：f為企業(yè)收益函數(shù)；n為工廠某時(shí)刻待排產(chǎn)訂單數(shù)；m為訂單需要處理的工序數(shù)，m=3；Ri為訂單i的期望收益；wi為訂單i的延遲懲罰系數(shù)；di為訂單i的交貨期；Cij為訂單i在完成工序j時(shí)的時(shí)間；Tij為訂單i在工序j上的處理時(shí)間；s（k）為在對n個(gè)訂單的一個(gè)可行的訂單處理順序中，第k個(gè)被處理的訂單。

式（1）為企業(yè)的收益函數(shù)，每個(gè)訂單的實(shí)際收益為期望收益減去延遲懲罰，企業(yè)的總收益為各個(gè)訂單實(shí)際收益之和；式（2）表示在處理訂單s（k）時(shí)，之前訂單的所有工序必須全部完成；式（3）表示在處理某個(gè)訂單時(shí)，最后一道工序必須在前2道工序都處理完成后才能處理，而且前2道工序之間沒有先后約束關(guān)系，可以同時(shí)生產(chǎn)；式（4）為訂單處理初始化約束。

3.2 蟻群算法求解策略

蟻群算法ACA（ant colony algorithm）是一種模擬進(jìn)化算法，啟發(fā)于螞蟻覓食的最短路徑原理：在螞蟻覓食過程中會釋放一種特殊的分泌物——信息素，并因此影響螞蟻的行為，當(dāng)一條路徑上經(jīng)過的螞蟻數(shù)量越來越多，留下的信息素也越多，使得后來的螞蟻選擇此條路徑的概率越來越大，從而進(jìn)一步增加了該路徑上的信息素濃度，利用這種正反饋機(jī)制，螞蟻?zhàn)罱K能夠在蟻巢和食物源頭之間找到一條最短路徑。蟻群算法的求解流程如圖3所示。

（1）參數(shù)初始化。設(shè)置算法迭代次數(shù)N以及螞蟻數(shù)N_ant，初始化信息τ（i，j）=C，C為較小的常數(shù)。

（2）螞蟻根據(jù)狀態(tài)轉(zhuǎn)移概率選擇下一個(gè)節(jié)點(diǎn)，轉(zhuǎn)移概率為

圖3 蟻群算法流程Fig.3 Flow chart of ACA

（3）更新信息素，經(jīng)過一次迭代之后，信息素為

式中：ρ為信息素的揮發(fā)系數(shù)，0≤ρ≤1；H為經(jīng)過（i，j）的螞蟻集合；L（k）為螞蟻k因?yàn)檠舆t交貨造成的懲罰；Δτ（i，j）為本次迭代中信息素增量。

（4）循環(huán)（2）、（3），直到算法收斂或達(dá)到最優(yōu)解，該最優(yōu)解對應(yīng)螞蟻的禁忌表中訂單的順序即是得出的最優(yōu)的排產(chǎn)方案。

3.3 仿真驗(yàn)證

為了驗(yàn)證上述模型的正確性，以一項(xiàng)實(shí)際工程項(xiàng)目某鞋底制造企業(yè)為例?？紤]該企業(yè)在一個(gè)生產(chǎn)加工調(diào)度周期內(nèi)排產(chǎn)池中有10個(gè)訂單，表1為訂單中3個(gè)工藝的加工時(shí)間、收益、延遲懲罰以及交貨期的表格，pa為大底工序所需時(shí)間，pb表示中底工序所需時(shí)間，pc表示貼合工序所需時(shí)間。

表1 訂單排產(chǎn)信息表Tab.1 Order attribute information

對該優(yōu)化問題利用蟻群算法進(jìn)行求解，在Matlab中進(jìn)行仿真，設(shè)置參數(shù)N_ant=20，N=500，α=1，β=2，ρ=0.1，Q=50，C=1。運(yùn)行程序，得到的最優(yōu)解為74，此時(shí)訂單排產(chǎn)結(jié)果如圖4所示，圖中序號表示執(zhí)行的訂單編號，則利用此甘特圖可以對鞋底生產(chǎn)過程進(jìn)行有效指導(dǎo)。

圖4 鞋底排產(chǎn)甘特圖Fig.4 Gantt diagram of sole scheduling

4 結(jié)語

本文根據(jù)鞋底生產(chǎn)工藝，建立了鞋底生產(chǎn)計(jì)劃與調(diào)度的框架，對鞋底生產(chǎn)中大底、中底以及貼合等工藝過程進(jìn)行了分析，提出了基于訂單排產(chǎn)以及車間排產(chǎn)的分級排產(chǎn)模式，以最大化企業(yè)利潤為目標(biāo)建立模型并利用蟻群算法求解，得到排產(chǎn)計(jì)劃的甘特圖。本方法有效地利用了企業(yè)現(xiàn)有的資源，合理地安排訂單生產(chǎn)，直觀指導(dǎo)車間生產(chǎn)，部分研究成果已在某鞋底生產(chǎn)企業(yè)中得到應(yīng)用驗(yàn)證。本模型為鞋底生產(chǎn)的復(fù)雜生產(chǎn)提供了排產(chǎn)支持，為企業(yè)創(chuàng)造更好的效益。

[1] Umble E J，Haft R R，Umble M M.Enterprise resource planning：Implementation procedures and critical success factors[J]. European Journal of Operational Research，2003，146（2）：241-257.

[2] Maravelias C T，Sung C.Integration of production planning and scheduling：Overview，challenges and opportunities[J].Computers &Chemical Engineering，2009，33（12）：1919-1930.

[3] 劉永，李言，李淑娟，等.面向訂單的生產(chǎn)計(jì)劃與調(diào)度的綜合優(yōu)化[J].工業(yè)工程與管理，2009，14（3）：84-89.

[4]De P，Ghosh J B，Wells C E.Job selection and sequencing on a single machine in a random environment[J].European Journal of Operational Research，1993，70（3）：425-431.

[5] Cheng C，Yang Z，Xing L，et al.An improved genetic algorithm with local search for order acceptance and scheduling problems [C]//Computational Intelligence in Production and Logistics Systems，IEEE，2013：115-122.

[6] Fang Xi，Chen Jing.A neural network model for resource scheduling optimization[C]//The IEEE International Conference on Information Management and Engineering.IEEE，2010：430-432.

[7] Cesaret B，O?uz C，Salman F S.A tabu search algorithm for order acceptance and scheduling[J].Computers&Operations Research，2012，39（6）：1197-1205.

[8] Liao Chingjong，Tseng Chaojong，Luarn P.A discrete version of particle swarm optimization for flowshop scheduling problems[J]. Computers&Operations Research，2007，34（10）：3099-3111.

[9] 王雪峰，陳志祥.用混合蟻群算法求解多工序訂單生產(chǎn)計(jì)劃[J].價(jià)值工程，2009（6）：5-8.

[10]Dorigo M，Caro G D.Ant colony optimization：a new meta-heuristic[C]//Evolutionary Computation，1999.CEC 99.Proceedings of the 1999 Congress on.IEEE，2002：1477 Vol.2.