一種提高輻照箱利用率的生產調度算法*

馬玲葉 陳金廣

（1.西安工程大學計算機科學學院 西安 710048）（2.柯橋區西紡紡織產業創新研究院 紹興 312030）

1 引言

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

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

一段時間內輻照企業加工能力固定不變，若訂單到達過多，部分訂單不能按期完成，造成經濟損失。目前的輻照企業生產調度算法是以最小化最大完成時間為目標，處理該問題時，會出現訂單排產不合理，造成企業經濟損失。本文提出企業負載能力［19］思想，根據企業的負載能力將排產方式分為兩種，使該問題得到處理。

2 輻照加工技術

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

3 問題描述

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

其中m 為總輻照箱數，Bi為訂單i 時所需輻照箱數。

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

輻照加工時需滿足以下幾點約束：

1）不同訂單的產品可以同時接受輻照，相互之間沒有干擾；

2）一個已排產訂單對應一個批P，批中有m個輻照箱，所有批組成一個批集合；

3）每個工件不能拆分只屬于一個批，批次進入輻照場就不能中斷；

4）每個訂單都需在Ti內完成加工；

5）裝箱時，直到產品全部裝完或輻照箱已滿，再順序裝載下一個輻照箱。

相關變量描述如下：

企業負載能力U：企業一段時間內所能處理的訂單量，值為各訂單加工時間與Ti的比值之和。

批中占用箱數Bi：值為產品總件數除以輻照箱可容納的產品件數。一個批中包含多個訂單時，Bi為各訂單占用箱數之和。

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

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

混合優先級proi：計算方法參考文獻［20］，如下式：

proi=hi+pri+impi+profi+resi

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

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

最優調度集Q 為S 中混合優先級高且U未過載的訂單；非最優調度集I為S中的剩余訂單。

4 合理排產訂單、提高輻照箱利用率的排產算法

初始情況為企業還沒有接到訂單，即S 為空。當訂單批量到達時，加入S并排產。根據U是否過載，將排產方式分為兩種分別予以討論。

情況一：企業負載能力未過載（U≤1）

當U≤1 即加工S 中的訂單在企業加工能力范圍之內時，按照Ti排序訂單。由于排產后每個訂單與確定批對應，批的輻照圈數以及Bi均可確定，排產前先判斷批集合中有無合適的批，若有則排產到合適批中，否則排產到新批中。

情況二：企業負載能力過載（U＞1）

當U＞1 即加工S 中的訂單超出企業加工能力范圍時，先確定S 中各訂單的proi，根據proi降序排序訂單，挑選Q 并排產，排產后每個訂單與確定批對應。然后在I中選擇合適的訂單排產到對應批中。

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

合理排產訂單、提高輻照箱利用率的排產算法實現步驟如下。

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

輸出：訂單排產順序以及所對應的批。

步驟1：對S 中的所有訂單是否超出企業加工能力進行判斷，若U≤1，轉至步驟2；若U＞1，轉至步驟3。

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

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

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

圖1 算法流程圖

圖2 最優調度集流程圖

5 算例與結果分析

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

5.1 算例1

該算例考慮U≤1 情況下的調度，假設一段時間內企業訂單集合中有5 個訂單，其參數如表1 所示。

表1 低負載情況下的產品加工參數

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

圖3 各批輻照箱使用情況對比

5.2 算例2

該算例考慮U＞1 情況下的調度，假設企業一段時間內訂單集合中有5 個訂單，其參數如表2 所示。

表2 過載情況下的產品加工參數

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

表3 訂單混合優先級影響因素表

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

若以最小化最大完成時間為目標，按照所選訂單在企業的加工能力范圍之內和最大完成時間最小這兩條規定，選擇訂單1 和訂單4 排產加工。排產完成后，訂單1對應批1，占用輻照箱數為2，剩余輻照箱數為4，利用率為33%；訂單4對應批2，占用輻照箱數為4，剩余輻照箱數為2，利用率為66%，此時兩個訂單可按期完成。批中輻照箱的使用情況如圖4中（b）所示。

圖4 不同優化目標下批中輻照箱使用對比圖

經對比本文算法不僅可以合理安排訂單排產順序，提高企業接單率，還能提高輻照箱利用率，提高企業利潤。

6 結語

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