需求量不確定條件下單臺機生產調度問題

呂 恒 肖 漢

摘要:研究了需求量不確定條件下帶有交貨期窗約束單臺機的生產調度問題,模糊需求用三角模糊數來表示,模糊交貨期用半梯形模糊數來表示,建立了以滿意度最大作為優化目標的模糊調度數學模型,并給出了基于遺傳算法的優化方法,通過仿真試驗驗證了方法的有效性。

關鍵詞:不確定性;單機調度;遺傳算法

中圖分類號:F273文獻標識碼:A

Abstract: In this paper, scheduling for single machine with uncertainty demand is considered, which includes due-data windows for orders. A triangular fuzzy number is used to represent the uncertainty demand, and a half-trapezoid one to represent fuzzy due-data. We use the maximum agreement index as optimized object, and genetic algorithm is adopted to find the optimal sequencing. Simulation results illustrated the efficiency of the proposed model and algorithm.

Key words: uncertainties; single machine scheduling; genetic algorithm

0引言

生產調度問題的研究源于20世紀50年代,由于該問題的實用性和重要性,隨之在運籌學和工業工程等學科中形成一個獨立的分支方向。直到目前,專家學者仍然在研究不同情況下生產調度問題。由于現在的生活節奏加快,產品的周期越來越短,隨之對產品的需求預測也成為現在生產的一個重要問題。企業在不能準確預測市場需求情況下如何更好地安排生產、更快地占領市場已經成為挑戰。因此,在市場需求不確定的情況下更好地安排生產對企業的發展有重要的意義。

許多學者對需求量不確定條件下的生產問題進行了研究,蘇生[1]等人研究了不確定需求和能力約束下的多目標多工廠生產計劃問題;孫光圻[2]等人研究了相關、不確定需求下生產計劃的優化問題;李初福[3]等研究了需求不確定下煉油企業的生產計劃優化問題,這些研究主要集中在宏觀的生產計劃方面的不確定性,對需求量不確定條件下的生產調度研究不多。顧幸生[4]在研究不確定性條件下的生產調度問題時提出不確定性包括外部環境的不確定性,如產品的需求量、產品的價格、能源等,隨后又研究了需求量不確定條件下連續過程生產調度問題。目前需求量的不確定性主要有兩種表達形式:概率模型和模糊數。本文主要研究單臺機生產調度問題,考慮市場對產品需求量的不確定性,采用三角模糊數來描述不確定性因素[5]。

1模糊函數

模糊集合是用隸屬函數來刻畫元素對集合屬于程度的連續過渡性,隸屬函數是0,1區間內的一個實數函數,當隸屬函數u x的圖形如圖1所示,則模糊數 =A ,A ,A 稱為三角模糊數,其中A 、A 、A 均為非負實,u x的函數表達式如式(1);當隸屬函數u x的圖形如圖2所示,則模糊數 =B ,B 稱為半梯形分布的模糊數,其中B 、B 均為非負實,u x的函數表達式如式(2)所示[6]。

u x=(1)

u x=(2)

設兩個三角模糊數=A,A,A和=A,A,A,實數?鄣,則滿足以下關系:

+=A+A, A+A, A+A

-=A-A, A-A, A-A

+?鄣=A+?鄣, A+?鄣, A+?鄣

?鄣=?鄣A, ?鄣A, ?鄣A

2問題描述

本文考慮將訂單集J=J ,J ,J ,…,J 中的n個訂單安排到一臺機器上加工,由于市場需求的不確定性,訂單J 的需求量用三角模糊數表示,=D,D,D;訂單J 的交貨時間用模糊數表示,=T,T;機器的生產率用P 表示;定單J 的實際交貨時間用模糊數表示,=t,t,t;訂單的重要程度用w 表示;客戶對訂單J 滿意度用Z 表示,客戶滿意度Z 則為訂單實際交貨時間隸屬函數與期望交貨時間隸屬函數的交集所圍成的圖形面積與訂單實際完成交貨時間隸屬函數所形成的圖形面積之比[5],即Z =area∩areaarea,如圖3所示。

假設:(1)各訂單經過其準備時間后即可開始加工,加工的優先級一樣;(2)每一時刻機器只能加工一份訂單;(3)加工過程為不間斷,緩沖區容量為無限大;(4)操作允許等待,即前一個操作未完成,則后面的操作需要等待;(5)當訂單提前于客戶需求時間,則需在倉庫等待,倉庫容量無限大。

