馬玲葉 陳金廣

（1.西安工程大學(xué)計(jì)算機(jī)科學(xué)學(xué)院 西安 710048）（2.柯橋區(qū)西紡紡織產(chǎn)業(yè)創(chuàng)新研究院 紹興 312030）

1 引言

輻照加工在食品的滅菌保存［1］，農(nóng)業(yè)突變育種等方面得到較為廣泛的應(yīng)用［2］。輻照加工企業(yè)是特殊的加工類企業(yè)，其輻照源是由放射性元素如γ［3～5］構(gòu)成，放射強(qiáng)度隨時(shí)間而不斷衰減且價(jià)格昂貴。目前已有一大批專業(yè)化輻照加工企業(yè)誕生［6～8］，合理的生產(chǎn)調(diào)度尤為重要。

1986 年Ikura 和Gimple［9］首 次 提 出 批 調(diào) 度 問題，主要針對(duì)尺寸相同的工件，并假設(shè)各個(gè)批的加工時(shí)間是固定的，與批大小無關(guān)；1994年Uzsoy［10］首先提出差異工件批調(diào)度（NBM）問題，證明了NBM問題是NP難問題。吳愁［11］在單機(jī)批調(diào)度問題中考慮了耗能情況，使調(diào)度更加合理。Kashan［12］等利用遺傳算法對(duì)最小化加工時(shí)間和最小化延遲時(shí)間這兩個(gè)目標(biāo)同時(shí)進(jìn)行優(yōu)化，實(shí)現(xiàn)多目標(biāo)優(yōu)化。楊棟［13］考慮了遺傳算法在包含差異工件的并行批處理機(jī)調(diào)度中的應(yīng)用問題。李國(guó)臣等［14］和張震等［15］分別考慮了能耗約束和模具約束并行批調(diào)度問題。輻照企業(yè)的生產(chǎn)調(diào)度屬于差異工件單機(jī)批調(diào)度問題（NSBM），是NP-hard［16］問題。對(duì)于輻照企業(yè)生產(chǎn)調(diào)度問題，張曉靜［17］等設(shè)計(jì)基于工件序列編碼的混合遺傳算法，縮短生產(chǎn)周期。王眾［18］用遺傳算法對(duì)訂單進(jìn)行優(yōu)化排序，縮短訂單間的空閑時(shí)間。

一段時(shí)間內(nèi)輻照企業(yè)加工能力固定不變，若訂單到達(dá)過多，部分訂單不能按期完成，造成經(jīng)濟(jì)損失。目前的輻照企業(yè)生產(chǎn)調(diào)度算法是以最小化最大完成時(shí)間為目標(biāo)，處理該問題時(shí)，會(huì)出現(xiàn)訂單排產(chǎn)不合理，造成企業(yè)經(jīng)濟(jì)損失。本文提出企業(yè)負(fù)載能力［19］思想，根據(jù)企業(yè)的負(fù)載能力將排產(chǎn)方式分為兩種，使該問題得到處理。

2 輻照加工技術(shù)

加工技術(shù)描述如下：假設(shè)某企業(yè)有一個(gè)輻照源，一個(gè)輻照行程內(nèi)（輻照箱圍繞放射源行進(jìn)一圈稱為一個(gè)輻照行程）共有m 個(gè)輻照箱同時(shí)接受輻照。產(chǎn)品到達(dá)時(shí)，由于γ射線穿透能力強(qiáng)，工人直接按原包裝裝入輻照箱，輻照箱中產(chǎn)品的堆積厚度不能超過客戶要求或產(chǎn)品本身要求；完成裝箱后工人利用輻照箱進(jìn)場(chǎng)的時(shí)間間隔將輻照箱放到加工鏈上，加工鏈圍繞著輻照源勻速前進(jìn)，并以一定的方式翻轉(zhuǎn)移位；輻照箱在，產(chǎn)品在完成輻照后，工人利用出場(chǎng)時(shí)間間隔完成卸貨，進(jìn)、出場(chǎng)的時(shí)間間隔相同。

3 問題描述

本文的目標(biāo)是使剩余輻照箱最少，公式如下式：

其中m 為總輻照箱數(shù)，Bi為訂單i 時(shí)所需輻照箱數(shù)。

假設(shè)J1,J2,…,JN是訂單集合S 中的訂單，每個(gè)訂單都有嚴(yán)格的到達(dá)、交付時(shí)間，訂單i到達(dá)與交付之間的時(shí)間段為訂單有效期Ti；訂單批量到達(dá)后，按規(guī)則拆分：1）一個(gè)訂單只包含一種產(chǎn)品，不同產(chǎn)品拆分為多個(gè)訂單；2）產(chǎn)品所需輻照箱數(shù)大于m，拆分訂單。

