作業(yè)車(chē)間調度問(wèn)題（Job-shop Scheduling Problem, JSP)，該問(wèn)題中，一組機器需處理一組工件，每個(gè)工件由一系列具有先后順序約束的工序形成，每個(gè)工序只需要一臺機器，機器一直可用，可以一次處理一個(gè)操作而不會(huì )中斷。決策內容包括如何對機器上的工序進(jìn)行排序，已優(yōu)化給定的性能指標。 JSP的典型性能指標是完工時(shí)間 (makespan)，即完成所有工作所需的時(shí)間。 JSP是一個(gè)眾所周知的NP難題。
JSP比傳統的JSP更難，因為它引入了除了排序之外的另一個(gè)決策內容，即作業(yè)路徑。確定作業(yè)路徑意味著(zhù)為每個(gè)工序決定使用哪臺機器處理它。FJSP可被定義為：
圖1
舉例2
圖2
柔性作業(yè)車(chē)間調度問(wèn)題 (FJSSP)是組合優(yōu)化和生產(chǎn)管理領(lǐng)域很重要的研究課題，它是經(jīng)典的作業(yè)車(chē)間調度問(wèn)題 (JSSP)的延伸且被認為是強NP-hard問(wèn)題。在FJSSP中，同一個(gè)工序的加工機器可能有多臺。FJSSP由兩個(gè)子問(wèn)題組成，第一個(gè)子問(wèn)題是將一系列可選的機器分配給指定的工序，第二個(gè)子問(wèn)題是計算分配給指定機器的工序序列的完工時(shí)間。雖然比JSSP僅多了一個(gè)將一系列可選機器分配給指定工序的步驟，但是為解決FJSSP在染色體編碼、解碼、交叉和變異方面要做出相當大的改進(jìn)，因此，解決FJSSP的難度要大得多。
相比每道工序被特定的某臺機器加工的JSSP，FJSSP的任務(wù)分配要更具挑戰性，它的每道工序的加工機器可能有不止一臺可供選擇，在本文中FJSSP由以下元素組成：
工件集：J={J1,J2,J3,… … …,Jn}是要被排程的大小為n的獨立工件集，每個(gè)工件Ji由一系列按順序依次加工的工序{Oi1,Oi2,Oi3,… … …,Oin}組成，所有的工件在時(shí)刻0都是可以被加工的。
機器集：M={M1,M2,… … …,Mm}是大小為m的機器集合，每個(gè)機器僅可以一次加工一個(gè)工件，所有機器在時(shí)刻0是可以加工工件的。
柔性：通常FJSSP的柔性可以分成如下兩類(lèi)，每道工序可以被m臺機器中任意一臺加工的整體柔性和每道工序可以被m臺機器的一個(gè)子集中的任意一臺機器加工的部分柔性。
對FJSSP的其它假設：每道工序每次只可以被一臺機器加工；每道工序的處理時(shí)間因機器而異且不同的機器是相互獨立的；每道加工工序是不可中斷的；加工某工件的機器準備時(shí)間已被考慮在相應的加工時(shí)間里；工件在不同機器間的轉移時(shí)間已被考慮在加工時(shí)間里。
目標：針對實(shí)際的生產(chǎn)需要，這里考慮的是最基礎、最典型的最大完工時(shí)間這一性能指標Cmax(Makespan)。FJSSP的目標是將每個(gè)工件分配到某臺合適的機器上進(jìn)行加工并對機器的加工序列進(jìn)行排程以使得完成所有工件加工任務(wù)的最大完工時(shí)間Cmax最小。對n個(gè)工件、m臺機器的柔性作業(yè)調度問(wèn)題，設Ci是工件Ji的完工時(shí)間，求最大完工時(shí)間Cmax最小值的目標函數為
Cmax = min {max Ci, i=1,…n}
遺傳算法是一種解決大規模計算問(wèn)題的全局搜索方法，它是受自然界中生物進(jìn)化的啟發(fā)而提出的。通常，被解決問(wèn)題的一個(gè)解被稱(chēng)作一條染色體或一個(gè)個(gè)體，每個(gè)個(gè)體都有自己的適應度值。通過(guò)全局搜索(GS)、局部搜索(LS)相結合的方式來(lái)生成初始種群的大部分個(gè)體，再通過(guò)隨機搜索(RS)來(lái)生成部分個(gè)體以增加種群的基因多樣性。遺傳算法以迭代的方式運行，每迭代一次代表了種群的一代。通過(guò)交叉、變異來(lái)搜索盡可能多的盡可能優(yōu)秀的解，通過(guò)適應度計算和選擇來(lái)選擇更優(yōu)秀的個(gè)體，進(jìn)而完成一代的進(jìn)化。一直重復這種搜索過(guò)程，直到在時(shí)間或求解質(zhì)量方面滿(mǎn)足給定條件為止。
Copyright © 2004-2022 深圳市華晨信息技術(shù)有限公司 版權所有 粵ICP備18059119號-3| 技術(shù)支持：快速開(kāi)發(fā)平臺