計(jì)算機(jī)輔助生產(chǎn)線平衡與產(chǎn)能分析研究

1、計(jì)算機(jī)輔助生產(chǎn)線平衡與產(chǎn)能分析研究計(jì)算機(jī)輔助生產(chǎn)線平衡與產(chǎn)能分析研究 計(jì)算機(jī)輔助生產(chǎn)線平衡與產(chǎn)能分析研究 摘要 生產(chǎn)線平衡是生產(chǎn)線設(shè)計(jì)規(guī)劃中重要的組合優(yōu)化決策問(wèn)題,與生產(chǎn)線這一生產(chǎn)方式可謂同日而生,其相關(guān)的解決方案也可謂汗牛充棟,但是具體的算法設(shè)計(jì)卻少見(jiàn)披露.本設(shè)計(jì)著重于計(jì)算機(jī)輔助生產(chǎn)線平衡和產(chǎn)能分析系統(tǒng)(Computer Aided Assembly Line Balancing and Capacity Analysis,CAALB&CA)的算法研究和編程實(shí)現(xiàn).系統(tǒng)利用開(kāi)放的關(guān)系數(shù)據(jù)庫(kù)平臺(tái)和面向?qū)ο蟮某绦蛟O(shè)計(jì)技術(shù),構(gòu)造了生產(chǎn)線平衡和產(chǎn)能分析中的作業(yè),工作站,產(chǎn)品,生產(chǎn)線等仿真對(duì)象,導(dǎo)出了單

2、一產(chǎn)品與混合產(chǎn)品,直線與U型布局生產(chǎn)線平衡優(yōu)化中先后關(guān)系矩陣,作業(yè)集合,網(wǎng)絡(luò)圖等基礎(chǔ)算法,采用有序雙點(diǎn)交叉遺傳算法以同時(shí)實(shí)現(xiàn)這些生產(chǎn)線的平衡優(yōu)化;并充分考慮實(shí)際工程應(yīng)用可能的需求,提出了并行工作站和產(chǎn)能調(diào)整的概念和相應(yīng)的算法;在混合產(chǎn)品生產(chǎn)線的平衡優(yōu)化中還考慮了不同的優(yōu)化目標(biāo)函數(shù)和作業(yè)分配均衡度指標(biāo).在本文最后用實(shí)際工程的數(shù)據(jù)對(duì)系統(tǒng)進(jìn)行了驗(yàn)證. 關(guān)鍵詞:生產(chǎn)線平衡,產(chǎn)能分析,遺傳算法,計(jì)算機(jī)輔助計(jì)算機(jī)輔助生產(chǎn)線平衡與產(chǎn)能分析研究 RESEARCH ON COMPUTER AIDED ASSEMBLY LINE BALANCING AND CAPACITY ANALYSIS ABSTRACT A

3、ssembly lines balancing problem is an important decision problem when (re-)configuring an assembly line. It consists of distributing the total workload for manufacturing any unit of the product to be assemb among the work stations along the line corresponding to the cycle time. Production capacity a

4、nalysis focuses on the balance of production capacity and production resource, which contributes much to the efficiency of a production system. This thesis aims to study the fundament algorithms for these two problems and builds up a test edition of the Computer Aided Assembly Line Balancing and Cap

5、acity Analysis System (CAALB&CA). In this system, a kind of genetic algorithm based on feasible tasks sequence is utilized to balance straight and U-shaped assembly line respectively. Then the author extends this algorithm to solve mix-model assembly line balancing problem by combining the products

6、into a virtual representative product. Whats more, this system also applies to the second kind of assembly line problem in which the stations number is fixed and the minimal cycle time is to be found. Key words: assembly line balancing, production capacity analysis,genetic algorithms, computer aided

7、計(jì)算機(jī)輔助生產(chǎn)線平衡與產(chǎn)能分析研究 目 錄 第一章 緒論.1 1.1 問(wèn)題的提出.1 1.1.1 背景介紹.1 1.1.2 生產(chǎn)線平衡問(wèn)題的描述.1 1.1.3 生產(chǎn)線平衡問(wèn)題的分類.2 1.2 研究意義.2 1.3 章節(jié)安排.3 第二章 生產(chǎn)線平衡問(wèn)題方法研究.4 2.1 生產(chǎn)線平衡的基本概念.4 2.2 術(shù)語(yǔ),符號(hào)定義及假設(shè).4 2.2.1術(shù)語(yǔ)定義.4 2.2.2 符號(hào)定義.5 2.2.3 生產(chǎn)線平衡模型的假設(shè).5 2.3 生產(chǎn)線平衡基本思路.5 2.4 生產(chǎn)線平衡的評(píng)價(jià)指標(biāo).6 2.4.1 生產(chǎn)線空閑時(shí)間.6 2.4.2 生產(chǎn)效率.6 2.4.3 生產(chǎn)線平滑指數(shù).6 2.5生產(chǎn)線平衡問(wèn)題

8、算法概要.7 2.6 U型布局生產(chǎn)線平衡.8 第三章 算法設(shè)計(jì).9 3.1遺傳算法概要介紹.9 3.2 單產(chǎn)品生產(chǎn)線平衡算法.9 3.2.1產(chǎn)品作業(yè)先后關(guān)系矩陣.9 3.2.2 構(gòu)建可行作業(yè)序列.11 3.2.3 生成生產(chǎn)線平衡問(wèn)題的可行解.11 3.2.4 遺傳算法設(shè)計(jì).12 3.2.5 ALB2型問(wèn)題遺傳算法設(shè)計(jì).15 3.3 混合產(chǎn)品生產(chǎn)線平衡算法.15 3.3.1 由多個(gè)產(chǎn)品緊后作業(yè)集合構(gòu)造混合生產(chǎn)線先后關(guān)系矩陣.15 3.3.2 由混合生產(chǎn)線先后關(guān)系矩陣生成作業(yè)的緊后作業(yè)集合.15 3.3.3 混合產(chǎn)品生產(chǎn)線平衡算法設(shè)計(jì).17 3.4 產(chǎn)能調(diào)整算法.19 3.4.1 人員及設(shè)備分配.

9、19 3.4.2 產(chǎn)能調(diào)整.20 第四章 系統(tǒng)的設(shè)計(jì)與開(kāi)發(fā).21 4.1 系統(tǒng)的結(jié)構(gòu)與功能.21 計(jì)算機(jī)輔助生產(chǎn)線平衡與產(chǎn)能分析研究 4.2系統(tǒng)模塊功能簡(jiǎn)述.22 4.2.1通用數(shù)據(jù)管理模塊.22 4.2.2 項(xiàng)目生成模塊.22 4.2.3生產(chǎn)線平衡模塊.22 4.2.4 產(chǎn)能調(diào)整模塊.23 4.3 系統(tǒng)模型設(shè)計(jì).23 4.3.1數(shù)據(jù)流程圖.25 4.3.2系統(tǒng)對(duì)象.25 4.3.4 模塊的結(jié)構(gòu)與 第一章 緒論 1.1 問(wèn)題的提出 1.1.1 背景介紹 從上世紀(jì)初福特創(chuàng)建第一條汽車工業(yè)流水線開(kāi)始,流水生產(chǎn)線已逐漸成為現(xiàn)代化制造業(yè)中一種主要的生產(chǎn)組織形式,廣泛應(yīng)用于以家電,汽車為代表的大規(guī)模生產(chǎn)

