求解JOB-SHOP車間作業(yè)調(diào)度的混合算法研究.pdf

1、作業(yè)車間調(diào)度問(wèn)題（JSP）是一類滿足任務(wù)配置和順序約束要求的資源分配問(wèn)題，是最困難的組合優(yōu)化問(wèn)題之一。有效的生產(chǎn)調(diào)度方法和優(yōu)化技術(shù)的研究和應(yīng)用是實(shí)現(xiàn)先進(jìn)制造和提高生產(chǎn)效益的基礎(chǔ)和關(guān)鍵。求解的方法以啟發(fā)式算法為主，基于優(yōu)先權(quán)規(guī)則，即從未排序的工序特定子集中選用工序的規(guī)則。 本文鑒于精確方法僅適合于小規(guī)模問(wèn)題，以混合算法來(lái)求解Job-shop調(diào)度問(wèn)題。主要工作如下：首先，通過(guò)對(duì)國(guó)內(nèi)外作業(yè)車間調(diào)度問(wèn)題的研究，介紹了已有的求解Job-s

2、hop調(diào)度問(wèn)題的各種算法。其次，在闡述遺傳算法基本概念、原理、方法的基礎(chǔ)上，針對(duì)普通遺傳算法在求解Job-shop調(diào)度問(wèn)題時(shí)，存在著收斂速度慢和易出現(xiàn)“早熟”現(xiàn)象的缺點(diǎn)，提出算法混合思想。接下來(lái)分析了遺傳算法和禁忌搜索算法及蟻群算法的優(yōu)缺點(diǎn)，遺傳算法能以較大概率找到全局最優(yōu)，但局部搜索能力不強(qiáng)，對(duì)車間調(diào)度系統(tǒng)進(jìn)行優(yōu)化時(shí)需較長(zhǎng)時(shí)間。禁忌搜索算法收斂較快，局部搜索能力強(qiáng)，但其收斂性和初值的選擇有很大關(guān)系。蟻群算法的正反饋和并行搜索特點(diǎn)提高解

3、的質(zhì)量和穩(wěn)定性，但算法時(shí)間長(zhǎng)，且容易陷入局部最優(yōu)解。本文提出了作業(yè)車間調(diào)度的混合算法。經(jīng)過(guò)多次試驗(yàn)，發(fā)現(xiàn)在遺傳算法完成后，直接選用遺傳算法得到的最優(yōu)解作為禁忌搜索的初始解進(jìn)行計(jì)算得到的最終解和用遺傳算法所得到的最終解相差無(wú)幾，但平均進(jìn)化代數(shù)減少，避免了遺傳算法的早熟收斂。對(duì)于混合蟻群遺傳算法由于遺傳算法具有快速隨機(jī)的全局搜索能力，但對(duì)于系統(tǒng)中的反饋信息利用卻無(wú)能為力，當(dāng)求解到一定范圍時(shí)往往做大量無(wú)為的冗余迭代，求精確解效率低，螞蟻算法是