求解Job-shop調(diào)度問題的混合遺傳算法.pdf

1、作業(yè)車間調(diào)度問題(Job Shop Scheduling Problem,JSSP)是一類滿足任務(wù)配置和順序約束要求的資源分配問題,是最困難的組合優(yōu)化問題之一.鑒于精確方法僅適合于小規(guī)模問題,構(gòu)造性方法優(yōu)化質(zhì)量較差且缺少柔性,本文以混合遺傳算法(Genetic Algorithm,GA)來求解Job-shop調(diào)度問題.主要工作如下:首先,通過對(duì)國內(nèi)外作業(yè)車間調(diào)度問題的研究,介紹了已有的求解Job-shop調(diào)度問題的各種算法,確定以遺傳算

2、法為主要的研究手段.其次,在闡述遺傳算法基本概念、原理、方法的基礎(chǔ)上,針對(duì)普通遺傳算法在求解Job-shop調(diào)度問題時(shí),存在著收斂速度慢或易出現(xiàn)"早熟"現(xiàn)象的缺點(diǎn),本文提出了一種將禁忌搜索思想與遺傳算法相結(jié)合的混合遺傳算法.在新算法中,一方面,在選擇操作中利用禁忌表的變化來選擇產(chǎn)生新種群中的個(gè)體.另一方面,對(duì)經(jīng)過遺傳算法的交叉和變異操作產(chǎn)生的后代種群中的個(gè)體進(jìn)行禁忌搜索操作,從而,加快了新算法的收斂速度.最后通過對(duì)標(biāo)準(zhǔn)作業(yè)車間調(diào)度問題(