10、中.流水生產(chǎn)線按照產(chǎn)品(零部件) 的生產(chǎn)工藝順序排列工位,使產(chǎn)品(零部件)按照一定的速度,連續(xù)地和有節(jié)奏地經(jīng)過(guò)各個(gè)工位依次加工,直到完成產(chǎn)品成品. 在這種生產(chǎn)組織形式下,一條流水生產(chǎn)線上固定地生產(chǎn)一種或少數(shù)幾種制品,每個(gè)工位均固定完成一道或幾道作業(yè),各工位具有較高的專業(yè)化程度,同時(shí)工位按工藝順序排列,加工對(duì)象在作業(yè)間單向移動(dòng),降低了工件搬運(yùn)成本,減少了作業(yè)間的在制品數(shù)量.每道作業(yè)的工位數(shù)量同各道作業(yè)的加工時(shí)間比例相一致.而且每道作業(yè)都按統(tǒng)一的節(jié)拍進(jìn)行生產(chǎn)(所謂節(jié)拍是指相鄰兩件制品的出產(chǎn)間隔時(shí)間),易于對(duì)各作業(yè)的產(chǎn)量進(jìn)行的生產(chǎn)能力,并獲得一個(gè)最接近實(shí)際生產(chǎn)能力的值.從整體上看,通過(guò)產(chǎn)能與負(fù)荷的平

11、衡,產(chǎn)能分析可以提高整個(gè)企業(yè)的生產(chǎn)運(yùn)作效率.從局部上看,通過(guò)產(chǎn)能分析可以發(fā)現(xiàn)瓶頸環(huán)節(jié),并可通過(guò)采取適當(dāng)措施改善瓶頸環(huán)節(jié),提高生產(chǎn)效率.同時(shí)產(chǎn)能分析還可以為MRPII/ERP中的能力需求計(jì)劃提供產(chǎn)能依據(jù).從結(jié)果上看,如果理論分析的產(chǎn)能比實(shí)際產(chǎn)能高,會(huì)導(dǎo)致生產(chǎn)節(jié)拍的混亂,計(jì)劃下達(dá)的訂單不能及時(shí)完成,延誤交貨期,降低客戶的滿意度,從而降低產(chǎn)品的市場(chǎng)份額;反之,又會(huì)導(dǎo)致開(kāi)工率不足,設(shè)備閑置,應(yīng)該能完成的訂單被取消,失去市場(chǎng)機(jī)遇,同樣也會(huì)失去市場(chǎng)份額. 在進(jìn)行生產(chǎn)線平衡之前,產(chǎn)能分析主要是為了確定生產(chǎn)線的生產(chǎn)能力,找出瓶頸作業(yè),以便在進(jìn)行平衡的時(shí)候可以為該作業(yè)分配并行工作站,增加資源,降低作業(yè)時(shí)間,提高

12、生產(chǎn)能力.在進(jìn)行生產(chǎn)線平衡以后,生產(chǎn)線的生產(chǎn)能力便確定下來(lái),這時(shí)仍可以對(duì)已得到的生產(chǎn)能力進(jìn)行調(diào)整,獲得新的平衡方案,以滿足柔性化生產(chǎn)的需要. 1.2 研究意義 計(jì)算機(jī)輔助生產(chǎn)線平衡與產(chǎn)能分析研究 第 3 頁(yè) 共 52 頁(yè) 入世后,我國(guó)制造業(yè)開(kāi)始與國(guó)際接軌,正逐步成為世界制造中心,各類生產(chǎn)流水線都已經(jīng)或?qū)⒈淮笠?guī)模的采用.生產(chǎn)線平衡作為生產(chǎn)線設(shè)計(jì)中的一個(gè)重要方面,具有巨大的實(shí)用價(jià)值.在國(guó)外,這方面的研究文獻(xiàn)較多,其計(jì)算機(jī)輔助軟件也已面市,如Proplanner等,但其昂貴的價(jià)格也令很多國(guó)內(nèi)企業(yè)望而卻步;在國(guó)內(nèi)也有這方面的研究和類似的軟件問(wèn)世,但多數(shù)都只能解決直線型的生產(chǎn)線平衡問(wèn)題,對(duì)U型生產(chǎn)線平衡

13、的解決方案較少. 本文采用遺傳算法,分別對(duì)生產(chǎn)線平衡的兩類問(wèn)題,按單一產(chǎn)品直線型,多種產(chǎn)品混合直線型,單一產(chǎn)品U型,多種產(chǎn)品混合U型四種生產(chǎn)形式提出了可行的平衡算法,并開(kāi)發(fā)了生產(chǎn)線平衡應(yīng)用軟件系統(tǒng). 1.3 章節(jié)安排 本文將在第二章對(duì)生產(chǎn)線平衡問(wèn)題及其約束進(jìn)行形式化描述,并給出其基本思路和平衡效果的評(píng)價(jià)指標(biāo),同時(shí)簡(jiǎn)要介紹常見(jiàn)的生產(chǎn)線平衡方法.第三章中詳細(xì)描述生產(chǎn)線平衡問(wèn)題的遺傳算法設(shè)計(jì)過(guò)程,第四章將介紹軟件系統(tǒng)的開(kāi)發(fā)和設(shè)計(jì)過(guò)程,第五章將給出兩個(gè)例子使用本軟件進(jìn)行平衡.第六章進(jìn)行全文總結(jié),并展望未來(lái),提出存在的問(wèn)題和今后繼續(xù)研究的方向. 計(jì)算機(jī)輔助生產(chǎn)線平衡與產(chǎn)能分析研究 第 4 頁(yè) 共 52

14、頁(yè) 第二章 生產(chǎn)線平衡問(wèn)題方法研究 2.1 生產(chǎn)線平衡的基本概念 生產(chǎn)線平衡的目的是將產(chǎn)品生產(chǎn)所需的一系列作業(yè)(task)(各項(xiàng)作業(yè)加工時(shí)間已知)按具體的生產(chǎn)順序分組,分配到數(shù)個(gè)工作站(station)中,使得各個(gè)工作站的負(fù)荷滿足生產(chǎn)節(jié)拍的要求并且空閑時(shí)間最小2. A. 作業(yè)(Task) 作業(yè)亦稱為工序,是產(chǎn)品加工過(guò)程中全部工作內(nèi)容的一部分,是完成某項(xiàng)操作所進(jìn)行的最小工作單元,在進(jìn)行生產(chǎn)線平衡時(shí)不能對(duì)作業(yè)再行拆分. B. 工作站(work station) 有時(shí)也稱工位,是生產(chǎn)線的一個(gè)工作地.產(chǎn)品在此工作地完成一個(gè)或幾個(gè)作業(yè)或工序的操作.如在汽車制造業(yè)中,我們可以將汽車在裝配線上停留待裝的部位