輻照加工時(shí)需滿足以下幾點(diǎn)約束：

1）不同訂單的產(chǎn)品可以同時(shí)接受輻照，相互之間沒有干擾；

2）一個(gè)已排產(chǎn)訂單對(duì)應(yīng)一個(gè)批P，批中有m個(gè)輻照箱，所有批組成一個(gè)批集合；

3）每個(gè)工件不能拆分只屬于一個(gè)批，批次進(jìn)入輻照?qǐng)鼍筒荒苤袛啵?/p>

4）每個(gè)訂單都需在Ti內(nèi)完成加工；

5）裝箱時(shí)，直到產(chǎn)品全部裝完或輻照箱已滿，再順序裝載下一個(gè)輻照箱。

相關(guān)變量描述如下：

企業(yè)負(fù)載能力U：企業(yè)一段時(shí)間內(nèi)所能處理的訂單量，值為各訂單加工時(shí)間與Ti的比值之和。

批中占用箱數(shù)Bi：值為產(chǎn)品總件數(shù)除以輻照箱可容納的產(chǎn)品件數(shù)。一個(gè)批中包含多個(gè)訂單時(shí)，Bi為各訂單占用箱數(shù)之和。

輻照劑量κi：由客戶要求給出，在排產(chǎn)前就已確定。

輻照圈數(shù)：由κi決定，值為κi除以輻照一圈最低吸收輻照劑量G。

混合優(yōu)先級(jí)proi：計(jì)算方法參考文獻(xiàn)［20］，如下式：

proi=hi+pri+impi+profi+resi

其中hi表示緊迫度，由訂單有效期決定，有效期越短值越大。pri表示訂單優(yōu)先級(jí)，分為緊急、急、正常三種級(jí)別。impi表示客戶重要程度，分為非常重要、重要、普通三種程度。profi表示訂單利潤(rùn)，由產(chǎn)品輻照圈數(shù)和有效期決定，分為高、中、低三個(gè)等級(jí)。resi表示設(shè)備資源利用程度，由Bi決定。

工件加工時(shí)間Ci：由基本加工時(shí)間和輻照箱進(jìn)場(chǎng)時(shí)間決定。基本加工時(shí)間為κi與G之比乘以輻照一圈所需的時(shí)間D；進(jìn)場(chǎng)時(shí)間是Bi的第一個(gè)輻照箱進(jìn)場(chǎng)至最后一個(gè)輻照箱進(jìn)場(chǎng)的時(shí)間，輻照箱之間的時(shí)間間隔為V。計(jì)算公式為

最優(yōu)調(diào)度集Q 為S 中混合優(yōu)先級(jí)高且U未過載的訂單；非最優(yōu)調(diào)度集I為S中的剩余訂單。

4 合理排產(chǎn)訂單、提高輻照箱利用率的排產(chǎn)算法

初始情況為企業(yè)還沒有接到訂單，即S 為空。當(dāng)訂單批量到達(dá)時(shí)，加入S并排產(chǎn)。根據(jù)U是否過載，將排產(chǎn)方式分為兩種分別予以討論。

情況一：企業(yè)負(fù)載能力未過載（U≤1）

當(dāng)U≤1 即加工S 中的訂單在企業(yè)加工能力范圍之內(nèi)時(shí)，按照Ti排序訂單。由于排產(chǎn)后每個(gè)訂單與確定批對(duì)應(yīng)，批的輻照圈數(shù)以及Bi均可確定，排產(chǎn)前先判斷批集合中有無合適的批，若有則排產(chǎn)到合適批中，否則排產(chǎn)到新批中。

情況二：企業(yè)負(fù)載能力過載（U＞1）

當(dāng)U＞1 即加工S 中的訂單超出企業(yè)加工能力范圍時(shí)，先確定S 中各訂單的proi，根據(jù)proi降序排序訂單，挑選Q 并排產(chǎn)，排產(chǎn)后每個(gè)訂單與確定批對(duì)應(yīng)。然后在I中選擇合適的訂單排產(chǎn)到對(duì)應(yīng)批中。

對(duì)于企業(yè)加工能力過載的情況，算法的主要思想是先排產(chǎn)proi高的訂單，再依據(jù)批集合中各批的輻照圈數(shù)以及批中空閑輻照箱數(shù)，在I 中挑選出合適的訂單進(jìn)行排產(chǎn)。如此可優(yōu)先排產(chǎn)價(jià)值大的訂單，使其按期完成，并能提高輻照箱利用率，盡可能多地排產(chǎn)未排產(chǎn)訂單。

