附件C
對于搶先與非搶先型車間調(diào)度問題具有模糊邏輯控制的遺傳算法

摘要

在本文中，我們將要提出一種新的基因遺傳算法——模糊邏輯控（ＦＬＣ）制來解決搶先的車間調(diào)度問題（Ｐ－ＪＳＰ）與非搶先的車間調(diào)度問題（ＮＰ－ＪＳＰ）。提出的算法考慮到了在單一機(jī)床加工計(jì)劃中的先決要素。在各類先決要素中，我們先做一個(gè)限制性規(guī)劃，接著用所提出的遺傳算法演化出一種新的基因表達(dá)方法，基因交換和基因突變。但是提出的算法與傳統(tǒng)的遺傳算法具有相同的弱點(diǎn)，在基因參數(shù)的初始化上將會(huì)花費(fèi)大量的時(shí)間，ＦＬＣ可以用來調(diào)節(jié)參數(shù)。
在本文中，ＦＬＣ將會(huì)適當(dāng)?shù)卣{(diào)節(jié)基因的交換率和突變率。為了證明ＰＬＣ的作用，在本文中我們將會(huì)把提出的算法分兩部分進(jìn)行：一部分具有模糊邏輯控制的遺傳算法（ＰＲＯ－ＦＧＡ），另一部分不具有模糊邏輯控制的遺傳算法（ＰＲＯ－ＧＡ）。
在眾多的的實(shí)例中，我們將會(huì)把提出的算法應(yīng)用到各類車間調(diào)度問題之中，并將獲得的結(jié)果一同進(jìn)行分析和比較。各種實(shí)驗(yàn)將會(huì)展現(xiàn)出ＰＲＯ－ＦＧＡ與ＰＲＯ－ＧＡ作用的不同結(jié)果。
關(guān)鍵詞：搶先的車間調(diào)度；非搶先的車間調(diào)度；遺傳算法；模糊邏輯控制

1.引言

本文考慮了在車間調(diào)度問題（ＪＳＰ）中各類活動(dòng)中的搶先因素。在搶先車間調(diào)度問題中（Ｐ－ＪＳＰ），每一個(gè)加工作業(yè)都是由一系列的工序組成，每個(gè)工序都是在指定的機(jī)器上，在給定的時(shí)間內(nèi)完成。每個(gè)工序都可以在任何時(shí)間被其他工序所中斷，并且沒有中斷的次數(shù)和時(shí)間限制。但是，在非搶先車間調(diào)度問題中，工序不能被中斷，每個(gè)工序自開始到結(jié)束前都不能被中止。因此，我們?nèi)粢瑫r(shí)考慮并比較這兩種類型的調(diào)度問題的話，就必須采用不同的限制條件。
Ｐ－ＪＳＰ問題在學(xué)術(shù)界和現(xiàn)實(shí)世界中很少受到關(guān)注，Applegate與Cook（１９９１）對Ｐ－ＪＳＰ型問題進(jìn)行了多種計(jì)算研究，并用１０?。剩樱邪l(fā)布了一些關(guān)于搶先與非搶先要素的標(biāo)準(zhǔn)化程序。Lee and Takagi(1993), Xu and Vukovich (1994) and Zeng and Rabenasolo (1997). Zeng and Rabenasolo (1995)考慮了關(guān)于P-JSP與NP-JSP資源系統(tǒng)參數(shù)，他提出了一些關(guān)于處理搶先要素與比較各類P-JSP問題的限制性程序的構(gòu)思。S and Baptiste (1994, 1997)在程序庫中通過約束程序提出了關(guān)于P-JSP與NP-JSP的約束繁殖技術(shù)。Baptiste(1999)在單一機(jī)器搶先調(diào)度中提出了一種O(n4)算法使加工延遲時(shí)間最小化。
P-JSP問題在遺傳算法中很少受到研究人員的關(guān)注。主要是因?yàn)樵撍惴ㄔ谶z傳算法中很難，并且會(huì)花大量的時(shí)間來尋找優(yōu)的結(jié)構(gòu)化參數(shù)。
對于GA參數(shù)，F(xiàn)LC具有很重要最的作用。研究人員可以用flc來適當(dāng)?shù)毓芾鞧A參數(shù)（遺傳的代數(shù)，種群大小，交換率，突變率及其他）。因此，可以節(jié)省大量的用于參數(shù)調(diào)節(jié)的時(shí)間并且GA在全局最適應(yīng)參數(shù)的搜索能力能得到改進(jìn)。Gen和Cheng建議在GA領(lǐng)域使用FLC。最早在擴(kuò)充模糊方面對 GA 的策略叁數(shù)的適合的規(guī)則邏輯技術(shù)的是Lee，Takagi(1993), Xu .Vukovich(1994)，Zeng和Rabenasolo(1997). Zeng和Rabenasolo用FLC來調(diào)節(jié)GA中的交換率，突變率與基因交換的位置。這些參數(shù)被考慮為GA輸入多樣性和FLC的輸出多樣性。Wang和Hu使用兩種FLC：一個(gè)用于控制交換率另一個(gè)用于突變率。由于FLC的貢獻(xiàn)，近來的GA算法比傳統(tǒng)的GA算法更強(qiáng)健。
本文將著重于改良一種有效GA算法用于解決在單一機(jī)器加工中的P-JSP和NP-JSP問題。提出的算法考慮了一些限制性得到了用于考慮在加工活動(dòng)中搶先要素的限制性程序的發(fā)展改良，并且使用FLC來適當(dāng)調(diào)節(jié)GA參數(shù)。
在第二部分，這種限制性程序用于考慮各種活動(dòng)中的搶先要素被提出，用于解決P-JSP和NP-JSP也被提出。遺傳算法中新的關(guān)于P-JSP和NP-JSP的有效描述的理念在第三節(jié)中得以提出。微量調(diào)節(jié)GA算法中的參數(shù)的觀點(diǎn)在第四節(jié)中提出。所有所提出算法的過程程序在第五節(jié)中展示。各種實(shí)例和演示在第六節(jié)中提出，并在第七節(jié)中作出總結(jié)。