15、或者車位看作是一個(gè)工作站. C. 流程圖 流程圖是描述各作業(yè)加工次序的圖.通常產(chǎn)品的作業(yè)之間存在某種技術(shù)上的先后順序約束關(guān)系,某些作業(yè)必須在其他作業(yè)完成之后才能進(jìn)行,我們將這種先后順序關(guān)系稱為作業(yè)先后關(guān)系,它決定了生產(chǎn)過(guò)程中作業(yè)完成的先后次序.實(shí)際上生產(chǎn)線的平衡問(wèn)題很大程度上依賴于流程圖,平衡的效率就取決于優(yōu)先圖的復(fù)雜程度.下圖就是一張簡(jiǎn)單的優(yōu)先圖. 圖2-1 產(chǎn)品加工流程圖 在產(chǎn)品作業(yè)流程圖中,圓表示作業(yè),箭頭表示作業(yè)之間的聯(lián)系,圓中的數(shù)字表示作業(yè)的編號(hào). D. 產(chǎn)品混合比例 它是指混合生產(chǎn)線上生產(chǎn)的各種產(chǎn)品之間的產(chǎn)量比例關(guān)系.在市場(chǎng)需求為主導(dǎo)的現(xiàn)代化制造業(yè)中,這一比例關(guān)系往往是變動(dòng)的,它的

16、變化反映了產(chǎn)品需求量的變化,通常就是生產(chǎn)線動(dòng)態(tài)調(diào)整與平衡的原動(dòng)力. 2.2 術(shù)語(yǔ),符號(hào)定義及假設(shè) 2.2.1術(shù)語(yǔ)定義 緊后作業(yè): 某一作業(yè)的直接后繼作業(yè),不包括間接后續(xù)關(guān)系.如圖2-1中,作業(yè)2的緊后作業(yè)包括作業(yè)6和作業(yè)7. 后繼作業(yè): 某一作業(yè)的所有后繼作業(yè),包括間接后續(xù)關(guān)系.如圖2-1中,作業(yè)2的后續(xù)作業(yè)包括作業(yè)6,作業(yè)7,作業(yè)9和作業(yè)11. 計(jì)算機(jī)輔助生產(chǎn)線平衡與產(chǎn)能分析研究 第 5 頁(yè) 共 52 頁(yè) 緊前作業(yè): 某一作業(yè)的直接先行作業(yè),不包括間接先行關(guān)系.如圖2-1中,作業(yè)7的緊前作業(yè)僅為作業(yè)2. 先行作業(yè): 某一作業(yè)的所有先行作業(yè),包括間接先行關(guān)系.如圖2-1中,作業(yè)7的先行作業(yè)包括

17、作業(yè)2和作業(yè)1. 作業(yè)先后關(guān)系矩陣:在生產(chǎn)線平衡中,我們通常使用產(chǎn)品作業(yè)先后關(guān)系矩陣來(lái)描述產(chǎn)品作業(yè)間的先行約束關(guān)系.矩陣的行和列均代表相應(yīng)編號(hào)的作業(yè),矩陣中的0代表列作業(yè)可以在行作業(yè)之前進(jìn)行,也可以在行作業(yè)之后進(jìn)行;而1代表列作業(yè)一定要在行作業(yè)完成之后才能進(jìn)行,即行作業(yè)為列作業(yè)的先行作業(yè),從而列作業(yè)也為行作業(yè)的后續(xù)作業(yè).對(duì)于圖2-1中的產(chǎn)品加工流程圖,其先后關(guān)系矩陣如圖2.2所示. 圖2-2 作業(yè)先后關(guān)系矩陣 2.2.2 符號(hào)定義 N 產(chǎn)品的作業(yè)總數(shù) K 分配的工作站總數(shù) Ti 產(chǎn)品的第i個(gè)作業(yè) ti (i=1,2, ,N)表示產(chǎn)品的作業(yè)i的作業(yè)時(shí)間. PSi,j (i=1,2, ,N; j=

18、1,2, ,N),產(chǎn)品先后關(guān)系矩陣,當(dāng)且僅當(dāng)作業(yè)i必須領(lǐng)先于作業(yè)j時(shí),PS(i,j)=1,否則等于0,包括了直接先后關(guān)系和間接先后關(guān)系. C 產(chǎn)品節(jié)拍時(shí)間,即生產(chǎn)單位產(chǎn)品耗時(shí). Si= Tl , Tm , Tn . 作業(yè)i的緊后作業(yè)的集合. Mk = Tl , Tm , Tn . 為所有分配給工作站k的作業(yè)的集合 T = Ti , Tj , Tk . 產(chǎn)品所有作業(yè)的一個(gè)有序排列,產(chǎn)品的所有作業(yè)均在而且僅在序列中出現(xiàn)一次,作業(yè)排列次序滿足作業(yè)先后關(guān)系的約束. 2.2.3 生產(chǎn)線平衡模型的假設(shè) (1) 在同一條生產(chǎn)線上進(jìn)行加工的產(chǎn)品總是相似的,即大部分的作業(yè)是相同; (2) 產(chǎn)品各道作業(yè)的加工時(shí)間

19、是已知且為定值; (3) 產(chǎn)品的作業(yè)的先后作業(yè)關(guān)系是已知的; (4) 對(duì)于多品種混合生產(chǎn)線,各產(chǎn)品作業(yè)的先后約束不會(huì)出現(xiàn)相互違背的情況,即若在產(chǎn)品A中作業(yè)i需在作業(yè)j完成后才能進(jìn)行,那么在生產(chǎn)線上生產(chǎn)的其余產(chǎn)品中就不會(huì)出現(xiàn)要求作業(yè)j在作業(yè)i完成后才能進(jìn)行的情況3; (5) 工作站之間沒(méi)有在制品庫(kù)存緩沖區(qū),即生產(chǎn)線上生產(chǎn)的產(chǎn)品是一個(gè)連續(xù)流的; (6) 不同產(chǎn)品的相同作業(yè)必須分配到同一個(gè)工作站; (7) 生產(chǎn)線上生產(chǎn)的每個(gè)產(chǎn)品都從頭至尾經(jīng)過(guò)生產(chǎn)線上每一個(gè)工作站. 2.3 生產(chǎn)線平衡基本思路 生產(chǎn)線平衡需要滿足的條件有二,一是在各工作站上進(jìn)行加工的作業(yè)加工時(shí)間之和必須小于生產(chǎn)節(jié)拍,以滿足生產(chǎn)能力的要

