需求量不確定條件下單臺機生產(chǎn)調度問題

呂 恒 肖 漢

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

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

中圖分類號: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引言

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

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

1模糊函數(shù)

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

u x=(1)

u x=(2)

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

+=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 的需求量用三角模糊數(shù)表示,=D,D,D;訂單J 的交貨時間用模糊數(shù)表示,=T,T;機器的生產(chǎn)率用P 表示;定單J 的實際交貨時間用模糊數(shù)表示,=t,t,t;訂單的重要程度用w 表示;客戶對訂單J 滿意度用Z 表示,客戶滿意度Z 則為訂單實際交貨時間隸屬函數(shù)與期望交貨時間隸屬函數(shù)的交集所圍成的圖形面積與訂單實際完成交貨時間隸屬函數(shù)所形成的圖形面積之比[5],即Z =area∩areaarea,如圖3所示。

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

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

MaxZ=Max w Z(3)

s.t.

=+(4)

P ≤P ≤P(5)

w =1 (6)

Z =(7)

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

3算法設計

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

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

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

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

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

父A15687324——子A16782354

父B36874215——子B36815724

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

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

4仿真分析

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

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

5結論

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

參考文獻:

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

-697.

[2] 孫光圻,趙娜,包紅. 相關、不確定需求下生產(chǎn)計劃的優(yōu)化[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] 顧幸生. 不確定性條件下的生產(chǎn)調度[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] 彭祖贈,孫韞玉. 模糊數(shù)學及其應用[M]. 武漢:武漢大學出版社,2002.

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