本文以客戶總的滿意度Z最大為目標函數,建立數學模型為:

MaxZ=Max w Z(3)

s.t.

=+(4)

P ≤P ≤P(5)

w =1 (6)

Z =(7)

由于需求量是模糊的,所以訂單的實際交貨時間也是模糊的,式(4)為實際交貨時間;式(5)為機器的能力約束;式(6)將訂單的重要程度歸一化處理;式(7)是不同情況下滿意度的計算。

3算法設計

目前,解決生產調度問題的有效算法是遺傳算法(GA),它主要是借用生物進化中的“適者生存”的規律,在競爭的過程中保留優良的個體。本文將模型中的模糊數通過客戶滿意度轉化成實數,采用遺傳算法進行最優排序。

(1)染色體編碼:采用自然數編碼,用自然數表示訂單,如有10個訂單,則分別用自然數1,2,3,…,10來表示。

(2)初始值的產生:由于是單機生產調度問題,為了能遍歷所有的排列,則采用隨機產生初始種群,即令訂單隨機排列生產順序,群體的規模為訂單數量的1～2倍。

(3)適應函數:用目標函數來計算各個染色體目標值,然后將同一群體中的m個染色體按目標函數的從小到大排列,直接取分布概率為:Pk= , 1≤k≤m。

(4)遺傳運算:隨機產生一個同染色體有相等維數的不變位向量,每一個分量產生0或1,1表示不變,0表示變,需要變化的基因分別按對方的基因順序選取不重基因順序排列。如:向量10010101

父A15687324——子A16782354

父B36874215——子B36815724

(5)變異運算:采用隨機變換兩個基因的方法,將染色體的一個基因與另一基因交換位置。如:父15687324——子13687542

在遺傳變異過程中,為了更快地得到最優個體,將遺傳后的子代與父代進行比較,選擇子代與父代中優良的染色體作為下次遺傳的父代,最優個體不參加交叉及變異,每次種群的規模保持一致。

4仿真分析

假設某企業收到20個訂單如表1所示,為了計算方便,生產率取1。利用上述算法,采用C語言編程進行仿真,初始種群個體數為30,迭代次數為200,交叉概率為0.6,變異概率為0.03。

通過仿真可以得到圖4、圖5。圖4反映了目標函數值隨迭代次數增加的變化趨勢,從圖中可以看出,在130代之前目標函數值不斷增加,130代之后開始處于穩定,表明基本接近了最優值。采用其它的交叉變異概率,選擇不同的迭代次數,雖然訂單的排列順序不同,但最終目標接近一致。由圖5可以得到這一段生產周期內每個訂單的生產順序,進而可以合理的安排生產任務,進行物料的準備。

5結論

本文對模糊需求情況下的單機生產調度問題進行了較為深入、全面研究,運用模糊數學的理論建立了生產調度模型,考慮模糊需求量和模糊交貨期的模糊流水車間調度模型,采用所有客戶滿意度最大為目標函數,使用遺傳算法搜索到最優加工順序。本文提出的算法通過仿真研究驗證了其有效性,為模糊環境下生產計劃與調度問題的研究提供了一種方法與途徑。

參考文獻:

[1] 蘇生,戰德臣,李海波,等. 不確定需求和能力約束下的多目標多工廠生產計劃[J]. 計算機集成制造系統,2007,13(4):692

-697.

[2] 孫光圻,趙娜,包紅. 相關、不確定需求下生產計劃的優化[J]. 遼寧師范大學學報:自然科學版,2007,30(3):273-276.

[3] 李初福,何小容,陳丙珍,等. A Hybrid Programming Model for Optimal Production Planning under Demand Uncertainty in Refinery[J]. Chinese Journal of Chemical Engineering, 2008,16(2):241-246.

[4] 顧幸生. 不確定性條件下的生產調度[J]. 華東理工大學學報,2000,26(5):441-446.

[5] Masatoshi Sakawa, Ryo Kubota. Fuzzy programming for multiobjective job shop scheduling with fuzzy processing time and fuzzy duedate through genetic algorithms[J]. European Journal of Operational Research, 2000(120):393-407.

[6] 彭祖贈,孫韞玉. 模糊數學及其應用[M]. 武漢:武漢大學出版社,2002.

注:本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文