20、求,二是產(chǎn)品依次經(jīng)過(guò)各工作站不違反作業(yè)的先后計(jì)算機(jī)輔助生產(chǎn)線平衡與產(chǎn)能分析研究 第 6 頁(yè) 共 52 頁(yè) 約束關(guān)系.因此平衡過(guò)程依照生產(chǎn)節(jié)拍來(lái)進(jìn)行,同時(shí)要求分配的順序滿足作業(yè)的先后關(guān)系限制.傳統(tǒng)的平衡思路如下: (1) 從工作站1開(kāi)始,依順序給工作站分配作業(yè); (2) 確定任務(wù)元素清單,分離可行任務(wù)元素和不可行任務(wù)元素; (3) 去掉已分派的任務(wù)元素; (4) 去掉那些不能滿足前后生產(chǎn)順序關(guān)系的任務(wù)元素,即分配的作業(yè)的前向作業(yè)已全部分配; (5) 去掉那此工作站不能提供足夠時(shí)間的任務(wù)元素,即該作業(yè)時(shí)間不超過(guò)該工作站的空閑時(shí)間,即生產(chǎn)節(jié)拍與以分配到該工作站的時(shí)間之差; (6) 確定一個(gè)能夠指派的

21、任務(wù)元素.比如清單上的第1個(gè)任務(wù)元素或最后一個(gè)任務(wù)元素時(shí)間最長(zhǎng)或最短的任務(wù)元素.也可以任意選擇的任務(wù)元素,或按其他一些標(biāo)準(zhǔn); (7) 改變?nèi)蝿?wù)元素以找到最佳平衡,選擇標(biāo)準(zhǔn)可按照生產(chǎn)效率最高,或者空閑時(shí)間最小等. 對(duì)于生產(chǎn)線平衡的第二類問(wèn)題,即給定工作站數(shù),求滿足生產(chǎn)要求的最小生產(chǎn)節(jié)拍,只需對(duì)上述步驟稍作改動(dòng). 給定工作站數(shù)為N,則理論最小生產(chǎn)周期可按下式計(jì)算: 1NiiTCN=理論 (2-1) 因?yàn)樯a(chǎn)線上最長(zhǎng)的作業(yè)時(shí)間決定了生產(chǎn)節(jié)拍的下限,因此最長(zhǎng)作業(yè)時(shí)間的作業(yè)為瓶頸作業(yè),故比較C理論與瓶頸作業(yè)時(shí)間.若C理論小,則取生產(chǎn)節(jié)拍等于C理論,否則取生產(chǎn)節(jié)拍等于瓶頸作業(yè)時(shí)間,即生產(chǎn)節(jié)拍的下限.然后采

22、用迭代法將作業(yè)分配到各工位,步驟如下: (1) 初始化節(jié)拍TT和迭代速率L; (2) 按前訴步驟分配作業(yè); (3) 若已分配的工作站數(shù)超過(guò)N而仍有作業(yè)未分配,則停止分配,并令CT = CT + L,轉(zhuǎn)入步驟2)重新分配. (4) 若所有作業(yè)都分配完畢時(shí)工作站數(shù)未超過(guò)N,則循環(huán)結(jié)束,輸出最終的生產(chǎn)節(jié)拍. 2.4 生產(chǎn)線平衡的評(píng)價(jià)指標(biāo) 2.4.1 生產(chǎn)線空閑時(shí)間 生產(chǎn)線空閑時(shí)間IdleTime為生產(chǎn)線流失的時(shí)間之和,即各工作站空閑時(shí)間之和. 1NiiIdleTime C K T= (2-2) 2.4.2 生產(chǎn)效率 生產(chǎn)效率E描述了生產(chǎn)線的相對(duì)生產(chǎn)率, 11KiiIdleTimeET= (2-3)

23、2.4.3 生產(chǎn)線平滑指數(shù) 生產(chǎn)線平滑指數(shù)SX,是生產(chǎn)線平衡狀態(tài)的主要指標(biāo),描述了各工作站工作負(fù)荷的差異計(jì)算機(jī)輔助生產(chǎn)線平衡與產(chǎn)能分析研究 第 7 頁(yè) 共 52 頁(yè) 情況. 21ikKikTMCtK=SX (2-4) 其中it為作業(yè)i的作業(yè)時(shí)間,而作業(yè)i被分配至工作站k. 2.5生產(chǎn)線平衡問(wèn)題算法概要 生產(chǎn)線平衡問(wèn)題是也生產(chǎn)線問(wèn)世之日同時(shí)出現(xiàn)的,但正式提出并著手解決這一問(wèn)題的是美國(guó)人B.Bryton,他于1954年完成的碩士論文連續(xù)生產(chǎn)線的平衡,引起了企業(yè)界和學(xué)術(shù)界人士的極大興趣.其后,許多人研究這個(gè)方面的問(wèn)題,并發(fā)表了各種各樣的方法,將研究成果直接用于生產(chǎn)實(shí)踐活動(dòng)中,取得了明顯的經(jīng)濟(jì)效益.

24、生產(chǎn)線平衡是一個(gè)系統(tǒng)工程,其中涉及到生產(chǎn)的方方面面,目前在ALB 問(wèn)題上國(guó)內(nèi)外有許多相關(guān)的論文,他們中有許多是研究生產(chǎn)線平衡的數(shù)學(xué)建模和優(yōu)化算法的.這中間包括了對(duì)于單種產(chǎn)品的研究和多種產(chǎn)品混線裝配的研究,還有不少論文研究了生產(chǎn)線的改善問(wèn)題,即通過(guò)各種途徑縮短工序的周期時(shí)間,增加操作的效率,提高生產(chǎn)率,生產(chǎn)質(zhì)量以及安全性等.就目前研究現(xiàn)狀來(lái)說(shuō)裝配線平衡問(wèn)題的求解方法大致可分為精確算法與近似算法兩大類4. 精確算法(主要是運(yùn)籌學(xué)中的各種算法) 圖2-3 U型生產(chǎn)線布局圖 如圖2-3 所示,這條生產(chǎn)線上共配備4個(gè)操作工,當(dāng)生產(chǎn)任務(wù)減半時(shí),要求工人數(shù)也減半,這時(shí)生產(chǎn)線安排如圖2-4所示. 圖2-4 生

25、產(chǎn)任務(wù)減少后的U型作業(yè)人數(shù)安排 U 型布局的本質(zhì)關(guān)鍵在于生產(chǎn)線的出口和入口在同一個(gè)位置, 我們正是利用這個(gè)特點(diǎn)靈活地增減作業(yè)現(xiàn)場(chǎng)的作業(yè)人員,同時(shí)這樣也便于實(shí)現(xiàn)準(zhǔn)時(shí)制生產(chǎn)的基本思想,即按后工序領(lǐng)取的數(shù)量進(jìn)行生產(chǎn).如圖2-3和2-4所示,生產(chǎn)線的入口和出口都由一個(gè)工人負(fù)責(zé),這樣可以很方便的實(shí)現(xiàn)成品離開(kāi)生產(chǎn)線和原料進(jìn)入生產(chǎn)線的同步.既實(shí)現(xiàn)了生產(chǎn)線的平衡,也使生產(chǎn)線內(nèi)待加工產(chǎn)品數(shù)維持恒定.通過(guò)明確規(guī)定每個(gè)工序可持有的標(biāo)準(zhǔn)待加工產(chǎn)品數(shù),即使出現(xiàn)了不平衡現(xiàn)象,也能很快發(fā)現(xiàn),有利于及時(shí)對(duì)各工序進(jìn)行改善6. 另外,U型生產(chǎn)線上工作站間距離較近,工人可以操作更多的機(jī)器,能夠充分發(fā)揮團(tuán)隊(duì)合作精神;同時(shí)還可以簡(jiǎn)化物

