利用遺傳算法求解作業(yè)調(diào)度問(wèn)題.pdf

1、作業(yè)調(diào)度問(wèn)題是一個(gè)被廣泛認(rèn)可的在實(shí)踐中所遇到的最難解決的NP完全問(wèn)題之一，對(duì)作業(yè)調(diào)度問(wèn)題解法的研究不僅對(duì)于制造業(yè)有特殊的意義，而且對(duì)所有NP完全問(wèn)題的解法都有普遍的借鑒意義。 全文共分為四章。第一章概述了當(dāng)前制造業(yè)的現(xiàn)狀，引出車(chē)間作業(yè)調(diào)度問(wèn)題在計(jì)算機(jī)集成制造系統(tǒng)中的重要地位以及研究它的重要性。 第二章簡(jiǎn)述了什么是計(jì)算機(jī)算法理論中的NP完全問(wèn)題，它既是難于解決的困難問(wèn)題，又是我們要面對(duì)不能回避的問(wèn)題，只能想辦法解決它。如果

2、采用傳統(tǒng)的算法在目前的計(jì)算機(jī)系統(tǒng)中運(yùn)行所花費(fèi)的時(shí)間是指數(shù)級(jí)的，是不現(xiàn)實(shí)的，因此在改變不了硬件的情況下，只能通過(guò)尋求一種新的算法來(lái)解決此類(lèi)問(wèn)題。 第三章介紹了現(xiàn)代優(yōu)化算法之一的遺傳算法，它是借鑒生物界自然選擇和進(jìn)化機(jī)制發(fā)展起來(lái)的高度并行性、隨機(jī)、自適應(yīng)搜索算法。文章通過(guò)對(duì)遺傳算法的思想、操作原理的分析得出遺傳算法不同于傳統(tǒng)搜索方法的突出特點(diǎn)是：全局性、并行性。即在全局范圍內(nèi)進(jìn)行的快速搜索，滿(mǎn)足終止條件后停止，得到一個(gè)最終解。雖然這

3、個(gè)解并不是精確解，也不一定是最優(yōu)解，但是卻在有限的時(shí)間內(nèi)，在全局范圍內(nèi)做了大量的、快速的、隨機(jī)性的搜索，這個(gè)結(jié)果對(duì)實(shí)際問(wèn)題的解決還是有意義的。 第四章以作業(yè)調(diào)度問(wèn)題為例，闡述了用遺傳算法求解的過(guò)程。包括如何建立作業(yè)調(diào)度問(wèn)題的數(shù)學(xué)模型、如何確定適應(yīng)度函數(shù)、如何用POX交叉算子完成交叉操作、如何完成變異操作等。最后，通過(guò)VisualC++環(huán)境，實(shí)現(xiàn)了仿真程序，并通過(guò)對(duì)比，說(shuō)明了用遺傳算法求解作業(yè)調(diào)度問(wèn)題的有效性。 在總結(jié)中指