- 相關(guān)推薦
應(yīng)用遺傳算法解決車(chē)間作業(yè)調(diào)度問(wèn)題
應(yīng)用遺傳算法解決車(chē)間作業(yè)調(diào)度問(wèn)題
摘要
車(chē)間調(diào)度問(wèn)題簡(jiǎn)單來(lái)說(shuō)就是設(shè)備資源優(yōu)化配置問(wèn)題。近年來(lái)遺傳算法得到了很大的發(fā)展，應(yīng)用遺傳算法來(lái)解決車(chē)間調(diào)度問(wèn)題早有研究。本文在已有算法基礎(chǔ)上詳細(xì)討論了染色體編碼方法并對(duì)其進(jìn)行了改進(jìn)。最后根據(jù)改進(jìn)的編碼進(jìn)行遺傳算法的設(shè)計(jì)，本文提出了1種求解車(chē)間作業(yè)調(diào)度問(wèn)題的改進(jìn)的遺傳算法，并給出仿真算例表明了該算法的有效性。
關(guān)鍵詞：車(chē)間作業(yè)調(diào)度;遺傳算法;改進(jìn)遺傳算法染色體編碼
Genetic algorithms for Job Shop Scheduling Problem
Abstract
simply speaking, the job shop scheduling problem is the equipment resources optimization question. In recent years, the genetic algorithms obtained great development, it was used to solve the job shop scheduling problem early. This paper discusses the chromosome code method in detail based on the genetic algorithms and make the improvement on it. In the end, according to the code which improved carries on the genetic algorithms design, this paper offer one improved genetic algorithms about soloving to the job shop scheduling problem, and the simulated example has indicated that this algorithm is valid.
Key words: job shop scheduling ;genetic algorithms ; Improvement genetic algorithms chromosome code
前言
隨著社會(huì)不斷向前發(fā)展，競(jìng)爭(zhēng)的加劇，制造業(yè)中普遍面臨的許多問(wèn)題不斷地突現(xiàn)出來(lái)。如何在有限的生產(chǎn)資料條件下，以最短的生產(chǎn)周期、最小的成本將產(chǎn)品制造出來(lái)以滿(mǎn)足客戶(hù)的需求是每1個(gè)制造商不斷追求的目標(biāo)。如何運(yùn)用有限的資源，降低產(chǎn)品的生產(chǎn)成本，縮短產(chǎn)品的制造周期，保證按時(shí)交貨，提高企業(yè)信譽(yù)，贏得更多的客戶(hù)，成為制造廠商在競(jìng)爭(zhēng)中生存的1個(gè)重要的條件。有效的利用現(xiàn)有的資源，合理的制定企業(yè)和車(chē)間生產(chǎn)計(jì)劃，是達(dá)到這個(gè)目標(biāo)的關(guān)鍵。
由于車(chē)間調(diào)度問(wèn)題不僅是1個(gè)典型的NP難題，也是至今為止所有組合優(yōu)化問(wèn)題中最難問(wèn)題之1，所以得到了廣泛的關(guān)注。早在20世紀(jì)50年代早期就有很多關(guān)于調(diào)度問(wèn)題的研究文獻(xiàn)。在計(jì)算機(jī)出現(xiàn)以前，作業(yè)車(chē)間調(diào)度問(wèn)題(Job Shop Scheduling Problem，簡(jiǎn)稱(chēng)為JSSP或JSS問(wèn)題)是用手工計(jì)算完成的。但是由于問(wèn)題本身復(fù)雜、計(jì)算量大，手工操作可靠性差、調(diào)度方案優(yōu)化性能不好，跟不上產(chǎn)品的多變性要求又容易受隨機(jī)因素的干擾，使資源和生產(chǎn)能力得不到充分的發(fā)揮和利用，生產(chǎn)車(chē)間效率不高。即使隨著計(jì)算機(jī)的出現(xiàn)和發(fā)展，調(diào)度問(wèn)題也沒(méi)有得到很好的解決，因?yàn)閱?wèn)題的規(guī)模和實(shí)時(shí)性要求也在不斷提高。通常用于求解JSSP的技術(shù)與方法主要分為兩類(lèi)，1類(lèi)是近似求解方法，1類(lèi)是最優(yōu)化求解方法。用近似方法求解時(shí)，可以很快地得到問(wèn)題的解，但它們不能保證所得到的解是最優(yōu)的；用最優(yōu)化方法求解這1問(wèn)題時(shí)，它們可以得到全局最優(yōu)解，但它們只能解決小規(guī)模的，而且速度很慢。
鑒于JSSP在實(shí)際應(yīng)用中的重要地位，論文的具體安排如下:
第1：本文將對(duì)車(chē)間作業(yè)調(diào)度問(wèn)題的基本概念、數(shù)學(xué)模型、表示方法及其基本理論進(jìn)行闡述。在深入對(duì)問(wèn)題進(jìn)行剖析的基礎(chǔ)上，借鑒自然進(jìn)化思想機(jī)理，對(duì)JSSP的求解問(wèn)題進(jìn)行探索性研究。旨在為求解JSSP問(wèn)題提供新的解決思路。而本文主要的研究重點(diǎn)放在基本遺傳算法，求解JSSP的研究上的編碼問(wèn)題。同時(shí)給出以最小化生產(chǎn)周期(minimum makespan)為目標(biāo)函數(shù)的問(wèn)題JSSP模型，并還給出了關(guān)于問(wèn)題的復(fù)雜性描述。
第2：對(duì)遺傳算法在JSSP應(yīng)用中的編碼問(wèn)題、解碼問(wèn)題以及JSSP的遺傳算子設(shè)計(jì)進(jìn)行了深入的分析，參照了西安電子科技大學(xué)姜迪剛，葉尚輝共同編寫(xiě)的論文《基于遺傳算法的車(chē)間調(diào)度作業(yè)》，針對(duì)1個(gè)生產(chǎn)周期最小化的優(yōu)化目標(biāo)進(jìn)行實(shí)現(xiàn)。
最后，對(duì)本文進(jìn)行了總結(jié)并對(duì)以后的研究工作給出了1些建議和展望。
【應(yīng)用遺傳算法解決車(chē)間作業(yè)調(diào)度問(wèn)題】相關(guān)文章：
公交車(chē)調(diào)度問(wèn)題的數(shù)學(xué)模型05-11
歷史性遺留婚姻問(wèn)題的解決05-31
分析論文答辯中遇到的問(wèn)題及解決對(duì)策05-31
淺談企業(yè)績(jī)效管理的現(xiàn)狀、問(wèn)題及解決對(duì)策09-16
建筑施工管理中存在的問(wèn)題及解決措施（精選10篇）05-12
法學(xué)雙語(yǔ)教學(xué)中存在的問(wèn)題及解決途徑教育論文08-06
無(wú)機(jī)化學(xué)實(shí)驗(yàn)中存在的問(wèn)題及解決措施12-05
礦山測(cè)量?jī)x器安全管理問(wèn)題的解決措施論文04-22