• 
    

    
    

      99热精品在线国产_美女午夜性视频免费_国产精品国产高清国产av_av欧美777_自拍偷自拍亚洲精品老妇_亚洲熟女精品中文字幕_www日本黄色视频网_国产精品野战在线观看 ?

      基于遺傳算法的RGV 動態(tài)調(diào)度問題

      2018-12-19 05:19:48李新靚王心如車東宇吳宇航
      新一代信息技術(shù) 2018年2期
      關(guān)鍵詞:解碼遺傳算法工序

      李新靚,王心如,車東宇,吳宇航

      (1. 華北理工大學(xué)以升創(chuàng)新教育基地,河北 唐山 063210;2. 華北理工大學(xué)理學(xué)院,河北 唐山 063210; 3. 華北理工大學(xué)數(shù)學(xué)建模創(chuàng)新實(shí)驗(yàn)室,河北 唐山 063210;4. 河北省數(shù)據(jù)科學(xué)與應(yīng)用重點(diǎn)實(shí)驗(yàn)室,河北 唐山 063210)

      0 引言

      隨著我國科學(xué)技術(shù)的發(fā)展和WTO 的加入,RGV(有軌穿梭小車)應(yīng)運(yùn)而生,提高了勞動生產(chǎn)率,而在制造業(yè),調(diào)度是實(shí)現(xiàn)制造業(yè)生產(chǎn)高效率、高柔性和高可靠性的關(guān)鍵,制定合理的RGV 動態(tài)調(diào)度策略擁有強(qiáng)大的時(shí)代背景和現(xiàn)實(shí)意義。RGV(有軌穿梭小車)提高了勞動生產(chǎn)率,在制造業(yè),調(diào)度是實(shí)現(xiàn)制造業(yè)生產(chǎn)高效率、高柔性和高可靠性的關(guān)鍵,分別考慮一道工序與兩道工序的物料加工形式、正常工作與發(fā)生故障的情況,制定合理的RGV 動態(tài)調(diào)度策略擁有強(qiáng)大的時(shí)代背景和現(xiàn)實(shí)意義。

      1 模型假設(shè)

      (1)假設(shè)人力資源為無限資源,不考慮人力資源的調(diào)度影響;

      (2)假設(shè)工件的任一工序必須在其前道工序完成后才能開始,即前一個(gè)工序未完成,則后面工序需要等待,保證同一工件不會同時(shí)在兩臺機(jī)器上加工;

      (3)假設(shè)任一臺機(jī)器每次只能加工一個(gè)工件,且一旦開工就不能中斷;

      (4)假設(shè)各工件經(jīng)過其準(zhǔn)備時(shí)間后可開始加工,工件的加工時(shí)間事先給定,且在整個(gè)加工工程中保持不變。

      2 模型建立及求解

      2.1 模擬工件到達(dá)個(gè)數(shù)

      根據(jù)許多研究表明[1],在一定的時(shí)間內(nèi),制造車間中的工件隨機(jī)到達(dá)相應(yīng)的CNC 處理機(jī)器的個(gè)數(shù)可呈泊松分布[2]。利用泊松分布公式可模擬一班次(8 個(gè)小時(shí))內(nèi)加工工件的個(gè)數(shù)。

      設(shè)泊松分布系數(shù)為λ,任意兩個(gè)先后到達(dá)同一CNC 的工件之間的時(shí)間間隔服從參數(shù)為λ 的指數(shù)分布,則根據(jù)泊松分布方程[3]:

      其中λ 為工件平均到達(dá)率,U 為車間利用率,m 為車間機(jī)器數(shù)量,μ 為工序的平均加工時(shí)間, μg為每個(gè)工件的平均加工序數(shù)。代入各加工參數(shù)得到λ=0.00879,則一班次之內(nèi)加工工件的個(gè)數(shù)大約為235 件。

      2.2 確定優(yōu)化系統(tǒng)效率的指標(biāo)

      2.2.1 建立實(shí)際生產(chǎn)的指標(biāo)體系[4]

      RGV 動態(tài)調(diào)度的目標(biāo)是確定最佳的產(chǎn)品加工順序,滿足裝配時(shí)間的合理調(diào)度,使得加工系統(tǒng)的各性能指標(biāo)達(dá)到最優(yōu)。RGV 的動態(tài)調(diào)度的性能指標(biāo)主要包括:縮短生產(chǎn)周期、降低生產(chǎn)成本、提高生產(chǎn)柔性,基于此目的考慮動態(tài)調(diào)度的性能指標(biāo),如圖1 所示:

      圖1 RGV 動態(tài)調(diào)動指標(biāo)體系 Fig.1 RGV dynamic mobilization indicator system

      2.2.2 構(gòu)造優(yōu)化系統(tǒng)的目標(biāo)函數(shù)

      分析實(shí)際情況可知,時(shí)間的指標(biāo)T越小,成本C越低,資源R利用效率越高,越符合優(yōu)化的條件,由此建立RGV 車間生產(chǎn)作業(yè)的動態(tài)調(diào)度數(shù)學(xué)模型,以及模型的目標(biāo)函數(shù)[5]。

      (1)關(guān)于時(shí)間指標(biāo)T

      包括有生產(chǎn)周期T1、提前或拖延完工時(shí)間T2、無效時(shí)間 T3。生產(chǎn)周期 T1是指完成所有的裝配任務(wù)所需的總時(shí)間,是反映車間的生產(chǎn)效率的重要的指標(biāo)之一,1T 計(jì)算公式如下:

      其中,tijk為單位工件的加工時(shí)間,nijk為工件規(guī)定的生產(chǎn)數(shù)量,mijk為CNC 移動的時(shí)間,Tijkb為故障修復(fù)時(shí)間, Tcijk為轉(zhuǎn)移機(jī)器的時(shí)間,dijk為上一個(gè)工件與下一個(gè)工件加工的沖突時(shí)間。求和部分表示的是裝配線完成所有裝配任務(wù)的完工時(shí)間。

      提前或拖延時(shí)間 T2,客戶規(guī)定的交貨期通常采用時(shí)間窗函數(shù),計(jì)算公式如下:

      其中[ pi, qi]為客戶規(guī)定的完工時(shí)間的區(qū)間,T 為產(chǎn)品完工時(shí)間即產(chǎn)品在各裝配線上最晚的完工時(shí)間。

      無效生產(chǎn)時(shí)間 T3,包括生產(chǎn)準(zhǔn)備的時(shí)間、產(chǎn)品換加工CNC 的時(shí)間、CNC 故障維修的時(shí)間等,其計(jì)算公式如下:

      (2)關(guān)于成本C

      根據(jù)對實(shí)際生產(chǎn)的理解,將成本分為原材料的成本 C1、故障成本 C2、人工成本 C3、庫存成本 C4、加工成本 C5。

      其中cwijk為單個(gè)的工件材料的成本,bk為故障率且其值為1%。

      其中cmijk為單個(gè)工件的加工成本,cgijk為單位故障時(shí)間的損失費(fèi)用。

      其中 cf為單個(gè)機(jī)器的維修費(fèi)用。

      庫存成本指的是提前完成的產(chǎn)品其必須保留到交貨期而耗用的成本,計(jì)算公式如下:

      Cs的含義為單個(gè)工件的存儲費(fèi)用,a、 b 分別表示規(guī)定的取貨日期前、后的取貨時(shí)間。

      (3)關(guān)于資源指標(biāo)R

      2.3 嵌入貪婪解碼算法的遺傳算法

      算法框圖如圖2 所示。

      圖2 遺傳算法的基本過程 Fig.2 Basic process of genetic algorithm

      2.3.1 編碼

      編碼就是解的遺傳基因[6],為其的數(shù)字化表示,它是在應(yīng)用的遺傳算法實(shí)施優(yōu)化過程中遇到的首要問題,也是應(yīng)用成功與否的關(guān)鍵之一。在眾多編碼方法中,目前基于工序的編碼方式是最為合理的:編碼方式和相對應(yīng)的解碼方案簡單,柔性高、容易實(shí)現(xiàn)。

      圖3 解碼方式 Fig.3 Decoding mode

      2.3.2 貪婪解碼算法

      將插入式貪婪解碼算法,應(yīng)用到給定的主動調(diào)度的反轉(zhuǎn)染色體、反轉(zhuǎn)工藝的路線,就能得到全主動調(diào)度[7]。

      表1 貪婪解碼算法 Tab.1 Greedy decoding algorithm

      對于一個(gè)給定的主動調(diào)度,通過反轉(zhuǎn)該調(diào)度,關(guān)于工序編碼的染色體及解決問題的工藝的路線,按半主動解碼方式,對反轉(zhuǎn)的染色體解碼,可將原來的主動調(diào)度轉(zhuǎn)變成一個(gè)新的動態(tài)調(diào)度,與原主動調(diào)度在每臺機(jī)器上的加工順序相反。

      2.3.3 交叉操作

      交叉是遺傳算法中的最重要的操作[8],并決定了的遺傳算法的全局搜索能力。采用POX 交叉算法的能夠很好地繼承父代特征。

      圖4 POX 算法 Fig.4 POX algorithm

      2.3.4 變異操作

      通過改進(jìn)遺傳機(jī)制中的變異操作來改良遺傳算法,使得整個(gè)體制可以得到優(yōu)秀的有效解,所以決定采用基于鄰域搜索的一種新型變異算子,它可以保持群體的狀態(tài)多樣性,而且能通過局部的搜索來改善系統(tǒng)的穩(wěn)定性,提高最優(yōu)解的出現(xiàn)頻率。

      2.3.5 選擇操作

      選擇操作的作用是避免有效基因的損失,使高性能的個(gè)體更大的概率生存,結(jié)合最佳個(gè)體保存和比例選擇,引入個(gè)體競爭,從而提高全局的收斂效率和系統(tǒng)的計(jì)算的效率。采用最佳個(gè)體的保存和比例選擇兩種策略的相結(jié)合的方式,產(chǎn)生隨機(jī)數(shù)rand∈[0,1],滿足:

      2.3.6 適應(yīng)度函數(shù)

      將染色體經(jīng)過交叉、變異等過程變?yōu)樾碌娜旧w子代,但并不是所有的子代染色體都可以使RGV的動態(tài)調(diào)度策略變得更滿足于給定的指標(biāo),提高系統(tǒng)效率。

      圖5 只含一道工序的各工序甘特圖 Fig.5 Gantt chart of each process with only one process

      對于兩道工序的過程,最大完成工時(shí)分別為28378 s、35280 s、27482 s。

      圖6 含兩道工序的各工序甘特圖 Fig.6 Gantt diagram of each process with two processes

      發(fā)生故障的時(shí)候,兩種情況如下:

      (1)只含有一道工序時(shí),CNC#6 在12760 s 時(shí)發(fā)生故障,由求解過程中的輸出P 可知,發(fā)生故障時(shí)第161 個(gè)工件正在第六臺上加工,工件報(bào)廢,在發(fā)生故障的期間,凍結(jié)CNC#6 在發(fā)生故障之前的已預(yù)約工件202 號與207 號,直至13340 s 時(shí)機(jī)器設(shè)備維修好立即投入使用,以13340 s 為起始點(diǎn)對剩余工件進(jìn)行調(diào)度,由模型求得完成該系統(tǒng)最大完工時(shí)為18840 s,知得原工時(shí)為19720 s,所以發(fā)生故障時(shí)的RGV 的動態(tài)調(diào)度方案對于系統(tǒng)的效率具有促進(jìn)作用。

      圖7 只含一道工序故障甘特圖 Fig.7 Contains only one process fault gantt diagram

      (2)當(dāng)系統(tǒng)包含兩道工序時(shí),CNC#3 在7560s 時(shí)發(fā)生故障,由求解過程中的輸出P 可知,發(fā)生故障時(shí)第72 個(gè)工件正在第六臺上加工,據(jù)題意可知該工件報(bào)廢,在發(fā)生故障的期間,凍結(jié)CNC#3 在發(fā)生故障之前的已預(yù)約工件98 號、86 號等工件,直至8400 s 時(shí)機(jī)器設(shè)備維修好立即投入使用,以8400 s為起始點(diǎn)對剩余工件進(jìn)行調(diào)度,由模型求得完成該系統(tǒng)最大完工時(shí)為35270 s,知得原工時(shí)為35280 s,所以發(fā)生故障時(shí)的RGV 的動態(tài)調(diào)度方案對于系統(tǒng)的效率具有促進(jìn)作用。

      圖8 含兩道工序的故障甘特圖[9] Fig.8 Fault gantt diagram with two processes

      算法有效性的分析,測試算法的性能,進(jìn)行仿真及分析。

      為測試算法性能,采用柔性車間調(diào)度的兩個(gè)問題Q1(十工件十機(jī)器)以及Q2(六工件四機(jī)器)和選擇能確定性能的加工數(shù)據(jù)作為算法好壞的指標(biāo),構(gòu)造2 個(gè)不相同的RGV 動態(tài)調(diào)度的測試。且將測試問題看作一般性調(diào)度問題,即工序的加工機(jī)器與各工序的時(shí)間已知,找到工序的最優(yōu)排序即RGV 的最佳調(diào)度策略并輸出該系統(tǒng)完成加工固定工件數(shù)所需要的最大工時(shí)。

      提前規(guī)定好算法內(nèi)的參數(shù):最大遺傳代數(shù)MAXGEN=500,個(gè)體數(shù)目NIND=20,代溝GGAP=0.9,交叉率XOVR=0.8,變異率MUTR=0.6,分別采用建立的模型和基本遺傳算法對每個(gè)測試隨機(jī)計(jì)算20次,得到結(jié)果如表所示,其中,Tmax,AMN、No.BMN 和AG 分別表示兩種算法運(yùn)行20 次結(jié)果后,其中所得的最大完工時(shí),平均的生產(chǎn)周期、得到最優(yōu)的生產(chǎn)結(jié)果的次數(shù)以及得到最優(yōu)解的代數(shù)平均值。

      表2 改進(jìn)遺傳算法 Tab.2 Improved genetic algorithm

      表2 為所得的測試結(jié)果,可知改進(jìn)的遺傳算法采用了貪心解碼算法以及基于鄰域搜索[10]的變異操作后可獲得最優(yōu)生產(chǎn)結(jié)果的次數(shù)增多,比原來的基本遺傳算法的穩(wěn)定性提高顯著;相比采用基本單點(diǎn)式或隨機(jī)式交叉方式,改進(jìn)后的遺傳算法應(yīng)用POX 交叉算子進(jìn)行交叉操作,使其可繼承父代優(yōu)良特征的性能大大提高;改進(jìn)的算法的AG 指標(biāo)較大,說明在選擇操作過程中結(jié)合最佳個(gè)體保存和比例選擇,有效提高了全局收斂和計(jì)算效率,進(jìn)而說明改進(jìn)的算法可以較優(yōu)良的跳出尋找局部最優(yōu)解,避免早熟收斂。

      通過解的變化和種群均值的變化,可見應(yīng)用改進(jìn)的遺傳算法的收斂性。

      圖9 解的變化與種群均值變化的過程 Fig.9 Change of solution and change of population mean

      3 結(jié)論

      遺傳算法利用簡單的編碼技術(shù)和繁殖機(jī)制來表現(xiàn)復(fù)雜的現(xiàn)象,僅根據(jù)個(gè)體個(gè)體的適應(yīng)度值進(jìn)行搜索,不受限制條件的約束,操作簡單且具有高效性、魯棒性、強(qiáng)通用性等特點(diǎn)。

      利用貪婪解碼算法優(yōu)化遺傳算法,將搜索空間限于主動調(diào)度集,不僅能保證最優(yōu)調(diào)度存在,而且能提高搜索效率。

      基于工序編碼的染色體只具有半Lamark 特性,遺傳操作的設(shè)計(jì)對算法的性能有較大影響。 一班(8 個(gè)小時(shí))內(nèi)加工工件數(shù)約為235 個(gè)。選取產(chǎn)品完成時(shí)間、生產(chǎn)周期等時(shí)間指標(biāo),原材料成本、人工成本等成本指標(biāo),人員利用率、時(shí)間利用率等資源指標(biāo)作為優(yōu)化約束條件。應(yīng)用遺傳算法對RGV 動態(tài)調(diào)度問題進(jìn)行求解,編碼方式應(yīng)用基于工序的編碼方式;插入貪婪解碼算法對傳統(tǒng)遺傳算法進(jìn)行優(yōu)化;應(yīng)用POX 交叉算子進(jìn)行交叉操作;采用基于鄰域搜索的變異操作;在選擇操作過程中結(jié)合最佳個(gè)體保存和比例選擇,引入個(gè)體競爭,提高全局收斂和計(jì)算效率;得出235 個(gè)工件一班之內(nèi)的加工順序流程。

      猜你喜歡
      解碼遺傳算法工序
      《解碼萬噸站》
      120t轉(zhuǎn)爐降低工序能耗生產(chǎn)實(shí)踐
      昆鋼科技(2022年2期)2022-07-08 06:36:14
      大理石大板生產(chǎn)修補(bǔ)工序詳解(二)
      石材(2020年4期)2020-05-25 07:08:50
      解碼eUCP2.0
      中國外匯(2019年19期)2019-11-26 00:57:32
      土建工程中關(guān)鍵工序的技術(shù)質(zhì)量控制
      NAD C368解碼/放大器一體機(jī)
      Quad(國都)Vena解碼/放大器一體機(jī)
      基于自適應(yīng)遺傳算法的CSAMT一維反演
      一種基于遺傳算法的聚類分析方法在DNA序列比較中的應(yīng)用
      基于遺傳算法和LS-SVM的財(cái)務(wù)危機(jī)預(yù)測
      鹰潭市| 四川省| 柳林县| 永吉县| 汝城县| 永和县| 新龙县| 龙游县| 施甸县| 元氏县| 齐齐哈尔市| 永寿县| 澎湖县| 齐河县| 寿光市| 建始县| 石狮市| 汝城县| 都安| 沈阳市| 连云港市| 永丰县| 泰州市| 桦甸市| 石台县| 石狮市| 汕尾市| 苏尼特左旗| 寿宁县| 浦东新区| 涟水县| 鄂托克前旗| 通化县| 新晃| 错那县| 望城县| 肇庆市| 九龙城区| 贵定县| 三明市| 宁德市|