機(jī)器故障下柔性Job Shop調(diào)度研究.pdf

1、車間調(diào)度問題是制造系統(tǒng)理論研究的基礎(chǔ)問題之一，主要討論在有限的制造資源條件下將工件合理地分配到各個制造資源，并在滿足加工約束的前提下使得一個或多個目標(biāo)達(dá)到最優(yōu)。隨著社會需求快速變化，產(chǎn)品生產(chǎn)周期不斷縮短，制造業(yè)正向著多品種，小批量的方向發(fā)展，柔性已成為生產(chǎn)制造過程所追求的重要特性之一。柔性Job Shop調(diào)度問題(Flexible Job Shop Problem，F(xiàn)JSSP)由于具有加工路徑柔性的特點(diǎn)，與傳統(tǒng)的Job Shop相比更符

2、合實(shí)際的生產(chǎn)環(huán)境和要求，因而成為車間調(diào)度的一個重要的研究方向。
　　在實(shí)際生產(chǎn)環(huán)境中，往往存在許多不確定因素，機(jī)器故障就是常見的典型不確定因素，它不僅會導(dǎo)致實(shí)際生產(chǎn)結(jié)果和計劃產(chǎn)生重大偏差，而且可能打亂諸如物料配送等相關(guān)生產(chǎn)環(huán)節(jié)，對生產(chǎn)過程帶來重大影響。因此，研究機(jī)器故障下的柔性Job Shop調(diào)度對提高生產(chǎn)過程的管理和控制水平具有重要的理論和實(shí)際意義。
　　對機(jī)器故障條件下的柔性 Job Shop的調(diào)度，其目標(biāo)是盡可能降低實(shí)

3、際調(diào)度和調(diào)度計劃的偏差，從而保證產(chǎn)品按時交付。魯棒性和穩(wěn)定性是評價機(jī)器故障下柔性Job Shop調(diào)度的兩個重要指標(biāo)，和控制理論中的魯棒性和穩(wěn)定性不同，它們分別反映了整體的實(shí)際調(diào)度結(jié)果和計劃的偏差以及每個工序?qū)嶋H完成時間和計劃完成時間的偏差。因此機(jī)器故障下的柔性Job Shop調(diào)度目標(biāo)就是努力提高調(diào)度的魯棒性和穩(wěn)定性。
　　本文針對機(jī)器故障這一典型不確定因素，以提高調(diào)度的魯棒性和穩(wěn)定性為研究目標(biāo)來研究機(jī)器故障下柔性Job Shop調(diào)

4、度問題。研究工作主要從兩個方面展開：一是研究多種策略組合下的預(yù)調(diào)度和重調(diào)度方法，二是研究機(jī)器故障下重調(diào)度的博弈模型和策略。首先，針對單一策略下得到的調(diào)度策略在魯棒性和穩(wěn)定性方面的不足，將多種調(diào)度策略引入到預(yù)調(diào)度和重調(diào)度過程中。其次，從魯棒性和穩(wěn)定性之間的均衡出發(fā)，研究了基于靜態(tài)和動態(tài)博弈理論的調(diào)度模型和調(diào)度算法以尋找Nash均衡解。再次，針對基于工序完成時間不能完全反映調(diào)度的穩(wěn)定性，研究并提出新的穩(wěn)定性指標(biāo)。最后，針對3個或以上的優(yōu)化目

5、標(biāo)，研究了基于 Pareto機(jī)制的人工免疫算法尋找Nash均衡。具體的研究內(nèi)容如下：
　?。?）針對單一調(diào)度策略不能較好地保障機(jī)器故障下調(diào)度的魯棒性和穩(wěn)定性，提出了基于機(jī)器故障概率的預(yù)調(diào)度策略和右移及更改加工路徑的混合重調(diào)度策略。
　　首先假設(shè)在機(jī)器故障概率為已知的條件下，根據(jù)機(jī)器故障的概率在生成的預(yù)調(diào)度中插入適當(dāng)數(shù)量的空閑時間。其次在機(jī)器發(fā)生故障時采用右移和變換加工路徑調(diào)度策略，盡可能保證調(diào)度的魯棒性和穩(wěn)定性，最后給出了基