合理排產(chǎn)訂單、提高輻照箱利用率的排產(chǎn)算法實(shí)現(xiàn)步驟如下。

輸入：訂單集合S，輻照空箱數(shù)m。

輸出：訂單排產(chǎn)順序以及所對(duì)應(yīng)的批。

步驟1：對(duì)S 中的所有訂單是否超出企業(yè)加工能力進(jìn)行判斷，若U≤1，轉(zhuǎn)至步驟2；若U＞1，轉(zhuǎn)至步驟3。

步驟2：對(duì)S中的訂單按Ti升序排序并排產(chǎn)，排產(chǎn)訂單時(shí)先判斷能否在批集合中找到與該訂單所需輻照圈數(shù)相同的批，若找到則判斷是否拆分訂單，在將符合條件的訂單安排到對(duì)應(yīng)批中，并更新批的剩余輻照箱數(shù)；若沒找到直接排產(chǎn)該訂單，該訂單對(duì)應(yīng)一個(gè)新批，記錄新批的輻照圈數(shù)和剩余輻照箱數(shù)，并加入批集合中。

步驟3：計(jì)算各訂單的proi并降序排序訂單，挑選訂單組成Q。排產(chǎn)Q，記錄排產(chǎn)后各訂單所對(duì)應(yīng)批的剩余輻照箱數(shù)和輻照圈數(shù)，按輻照圈數(shù)升序排序各批。再順序挑選I 中的訂單，若找到符合條件的批則判斷是否拆分訂單，若沒找到則處理下一個(gè)訂單。

判斷是否拆分訂單依據(jù)：訂單所需輻照箱數(shù)小于或等于批中剩余輻照箱數(shù)，不拆分訂單；否則將訂單按照批中剩余輻照箱所能容納的產(chǎn)品大小拆分并排產(chǎn)到應(yīng)批中，另一個(gè)訂單保存到S 中；更新相應(yīng)的值。算法流程如圖1 所示，挑選Q 流程如圖2所示。

圖1 算法流程圖

圖2 最優(yōu)調(diào)度集流程圖

5 算例與結(jié)果分析

假設(shè)某輻照加工企業(yè)只有一個(gè)輻照源，輻照箱m=6，輻照一圈所需時(shí)長(zhǎng)D=30 min，空箱輻照一圈最低吸收劑量G=0.2 kGy，相鄰兩輻照箱的發(fā)車間隔V=5 min。

5.1 算例1

該算例考慮U≤1 情況下的調(diào)度，假設(shè)一段時(shí)間內(nèi)企業(yè)訂單集合中有5 個(gè)訂單，其參數(shù)如表1 所示。

表1 低負(fù)載情況下的產(chǎn)品加工參數(shù)

該輻照公司總負(fù)載為U= 80/600 + 120/600 +70/600+80/600+70/600=420/600 ＜1，企業(yè)負(fù)載能力未過載，按Ti對(duì)訂單進(jìn)行升序排序，排序后的訂單順序?yàn)?、3、2、4、5，此時(shí)批集合為空。排產(chǎn)訂單1，訂單1 對(duì)應(yīng)批1，占用兩個(gè)輻照箱，剩余4 個(gè)輻照箱，將批1 加入批集合中；排產(chǎn)訂單3，由于批1 與其輻照圈數(shù)一致，且訂單3 所需輻照箱數(shù)小于批1中剩余輻照箱數(shù)，故將訂單3 排產(chǎn)到批1，此時(shí)批1中占用3 個(gè)輻照箱，剩余3 個(gè)輻照箱；排產(chǎn)訂單2，由于批集合中沒有符合條件的批，因此訂單2 對(duì)應(yīng)批2，批2中占用6個(gè)輻照箱，剩余0個(gè)輻照箱，將批2加入批集合中；排產(chǎn)訂單4時(shí)，由于批集合中沒有符合條件的批，因此訂單4 對(duì)應(yīng)批3，批3 中占用4個(gè)輻照箱，剩余兩個(gè)輻照箱，將批3 加入批集合中；排產(chǎn)訂單5，批3 與其輻照圈數(shù)一致，且訂單5 所需輻照箱數(shù)等于批3 中剩余輻照箱數(shù)，故將訂單5 排產(chǎn)到批3，此時(shí)批3 中占用6 個(gè)輻照箱，剩余0 個(gè)輻照箱，此時(shí)5 個(gè)訂單均可按期完成。各批的輻照箱使用情況如圖3（a）所示。與每個(gè)訂單對(duì)應(yīng)一個(gè)批的排產(chǎn)方式相比，輻照箱利用率得到提升，各批的輻照箱使用情況如圖3（b）所示。