26、料搬運(yùn)過(guò)程,降低庫(kù)存. 在生產(chǎn)線平衡上,U型生產(chǎn)線分配作業(yè)到工作站時(shí), 可以按照從前到后或者從后到前的順序單方向進(jìn)行, 也可以從兩個(gè)方向同時(shí)進(jìn)行. 在直線型的生產(chǎn)線上, 分配作業(yè)元素的順序只能按照單方向進(jìn)行. 因而, 在U 型生產(chǎn)線上, 分配作業(yè)元素時(shí), 選擇的范圍更大. 在一些使用直線型布局不能得到滿意結(jié)果的場(chǎng)合,可以得到更優(yōu)的平衡方案. U-型生產(chǎn)線平衡算比直線型更為復(fù)雜,常見(jiàn)的算法有啟發(fā)式算法,動(dòng)態(tài)規(guī)劃法,遺傳算法,分支定界算法等.計(jì)算機(jī)輔助生產(chǎn)線平衡與產(chǎn)能分析研究 第 9 頁(yè) 共 52 頁(yè) 第三章 算法設(shè)計(jì) 3.1遺傳算法概要介紹 在詳細(xì)介紹求解ALB問(wèn)題的基于可行作業(yè)序列的遺傳算法之

27、前,本文先對(duì)傳統(tǒng)的遺傳算法進(jìn)行一下簡(jiǎn)單的介紹. 遺傳算法是一種基于生物自然選擇與遺傳機(jī)理的隨機(jī)搜索算法,和傳統(tǒng)搜索算法不同,遺傳算法從一組隨機(jī)產(chǎn)生的初始解(稱為種群Population)開(kāi)始搜索過(guò)程.種群中的每個(gè)個(gè)體都是問(wèn)題的一個(gè)可行解,稱為染色體(chromosome).染色體數(shù)值化為一串符號(hào),比如一個(gè)二進(jìn)制字符串.這些染色體在后續(xù)迭代中不斷進(jìn)化,稱為遺傳.在每一代中用適應(yīng)值(fitness)來(lái)測(cè)量染色體的好壞.生成的下一代染色體,稱為后代(offSpring).后代是由前一代染色體通過(guò)交叉(crossover)或者變異(Mutahon)運(yùn)算形成的.交叉是指選擇群體中的兩個(gè)個(gè)體,以這兩個(gè)個(gè)體

28、為雙親,做基因鏈碼的交叉,從而產(chǎn)生兩個(gè)新的個(gè)體做它們的后代.最常用的簡(jiǎn)單交叉方法是隨機(jī)選取一個(gè)截?cái)帱c(diǎn)切開(kāi),并交換其后部基因,從而組合成兩個(gè)新的個(gè)體.變異是指對(duì)于群體中的某個(gè)個(gè)體,即基因鏈碼,隨機(jī)選取某一位(某基因),將該位基因碼翻轉(zhuǎn),1轉(zhuǎn)為0,0轉(zhuǎn)為1.新一代種群形成過(guò)程中,根據(jù)適值的高低選擇部分后代,淘汰部分后代,從而保持種群大小是常數(shù).適值高的染色體被選中的概率較高.這樣,經(jīng)過(guò)若干代之后,算法收斂于最好的染色體,它很可能就是問(wèn)題的最優(yōu)解或次優(yōu)解.其基本程序結(jié)構(gòu)如圖3-1所示5. 圖3-1 傳統(tǒng)遺傳算法基本程序結(jié)構(gòu)圖 遺傳算法是人工智能領(lǐng)域中新興的一種全局尋優(yōu)算法,具有極強(qiáng)的并行搜索能力,尋

29、優(yōu)速度快,能跳出局部最優(yōu),并且不需要任何先驗(yàn)知識(shí)和專家知識(shí)的指導(dǎo). 3.2 單產(chǎn)品生產(chǎn)線平衡算法 在本節(jié)中我們先考慮ALB1型問(wèn)題.基于可行作業(yè)序列的遺傳算法首先需要構(gòu)建可行作業(yè)序列集合.可行作業(yè)序列就是一個(gè)作業(yè)序列T = Ti , Tj , Tk .,這個(gè)序列是產(chǎn)品作業(yè)的一個(gè)全排列,并且所有作業(yè)的出現(xiàn)次序滿足作業(yè)先后關(guān)系的約束.然后將可行作業(yè)序列用貪婪法組合分配入工作站,得到生產(chǎn)線平衡問(wèn)題可行解,根據(jù)可行解構(gòu)建遺傳算法的基礎(chǔ)種群. 3.2.1產(chǎn)品作業(yè)先后關(guān)系矩陣 計(jì)算機(jī)輔助生產(chǎn)線平衡與產(chǎn)能分析研究 第 10 頁(yè) 共 52 頁(yè) 由2.2中所述,我們使用產(chǎn)品作業(yè)先后關(guān)系矩陣描述產(chǎn)品作業(yè)的先后順序

30、約束. 3.2.1.1產(chǎn)品作業(yè)先后關(guān)系矩陣的形態(tài) 很多關(guān)于生產(chǎn)線平衡的文獻(xiàn)中都描述產(chǎn)品的先后關(guān)系矩陣是一個(gè)上三角矩陣.作為上三角矩陣,我們知道矩陣行和列所代表的作業(yè)的排序必定滿足位于矩陣上端的行或矩陣左邊的列所代表的作業(yè)先于矩陣下端的行或矩陣右邊的列所代表的作業(yè),例如,矩陣第一行第一列所代表的作業(yè)一定是該產(chǎn)品的首發(fā)作業(yè).在這種情況下,產(chǎn)品作業(yè)間的先后關(guān)系已經(jīng)是很清晰了,由先后關(guān)系矩陣?yán)L制產(chǎn)品的先后關(guān)系圖或產(chǎn)生可能的作業(yè)序列就十分方便. 但是仔細(xì)的研究發(fā)現(xiàn),這一觀點(diǎn)實(shí)際上僅對(duì)于手工編制的先后關(guān)系矩陣是成立的,對(duì)于計(jì)算機(jī)輔助設(shè)計(jì)而言,通常是由計(jì)算機(jī)根據(jù)緊后作業(yè)集合編制先后關(guān)系矩陣,因此計(jì)算機(jī)需要遍

