啟發(fā)式求解大規(guī)模流水調(diào)度問(wèn)題.pdf

1、大規(guī)模Flow shop調(diào)度是一個(gè)重要的制造加工系統(tǒng)中的核心問(wèn)題，廣泛應(yīng)用于工業(yè)環(huán)境中。大規(guī)模流水調(diào)度是很多實(shí)際流水線生產(chǎn)調(diào)度問(wèn)題的簡(jiǎn)化模型，也是一類典型的NP完全問(wèn)題，己被證明在多項(xiàng)式時(shí)間內(nèi)得不到最優(yōu)值。該問(wèn)題也是生產(chǎn)管理中的核心問(wèn)題，好的求解方法可以促進(jìn)企業(yè)提高生產(chǎn)率。因此，對(duì)于該問(wèn)題的研究從理論到實(shí)踐都有重要意義。近年來(lái)，對(duì)于流水調(diào)度問(wèn)題的求解主要有啟發(fā)式算法和元啟發(fā)式算法，但各有其不足之處：元啟發(fā)式方法的運(yùn)行時(shí)間長(zhǎng)，可獲得較好的

2、解，但其解不穩(wěn)定；啟發(fā)式方法可在較短的時(shí)間內(nèi)得到魯棒性較強(qiáng)的解，但是極少獲得較優(yōu)的解。為了更好地解決大規(guī)模流水調(diào)度問(wèn)題，提出兩個(gè)相應(yīng)的啟發(fā)式算法，從實(shí)時(shí)性和優(yōu)解性兩個(gè)方面與現(xiàn)有的算法進(jìn)行比較，大量試驗(yàn)結(jié)果表明該方法能有效求解所考慮的大規(guī)模流水調(diào)度問(wèn)題。 首先，針對(duì)以總完工時(shí)間為優(yōu)化目標(biāo)的大規(guī)模流水作業(yè)調(diào)度問(wèn)題，提出基于局部插入和全局插入的雙插入啟發(fā)式算法DIH。DIH算法與目前求解流水調(diào)度問(wèn)題最好的啟發(fā)算法RZ、WY、FL在15

3、00個(gè)實(shí)例上進(jìn)行比較。試驗(yàn)表明，DIH算法具有最好的性能，并且能夠滿足大規(guī)模調(diào)度對(duì)于實(shí)時(shí)性和優(yōu)解性的要求。 其次，提出復(fù)合啟發(fā)式算法CDIH求解最優(yōu)化總完工時(shí)間的大規(guī)模流水調(diào)度問(wèn)題。在CDIH算法中，將DIH算法的調(diào)度結(jié)果通過(guò)全局插入和工件交換操作進(jìn)行二次改進(jìn)。通過(guò)4000個(gè)不同規(guī)模實(shí)例將CDIH算法與目前最好的復(fù)合啟發(fā)式算法IH7、FL-IH7在ARPD、STD、OPT和計(jì)算時(shí)間等參數(shù)方面進(jìn)行比較，試驗(yàn)結(jié)果表明：在最好調(diào)度的獲