基于分解策略處理Job shop調(diào)度問(wèn)題的兩種方法.pdf

1、作業(yè)車間調(diào)度問(wèn)題(Job Shop Scheduling Problem，JSSP)被認(rèn)為是一種困難的組合最優(yōu)化問(wèn)題之一，它的復(fù)雜性主要體現(xiàn)在其計(jì)算的難處理性和動(dòng)態(tài)不確定性，由于人們找不到處理這類復(fù)雜問(wèn)題的精確優(yōu)化算法，因此用啟發(fā)式算法求解成為當(dāng)今研究這類問(wèn)題的重點(diǎn)。 分解策略作為一種啟發(fā)式方法，能夠有效的降低問(wèn)題的復(fù)雜性。將調(diào)度問(wèn)題分為兩層，上層考慮各子問(wèn)題之間的約束關(guān)系，下層考慮各子問(wèn)題內(nèi)的約束關(guān)系，實(shí)際的調(diào)度發(fā)生在下層，再

2、考慮上層中的約束關(guān)系，使得到的調(diào)度解可行。 本文給出了處理一類典型Job shop調(diào)度問(wèn)題的基于分解策略的兩種方法：一種是滾動(dòng)時(shí)域方法并給出其改進(jìn)，另一種是基于移動(dòng)瓶頸的禁忌搜索方法。歸納起來(lái)，本文主要做了以下幾方面的工作： 簡(jiǎn)單介紹了車間調(diào)度問(wèn)題的分類和特點(diǎn)、研究現(xiàn)狀及方法以及研究方法存在的缺陷和解決思路； 對(duì)于一種滾動(dòng)時(shí)域方法，給出了它的改進(jìn)算法，分別給出這兩種算法的仿真結(jié)果，并對(duì)這兩種算法做出比較。由于調(diào)度