6、于二叉樹的右移調(diào)度算法和右移與變換加工路徑相結(jié)合的調(diào)度算法。實(shí)驗(yàn)結(jié)果表明，和單一的右移策略以及完全重調(diào)度相比，本文所提出的策略能夠得到較好的魯棒性和穩(wěn)定性。
　?。?）考慮到魯棒性和穩(wěn)定性之間的均衡性存在博弈關(guān)系，建立了基于靜態(tài)博弈的重調(diào)度模型，并給出尋找Nash均衡解的算法；考慮到可能存在多個Nash均衡和不存在Nash均衡情況，提出了尋找近似Nash均衡的方法；針對受影響工序超過2個的情況，提出多階段博弈的調(diào)度算法。
　

7、　由于調(diào)度的魯棒性和穩(wěn)定性指標(biāo)可以看成具有決策能力的實(shí)體，兩者為保持各自的最優(yōu)性能的決策過程可以看成是博弈的過程，因此運(yùn)用靜態(tài)博弈的相關(guān)理論與方法，建立了機(jī)器故障下重調(diào)度的靜態(tài)博弈模型。由于博弈雙方采用純策略，針對可能出現(xiàn)無Nash均衡解或著多個Nash均衡解的情況，提出了尋找近似Nash均衡解的方法；對于受影響工序超過兩個時策略空間的急劇膨脹的情況，提出了多階段博弈的思想。實(shí)驗(yàn)結(jié)果表明，采用靜態(tài)博弈模型能夠提高調(diào)度的魯棒性和穩(wěn)定性。<

8、br>　?。?）從博弈過程中決策有先后順序的角度出發(fā)，運(yùn)用動態(tài)博弈理論，建立了機(jī)器故障下動態(tài)博弈的重調(diào)度模型，給出了求解子博弈完美Nash均衡的算法。
　　在靜態(tài)博弈的基礎(chǔ)上進(jìn)一步考慮博弈雙方?jīng)Q策的先后順序，建立基于動態(tài)博弈的重調(diào)度模型。為求解子博弈完美Nash均衡，給出基于博弈樹的求解子博弈完美Nash均衡的算法。在生產(chǎn)過程后期發(fā)生機(jī)器故障時，采用該模型能夠得到較好的魯棒性和穩(wěn)定性。
　?。?）針對基于工件加工完成時間的穩(wěn)

9、定性指標(biāo)的不足，提出了基于工序的加工機(jī)器分配的穩(wěn)定性指標(biāo)。
　　基于工序完成時間的穩(wěn)定性指標(biāo)不能完全反映調(diào)度的穩(wěn)定性，論文從資源分配的角度出發(fā)，在已有穩(wěn)定性的基礎(chǔ)上定義了基于工序的機(jī)器分配的穩(wěn)定性指標(biāo)，增加該指標(biāo)能更加全面反映調(diào)度的穩(wěn)定性。
　　（5）針對兩個以上的調(diào)度目標(biāo)，上述尋找Nash均衡的方法不再適用，論文提出了將Nash均衡和Pareto最優(yōu)相結(jié)合的改進(jìn)的人工免疫克隆算法。
　　機(jī)器故障下對重調(diào)度的魯棒性和穩(wěn)

10、定性進(jìn)行優(yōu)化可歸結(jié)為多目標(biāo)優(yōu)化問題。當(dāng)調(diào)度目標(biāo)多于兩個時，本文將Nash均衡和Pareto機(jī)制引入到人工免疫克隆算法之中，并運(yùn)用該算法尋找Nash均衡解。仿真結(jié)果表明，對于三個目標(biāo)的調(diào)度問題，本文提出的方法能夠?qū)ふ业捷^好的Nash均衡解。
　　綜上所述，本文以提高調(diào)度的魯棒性和穩(wěn)定性為目標(biāo)，研究了對機(jī)器故障下的柔性Job Shop的預(yù)調(diào)度和重調(diào)度策略，然后從博弈的角度對該問題進(jìn)行了研究，為求解機(jī)器故障下車間調(diào)度多目標(biāo)優(yōu)化問題提供了