31、歷緊后作業(yè)集合組成的多叉樹(shù)才能確定作業(yè)之間的完整先后關(guān)系.然而,要按照作業(yè)之間的先后關(guān)系安排作業(yè)在關(guān)系矩陣中的行列位置比較困難.一般情況下,作業(yè)與先后關(guān)系關(guān)系矩陣行列序號(hào)之間的關(guān)系就是作業(yè)在產(chǎn)品作業(yè)清單中的存放順序,要求先后關(guān)系矩陣是一個(gè)上三角矩陣意味著作業(yè)清單的存放順序滿足作業(yè)先后關(guān)系的要求,則通常意味著從數(shù)據(jù)庫(kù)中取出產(chǎn)品作業(yè)時(shí)也必須滿足產(chǎn)品作業(yè)順序的要求,更麻煩的是在多個(gè)產(chǎn)品混合的情況下,由于各產(chǎn)品所包含的作業(yè)不完全相同,為了保證混合后的先后關(guān)系矩陣是一個(gè)上三角矩陣,必須對(duì)原有的先后關(guān)系矩陣進(jìn)行大量的插入和移動(dòng)操作.綜合以上的因素考慮,將先后關(guān)系矩陣定義為上三角矩陣帶來(lái)的麻煩太多,造成軟件

32、不同模塊之間不必要的牽連,因此,必須提出與任意形狀的先后關(guān)系矩陣相關(guān)的算法. 一個(gè)上三角矩陣的產(chǎn)品的先后關(guān)系矩陣隱含了作業(yè)間接先后關(guān)系的概念,即如果A作業(yè)的直接后繼作業(yè)是B作業(yè),B作業(yè)的直接后繼作業(yè)是C作業(yè),則C作業(yè)是A作業(yè)的間接后繼作業(yè),則A作業(yè)是C作業(yè)的間接先行作業(yè).引入間接先后關(guān)系是為了在多產(chǎn)品混合時(shí)正確的創(chuàng)建混合產(chǎn)品的先后關(guān)系矩陣和緊前與緊后作業(yè)集合. 3.2.1.2產(chǎn)品作業(yè)先后關(guān)系矩陣的構(gòu)造 用戶在定義產(chǎn)品時(shí),最直觀的感受是一項(xiàng)作業(yè)的緊前作業(yè),用一組緊后作業(yè)集后描述作業(yè)間的先后關(guān)系: S=S1 , S2 , ,Sni 而在計(jì)算機(jī)內(nèi)部通過(guò)產(chǎn)品先后關(guān)系矩陣PSi,j來(lái)處理約束.由緊后作業(yè)

33、集合S集合變換到先后關(guān)系矩陣的算法分為2個(gè)階段.首先,依據(jù)緊后作業(yè)集合,直接確定關(guān)系矩陣PSi,j的直接關(guān)系位;然后分析直接先后關(guān)系,確定各任務(wù)的間接先后關(guān)系. A. 算法思想: 如果PS(i,j)=1,說(shuō)明Tj是Ti的緊后作業(yè),如果PS(j,k)=1,則說(shuō)明Tk是Tj的緊后作業(yè),因此Ti是Tk 先行作業(yè),進(jìn)一步以此類推,如果PS(j,k)=1,PS(k,l)=1, ,PS(y,z)=1,則導(dǎo)出Ti是Tk,Tl, ,Tz的先行作業(yè). B. 算法設(shè)計(jì) (1) 將先后關(guān)系矩陣PSi,j的所有元素清零. (2) 遍歷Si集合中的所有成員,如果Ti 在集合中,則置PS(i,j)=1. (3) 遍歷S集

34、合,對(duì)S=S1 , S2 , ,Sni 執(zhí)行第2步同樣的操作. (4) 從先后關(guān)系矩陣PSi,j的第一行,第一列的元素PS(1,1)開(kāi)始. (5) 如果某一元素等于1,不失一般性,設(shè)1=ijp,則檢查第j行的所有元素,對(duì)第j行的所有等于1的元素,不失一般性,設(shè)1=jkp,則置PS(i,j)=1. (6) 重復(fù)進(jìn)行5的步驟,直到遍歷PSi,j的所有元素. 說(shuō)明性程序如下: 計(jì)算機(jī)輔助生產(chǎn)線平衡與產(chǎn)能分析研究 第 11 頁(yè) 共 52 頁(yè) For i = 1 To n For j = 1 To n If PS(i, j) = 1 Then For k = 1 Ton If PR(j, k) = 1

35、Then PR(i, k) = 1 End If Next End If Next Next 3.2.2 構(gòu)建可行作業(yè)序列 A. 算法思想: 為了使作業(yè)的排列滿足先后關(guān)系的約束,首先需要確定當(dāng)前可以添加到序列中的作業(yè),即該作業(yè)的先行作業(yè)都已放入這個(gè)作業(yè)序列,也即當(dāng)前的最先行作業(yè).在先后關(guān)系矩陣中,元素全為零的列所代表的作業(yè)就是當(dāng)前的最先行作業(yè),因?yàn)檫@些作業(yè)沒(méi)有緊前作業(yè).例如,對(duì)所有(i=1,2, ,N) ,均有PS(i,j)=0,則Tj是當(dāng)前最先行作業(yè).再?gòu)漠?dāng)前最先行作業(yè)中選擇一個(gè)作業(yè)放入作業(yè)序列,該作業(yè)進(jìn)入作業(yè)序列后,則他的緊后作業(yè)也將滿足先后關(guān)系成為可以進(jìn)行的作業(yè). B. 算法設(shè)計(jì): (1

36、) 設(shè)立一個(gè)緩沖數(shù)組,命名為buf (2) 搜索先后關(guān)系矩陣PSi,j,找出全為零的列,設(shè)為j,判斷對(duì)應(yīng)的作業(yè)Tj是否已經(jīng)進(jìn)入作業(yè)序列,如是,則將其丟棄,如否,則將其對(duì)應(yīng)的列號(hào)j加入buf.繼續(xù)尋找其他全為零的列,執(zhí)行上述相同動(dòng)作,直到所有PSi,j的所有列均已遍歷. (3) 從buf中按照某種算法抽取一項(xiàng)(如隨機(jī)抽取或抽取后續(xù)作業(yè)最多的作業(yè)),設(shè)為k,則將Tk 加入作業(yè)序列T.同時(shí)將先后關(guān)系矩陣PSi,j的第k行全部清為零. (4) 如buf不為空,或PSi,j不為零矩陣,則跳轉(zhuǎn)到第2步繼續(xù)執(zhí)行,否則結(jié)束.作業(yè)序列T = Ti , Tj , Tk .已經(jīng)生成. 圖3-2 可行作業(yè)系列生成算法

37、流程 3.2.3 生成生產(chǎn)線平衡問(wèn)題的可行解 對(duì)于某一給定的作業(yè)序列T = Ti , Tj , Tk .,將其作業(yè)分配給工作站的算法取決于生產(chǎn)線的布置形式.對(duì)于直線型生產(chǎn)線,由于作業(yè)順序已經(jīng)確定,分配工作站的算法計(jì)算機(jī)輔助生產(chǎn)線平衡與產(chǎn)能分析研究 第 12 頁(yè) 共 52 頁(yè) 非常簡(jiǎn)單,采用最大可能分配法,在不超過(guò)生產(chǎn)節(jié)拍的前提下,盡可能多的把作業(yè)分配給工作組.對(duì)于U型生產(chǎn)線,情況要復(fù)雜一些,文獻(xiàn)3指出有6種可能的分配方法,即: (1)交替從作業(yè)序列頭尾分配, (2)交替從頭尾分配,但是序列尾部的作業(yè)優(yōu)先分配, (3)先盡力從作業(yè)序列頭分配,然后再?gòu)淖鳂I(yè)序列尾分配, (4)先盡力從作業(yè)序列尾分配