圖3 各批輻照箱使用情況對(duì)比

5.2 算例2

該算例考慮U＞1 情況下的調(diào)度，假設(shè)企業(yè)一段時(shí)間內(nèi)訂單集合中有5 個(gè)訂單，其參數(shù)如表2 所示。

表2 過載情況下的產(chǎn)品加工參數(shù)

該輻照公司總負(fù)載為U = 120/360 + 135/360+140/360+150/360+70/360 ＞1，企業(yè)負(fù)載能力過載。計(jì)算各訂單proi，proi影響因素如表3所示。

表3 訂單混合優(yōu)先級(jí)影響因素表

按proi降序排序各訂單，順序?yàn)?、5、2、4、3，挑選Q。由于加工訂單1、訂單5、訂單2時(shí)，U=120/360 + 70/360 + 135/360 ＜1，企業(yè)負(fù)載能力未過載，故可作為Q。排產(chǎn)Q，訂單1 對(duì)應(yīng)批1，占用兩個(gè)輻照箱，剩余4 個(gè)輻照箱；訂單5 對(duì)應(yīng)批2，占用兩個(gè)輻照箱，剩余4個(gè)輻照箱；訂單2對(duì)應(yīng)批3，占用3個(gè)輻照箱，剩余3 個(gè)輻照箱，此時(shí)批1、批2、批3 的輻照箱利用率分別為33%、33%、50%。排產(chǎn)I，在批集合中搜索與訂單4 輻照圈數(shù)一樣的批，判斷該批中剩余輻照箱數(shù)是否滿足訂單4 所需輻照箱數(shù)，經(jīng)分析計(jì)算將訂單4 安排到批1 中，同理，將訂單3 安排到批2 中。此時(shí)批1 中的占用輻照箱數(shù)為6，剩余0個(gè)，利用率為100%，提升了67%；批2 中的占用輻照箱數(shù)為4，剩余2 個(gè)，利用率為66%，提升了33%，此時(shí)五個(gè)訂單均能按期完成。批中輻照箱的使用情況如圖4中（a）所示。

若以最小化最大完成時(shí)間為目標(biāo)，按照所選訂單在企業(yè)的加工能力范圍之內(nèi)和最大完成時(shí)間最小這兩條規(guī)定，選擇訂單1 和訂單4 排產(chǎn)加工。排產(chǎn)完成后，訂單1對(duì)應(yīng)批1，占用輻照箱數(shù)為2，剩余輻照箱數(shù)為4，利用率為33%；訂單4對(duì)應(yīng)批2，占用輻照箱數(shù)為4，剩余輻照箱數(shù)為2，利用率為66%，此時(shí)兩個(gè)訂單可按期完成。批中輻照箱的使用情況如圖4中（b）所示。

圖4 不同優(yōu)化目標(biāo)下批中輻照箱使用對(duì)比圖

經(jīng)對(duì)比本文算法不僅可以合理安排訂單排產(chǎn)順序，提高企業(yè)接單率，還能提高輻照箱利用率，提高企業(yè)利潤(rùn)。

6 結(jié)語

本文提出一種合理安排訂單，提高輻照箱利用率的生產(chǎn)調(diào)度算法。該算法根據(jù)企業(yè)加工能力是否過載分為兩種情況：企業(yè)加工能力過載和企業(yè)加工能力未過載。企業(yè)加工能力未過載時(shí)，按照訂單有效期對(duì)訂單集合排序，排產(chǎn)排序后的訂單集合時(shí)，先判斷批集合中有無合適的批，若有則安排到對(duì)應(yīng)批中加工，若沒有則安排到新批中；企業(yè)加工能力過載時(shí)，按照混合優(yōu)先級(jí)對(duì)訂單排序，挑選混合優(yōu)先級(jí)高且符合企業(yè)負(fù)載能力未過載的訂單作為最優(yōu)調(diào)度集，優(yōu)先排產(chǎn)最優(yōu)調(diào)度集中訂單，排產(chǎn)訂單與批對(duì)應(yīng)，記錄各批的輻照圈數(shù)與剩余輻照箱數(shù)，挑選合適的未排產(chǎn)訂單進(jìn)行排產(chǎn)。算例結(jié)果表明所提算法不僅能夠合理安排訂單排產(chǎn)順序，使混合優(yōu)先級(jí)高的訂單優(yōu)先排產(chǎn)，排產(chǎn)盡可能多的訂單，還能提高輻照箱利用率，增大企業(yè)利潤(rùn)。下一步將研究如何提高每個(gè)輻照箱空間利用率，使企業(yè)資源充分利用。