1、PowerPoint Template基于局部搜索的生產調度算法傳統算法與啟發式算法都屬于構造型算法。都是從沒有調度序列開始，每次增加一項工作來逐漸構造一個調度。改進型算法：在概念上與構造型算法完全不同，它們是從一個任意選擇出的完整的調度方案開始，然后通過改進現有的調度來嘗試獲得更好的調度。在改進型的調度中一個重要的類別就是局部搜索法。Company Logo局部搜索算法相鄰：如果一個調度可以通過定義的修改，轉化為另一個調度，那么這兩個調度就可以成為相鄰。局部搜索算法不保證會產生最優解，它通常會試著在現有調度鄰域找到一個更好的調度。每次轉化之后，局部搜索法會在鄰域之中進行搜索，評價不同的鄰域的

2、解。然后按照給定的接受拒絕原則或者接受或者拒絕一個候選的解來作為下一個調度改進的方向。局部搜索算法中目前應用于生產調度中比較廣泛的有模擬退火法（SA）、禁忌搜索法（TS）以及遺傳算法（GA） 。Company Logo模擬退火算法 模擬退火算法是用來解決復雜的組合優化問題，根據固體退火過程的模擬而得名，固體退火就是先將固體加熱至融化，再徐徐冷卻使之凝固成規則的晶體。假設存在一個解集S（所有可能解的集合）和一個目標函數f（定義在解集S上的成員的實數函數），目標是在解集S中尋找一個解使其能使目標函數值最小。模擬退火是一個迭代過程，這個過程取決于鄰域的產生。首先產生一個初始解，然后在每個溫度下產生當

3、前解的鄰域，直到滿足停止準則為止。Company Logo模擬退火算法要經過多次迭代，在第k次迭代時，會得到當前的調度 以及目前可以找到的最好的調度 。對于單機問題，這些調度是工作的次序。令 和 表示對應的目標值。目前得到的最佳調度值是 ，通常作為期望達到的標準。在搜索最優調度時，算法從一個調度移到另一個調度。在第k次迭代時，在 的鄰域中搜索新調度。首先，在鄰域中選出一個候選調度 ，如果 那么將進行一次移動，設定 。如果 那么 就被設定為 ，然而，如果 ，那么就會按照以下該概率對 進行移動：按 的概率，拒絕調度 而保留現有的調度，設定 。當調度 比調度 更優時，它不會改變。 是控制參數，用來表

4、示冷卻參數或者溫度。通常 ，其中a的值在 01之間。Company Logo模擬退火算法步驟1.設定k=1，選擇 ； 使用啟發式算法選擇初始序列 ；設定 。2. 從 的鄰域中選擇候選調度 ； 如果 ，那么設定 ，到步驟3； 如果 ，那么設定 ，到步驟3； 如果 ，那么生成服從Uniform（0，1） 分布的隨機數 ； 如果 ，那么設定 否則設 ，到步驟3.3.選擇 ；將k增加1；如果k=N，就停止，否則到步驟2. Company Logo禁忌搜索算法（TS）禁忌搜索算法是一種迭代方法，它開始于一個初始可行解S，然后移動到鄰域N（S）中最好的解 ， 即 對于目標函數 在鄰域N（S）中是最優的。然

5、后從新的開始點重復此方法。為了避免死循環，禁忌搜索把最近的T個移動放在一個禁忌表中，在目前的迭代中這些移動是被禁止的，在一定數目的迭代之后它們又被釋放出來。這樣的禁忌表是一個循環表，它被循環的修改，其長度T是事前自己設定的一個值。最后通過定義一個停止準則來終止整個算法。Company Logo序列 4，2，1，3 2，1，4，3 2，4，3，1 460 500 608 可以看出第二次移動是被禁忌的，然而，第一次移動要比第二次優化。第一次移動產生的調度比目前為止最好的調度要差，最好的調度就是當前這個，所以它是個局部極小值。依然選 ，禁忌表被更新包含（2，4），（1，4）。 鄰居對應的目標函數值為

6、序列 2，4，1，3 4，1，2，3 4，2，3，1 436 440 632 現在盡管最好的移動是移動到2，4，1，3（ ），但是這個移動是被禁止的，因而， 被選定為4，1，2，3.更新禁忌表，得到（1，2），（2，4），而條目（1，4）就會從禁忌表中刪除掉，因為表的長度要保持為2. 鄰居對應的目標函數值為：Company Logo 序列 1，4，2，3 4，2，1，3 4，1，3，2 408 460 586 調度4，2，1，3是被禁忌的，但是最好的移動是移動到調度1，4，2，3.所以 ，對應的目標函數值比期望得到的標準要好。所以期望得到的標準變為408.禁忌表更新，增加（1，4）而去掉（2，4）。從而得到全局最小值。即為利用禁忌搜索方法得到的調度。 Company Logo遺傳算法基于遺傳算法的調度是將序列或者調度看成個體或是種群的成員，每個個體以其適應度為特征。個體的適應度由對應的目標函數值來衡量。過程反復進行，每次迭代稱為一代。種群的一代包含從上一代存活下來的個體和從上一代得到的新調度或者說是子代。從一代到下一代，種群的大小通常保持不變，通過將上一代的部分個體進行復制和變異而產生子代。個體有時也被稱為染色體。在多機環境下，一條染色體可以由子染色體組成，每個子染色體包含著關于工作序列在一臺機器上的信息。上一代染色