求解一類訂單調度問題的遺傳算法研究.pdf

1、訂單調度問題可以簡單描述為：每個訂單包括k(k≤m)種不同的作業(yè)，每臺機器能且只能加工某一特定的作業(yè)，每個訂單的作業(yè)必須連續(xù)加工直至完成，每個訂單的完成時間是訂單中所有作業(yè)的最大完成時間。所以，訂單調度研究的是一組作業(yè)的整體完工情況。因為訂單調度問題類型眾多，模型復雜，并且大部分被證明為NP-hard難題，因此尋找多項式時間最優(yōu)解是不可能的。國內外眾多學者嘗試發(fā)展啟發(fā)式算法求解訂單調度問題，可以求得較優(yōu)解，而遺傳算法作為一種人工智能優(yōu)化

2、算法，具有自適應性、并行性和全局優(yōu)化的特點，所以本文嘗試將遺傳算法應用于一類訂單調度模型，研究了專門機環(huán)境下以最小化總(加權)完工時間優(yōu)化目標的訂單調度模型，并將其與啟發(fā)式算法進行性能比較。
　　 文章首先詳細地描述了訂單調度問題，建立了總完工時間和總加權完工時間情況下訂單調度問題的數學模型；然后針對這兩個數學模型的特點，完成了遺傳算法的編碼設計、適應度函數設計、遺傳算子參數的優(yōu)選、遺傳因子的基因操作等，并運用Matlab強大的