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

呂 恒 肖 漢

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

關(guān)鍵詞:不確定性;單機(jī)調(diào)度;遺傳算法

中圖分類號:F273文獻(xiàn)標(biāo)識碼: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)調(diào)度問題的研究源于20世紀(jì)50年代,由于該問題的實(shí)用性和重要性,隨之在運(yùn)籌學(xué)和工業(yè)工程等學(xué)科中形成一個(gè)獨(dú)立的分支方向。直到目前,專家學(xué)者仍然在研究不同情況下生產(chǎn)調(diào)度問題。由于現(xiàn)在的生活節(jié)奏加快,產(chǎn)品的周期越來越短,隨之對產(chǎn)品的需求預(yù)測也成為現(xiàn)在生產(chǎn)的一個(gè)重要問題。企業(yè)在不能準(zhǔn)確預(yù)測市場需求情況下如何更好地安排生產(chǎn)、更快地占領(lǐng)市場已經(jīng)成為挑戰(zhàn)。因此,在市場需求不確定的情況下更好地安排生產(chǎn)對企業(yè)的發(fā)展有重要的意義。

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

1模糊函數(shù)

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

u x=(1)

u x=(2)

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

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

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

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

?鄣=?鄣A(chǔ), ?鄣A(chǔ), ?鄣A(chǔ)

2問題描述

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

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

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

MaxZ=Max w Z(3)

s.t.

=+(4)

P ≤P ≤P(5)

w =1 (6)

Z =(7)

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

3算法設(shè)計(jì)

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

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

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

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

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

父A15687324——子A16782354

父B36874215——子B36815724

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

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

4仿真分析

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

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

5結(jié)論

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

參考文獻(xiàn):

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

-697.

[2] 孫光圻,趙娜,包紅. 相關(guān)、不確定需求下生產(chǎn)計(jì)劃的優(yōu)化[J]. 遼寧師范大學(xué)學(xué)報(bào):自然科學(xué)版,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)調(diào)度[J]. 華東理工大學(xué)學(xué)報(bào),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] 彭祖贈(zèng),孫韞玉. 模糊數(shù)學(xué)及其應(yīng)用[M]. 武漢:武漢大學(xué)出版社,2002.

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