38、,然后再?gòu)淖鳂I(yè)序列頭分配 (5) 交替從頭尾分配,但是初始優(yōu)先分配作業(yè)序列頭的作業(yè),分配下一個(gè)作業(yè)時(shí),交換優(yōu)先權(quán),優(yōu)先下一輪分配作業(yè)序列尾的作業(yè). (6) 交替從頭尾分配,但是初始優(yōu)先分配作業(yè)序列尾的作業(yè),分配下一個(gè)作業(yè)時(shí),交換優(yōu)先權(quán),優(yōu)先下一輪分配作業(yè)序列頭的作業(yè). 但是,根據(jù)文獻(xiàn)11給出的大量計(jì)算結(jié)果分析,各種的算法的差別不大,限于時(shí)間關(guān)系,本設(shè)計(jì)僅實(shí)現(xiàn)了從作業(yè)序列頭和尾盡力分配,即先從作業(yè)序列頭開(kāi)始,如果頭部的作業(yè)可以分配給工作組,立即分配,如果作業(yè)序列尾部的作業(yè)可以分配,立即分配.直到作業(yè)序列頭尾的作業(yè)均不能再分配為止. 3.2.4 遺傳算法設(shè)計(jì) 遺傳算法的基本步驟如下: (1) 根據(jù)

39、可行解,構(gòu)造指定容量的初始種群染色體. (2) 計(jì)算種群中的所有染色體的目標(biāo)優(yōu)化函數(shù)值,并將染色體的目標(biāo)優(yōu)化函數(shù)值轉(zhuǎn)換為適應(yīng)度. (3) 采用啟發(fā)式選擇,優(yōu)先從種群中挑選一定數(shù)量(如1/2種群數(shù)量)的具有最優(yōu)目標(biāo)優(yōu)化函數(shù)值的染色體進(jìn)入交配種群. (4) 隨即生成0-1之間的隨機(jī)數(shù),采用輪盤(pán)賭算法和染色體適應(yīng)度隨機(jī)選擇其余的染色體進(jìn)入交配種群. (5) 采用有序雙點(diǎn)交叉法,從交配種群中交配產(chǎn)生下一代種群. (6) 重復(fù)從第2步進(jìn)行迭代計(jì)算,直到完成指定次數(shù)的迭代計(jì)算為止. 圖3-3 遺傳算法實(shí)現(xiàn)過(guò)程 在這里我們沒(méi)有采用遺傳算法中的變異操作,主要因?yàn)闃?gòu)成染色體的作業(yè)序列必須滿足作業(yè)的先后順序關(guān)系,

40、而由一條染色體自身通過(guò)交換其上某些作業(yè)的位置而得到的一個(gè)新的作業(yè)序列極其可能就會(huì)違反作業(yè)先后關(guān)系.另一方面,我們構(gòu)建的個(gè)體選擇方法和交叉方法在盡可能做到全局搜索的同時(shí)也注意了對(duì)優(yōu)良個(gè)體的保護(hù). 3.2.4.1 遺傳算法的染色體構(gòu)造方法 遺傳算法染色體構(gòu)造方法用于構(gòu)造遺傳算法所需要的初始種群.根據(jù)遺傳算法的特點(diǎn),初始種群由用戶指定數(shù)量(稱為種群數(shù)量)的染色體構(gòu)成,每一條染色體為一種可能的平衡方案,滿足平衡的全部約束.同時(shí),為實(shí)現(xiàn)通過(guò)遺傳算法全局尋優(yōu)的目的,初始種群應(yīng)計(jì)算機(jī)輔助生產(chǎn)線平衡與產(chǎn)能分析研究 第 13 頁(yè) 共 52 頁(yè) 該具有足夠的代表性,盡可能多包括所有可能的作業(yè)排列,以避免尋優(yōu)中收斂

41、于局部最優(yōu)點(diǎn),這類似于保證染色體的生物多樣性,避免近親繁殖.染色體構(gòu)造分為兩步,即基因編碼和染色體的生成算法如下: (1) 基因編碼,采用前述創(chuàng)建滿足約束要求的作業(yè)序列的方法構(gòu)建作業(yè)序列T = Ti , Tj , Tk .,作為基因編碼.在構(gòu)建作業(yè)序列算法的第3步,假設(shè)當(dāng)前buf內(nèi)的作業(yè)個(gè)數(shù)為M,則先生成一個(gè)1M之間的隨機(jī)數(shù)i,然后,抽取buf內(nèi)的第i個(gè)作業(yè)組成作業(yè)序列.通過(guò)這種方法來(lái)保證染色體的多樣性. (2) 采用前述按照作業(yè)序列分配工作站的算法,為基因編碼分配工作站. (3) 根據(jù)已經(jīng)確定的工作站作業(yè)分配方案,計(jì)算染色體的平衡數(shù)據(jù),如總空閑時(shí)間,空閑時(shí)間均方差,生產(chǎn)線效率等. 3.2.4

42、.2 有序雙點(diǎn)交叉算子方法 有序雙點(diǎn)交叉算子用于遺傳算法的染色體交配,以便產(chǎn)生新一代的染色體.如前所述,用于生產(chǎn)線平衡問(wèn)題的基因編碼是約束要求的作業(yè)序列,有序雙點(diǎn)交叉算子必須保證兩條染色體交叉說(shuō)形成的下一代染色體仍然具有滿足生產(chǎn)線平衡問(wèn)題約束要求的基因編碼,為此算法設(shè)計(jì)如下. 設(shè)基因編碼長(zhǎng)度為N ,等于產(chǎn)品的作業(yè)個(gè)數(shù).P表示種群數(shù)量. (1) 建立一個(gè)長(zhǎng)度為P的數(shù)組,命名為index,index數(shù)組內(nèi)依次存放1-P,即第一個(gè)單元存入1,第P個(gè)單元存入P. (2) 從第一個(gè)單元開(kāi)始,依次進(jìn)行P次以下動(dòng)作. (3) 設(shè)當(dāng)前操作的是index數(shù)組的第i個(gè)單元,生成一個(gè)1P之間的隨機(jī)數(shù)point,然后

43、交換index數(shù)組當(dāng)前單元和第point號(hào)單元. (4) 重復(fù)第3步操作,直到P個(gè)數(shù)組單元均已操作完畢,這是為了使index數(shù)組的序號(hào)具有隨機(jī)性. (5) 設(shè)完成以下動(dòng)作種群數(shù)量/2次. (6) 生成一個(gè)0-1之間的隨機(jī)數(shù),如果該數(shù)小于預(yù)先指定的交叉概率,則進(jìn)行以下動(dòng)作,否則,跳轉(zhuǎn)到第12步. (7) 設(shè)當(dāng)前進(jìn)行的是第i次操作.從index數(shù)組中取出第i和第i+1單元,假設(shè)其內(nèi)容分別為l和m,在從當(dāng)前運(yùn)算的染色體種群取出第l和第m條染色體分別作為母本和父本. (8) 生成兩個(gè)1N之間的隨機(jī)數(shù),分別命名為first和second,如果first大于second,則二者交換;如果二者相等,則令se

44、cond=first+1;如果二者相等且都等于N,則令first=first-1. (9) 設(shè)立兩個(gè)將緩沖數(shù)組,命名為buf1和buf2,分別將母本和父本的作業(yè)序列中第first到second的作業(yè)移入buf1和buf2. (10) 對(duì)buf1中作業(yè),按照該作業(yè)在父本作業(yè)序列中的次序,調(diào)整buf1中作業(yè)的次序,同理,對(duì)buf2中作業(yè),按照該作業(yè)在母本作業(yè)序列中的次序,調(diào)整buf2中作業(yè)的次序.如: 母本: 4 2 | 1 3 | 6 5 父本: 2 3 | 1 4 | 5 6 buf1: 1 3 buf2: 1 4 buf1中的作業(yè)3 在父本中領(lǐng)先作業(yè)1,因此按照調(diào)整父本中的作業(yè)順序進(jìn)行調(diào)整.

45、同理調(diào)整buf1. buf1: 3 1 計(jì)算機(jī)輔助生產(chǎn)線平衡與產(chǎn)能分析研究 第 14 頁(yè) 共 52 頁(yè) buf2: 4 1 (11) 用調(diào)整以后的buf1和buf2替代原母本和父本作業(yè)序列中first和second之間的作業(yè)的內(nèi)容.交換操作后的染色體為 后代1: 4 2 3 1 6 5 后代2: 2 3 4 1 5 6 (12) 跳轉(zhuǎn)到第6步,直到對(duì)種群中所有染色體均完成上述操作. 顯然,交配概率決定了每次迭代中染色體交配的對(duì)數(shù). 3.2.4.3 優(yōu)化目標(biāo)函數(shù) 優(yōu)化目標(biāo)函數(shù)確定了遺傳算法的優(yōu)化方向.不同的應(yīng)用目的有不同的目標(biāo)函數(shù).通常單一產(chǎn)品生產(chǎn)線平衡第一類問(wèn)題為給定節(jié)拍時(shí)間,希望平衡結(jié)果具有

46、最小的工作站空閑時(shí)間,即目標(biāo)函數(shù)為下式的最小化 )()(11= KkkKkikMiPctc (3-3) 式中ikt為在工作站k上完成的作業(yè)iT 的時(shí)間,kP為工作站k的負(fù)荷時(shí)間.等價(jià)于 tconsKcPKcPKcPcKkkKkkKkktan)(111= = = =(3-4) 并且有 tconscKtconsKctconsKctconsKctan)min(tan)min(tan)min()tanmin(顯然,節(jié)拍時(shí)間一經(jīng)給定即為常數(shù),因此最小空閑時(shí)間等價(jià)于最小工作站數(shù)量.對(duì)于第二類問(wèn)題,給定工作站數(shù)量,求最小化節(jié)拍時(shí)間,根據(jù)上式,其目標(biāo)函數(shù)是等價(jià)的.文獻(xiàn)3提出了三種優(yōu)化目標(biāo)函數(shù)形式,即 =Kki

47、kMitKcf11 (3-5) KctfKkMiik212)( = (3-6) 313fbaff+= (3-7) 本設(shè)計(jì)采用了1f作為優(yōu)化目標(biāo)函數(shù),但是同時(shí)計(jì)算了2f數(shù)值和KctKkikMi=1作為平衡結(jié)果數(shù)據(jù)提交,由用戶判斷優(yōu)劣,其中,對(duì)一批方案中的2f進(jìn)行了比較,并將2f最小的方案稱為最優(yōu)方案,將2f最大的方案稱為最差方案. 3.2.4.4 優(yōu)化目標(biāo)函數(shù)轉(zhuǎn)換為適應(yīng)度函數(shù)的算法 基因算法要求適應(yīng)度大的染色體具有較大的生存概率,因此隱含了最大值優(yōu)化原則.而生產(chǎn)線平衡算法普遍是目標(biāo)函數(shù)的最小值優(yōu)化,因此需要建立優(yōu)化目標(biāo)函數(shù)到適應(yīng)度函數(shù)的數(shù)學(xué)變換.本設(shè)計(jì)采用的線性變換方法,設(shè)種群中的染色體數(shù)為N,

48、計(jì)算機(jī)輔助生產(chǎn)線平衡與產(chǎn)能分析研究 第 15 頁(yè) 共 52 頁(yè) ,.,2,1)(Nkkf=第k個(gè)染色體的優(yōu)化目標(biāo)函數(shù)值.為每一染色體計(jì)算 =Nkkfkfkg1)()()( (3-8) 顯然,1)(0kg. 定義染色體的適應(yīng)度為 = =NkkfkfkgkA1)()(1)(1)( (3-9) 這實(shí)際上是在0,1區(qū)間上的累積概率分布函數(shù),所有染色體的優(yōu)化目標(biāo)函數(shù)值,.,2,1)(Nkkf=轉(zhuǎn)換為0,1區(qū)間上的一段區(qū)間,染色體的優(yōu)化目標(biāo)函數(shù)值越小,其所占據(jù)的區(qū)間相對(duì)越大,在利用輪盤(pán)賭算法抽取下一代種群的母本和父本,就具有較大的幾率.從而在迭代計(jì)算中,實(shí)現(xiàn)逐步尋優(yōu)的目的. 3.2.5 ALB2型問(wèn)題遺傳算法設(shè)計(jì) ALB2型問(wèn)題與ALB1型問(wèn)題的不同之處在于他們的求解目標(biāo)和求解條件正好相反.ALB2是給定工作站數(shù)K,要求找到一種最優(yōu)的作業(yè)分配方案使節(jié)拍時(shí)間最小.根據(jù)2.3中講述的基本思路,我們從最小生產(chǎn)節(jié)拍1NiitK=開(kāi)始進(jìn)行迭代,使用3.2中介紹的ALB1型平衡遺傳算法進(jìn)行計(jì)算,如果得到的平衡方案工作站數(shù)小于或等于K,則結(jié)束計(jì)算過(guò)程.否則,將生產(chǎn)節(jié)拍延長(zhǎng)一個(gè)固定值,在進(jìn)行計(jì)算,直到滿足工作站數(shù)K的要求為止. 3.3 混合產(chǎn)品生產(chǎn)線平衡算法 3.3.1 由多個(gè)產(chǎn)品緊后作業(yè)集合構(gòu)造混合生產(chǎn)線先后關(guān)系矩陣 由多個(gè)產(chǎn)品的緊后作業(yè)集合構(gòu)造