求解柔性作業車間調度問題的細菌算法對比及改進

吳秀麗， 張志強

(北京科技大學 機械工程學院，北京 100083)

0 引言

生產調度對于提高制造企業運作效率、降低成本具有舉足輕重的作用，該問題也是典型的優化難題，吸引了眾多學者開展研究.近年來，Brukcer等[1]提出了柔性作業車間調度問題(flexible job shop scheduling problem, FJSP).FJSP包含兩個子問題：路由問題和調度問題，分別表示工序的機器分配問題和調度問題.FJSP將機器柔性引入傳統job-shop調度模型，更接近于實際生產調度環境，增加了調度靈活性，但問題復雜度也相應增加，傳統數學方法難以在有限時間內求解，因此眾多學者采用智能優化算法研究該問題[2-3].

細菌算法作為一個較為新穎的算法，受到了學者的廣泛關注.細菌算法都是基于細菌的生物特性來實現的:其一是基于細菌覓食過程;其二是基于細菌進化過程.前者由于對細菌覓食過程的拆解和側重，衍生出一系列其它算法，如細菌趨化算法、細菌群體趨化算法、細菌群游算法和細菌覓食算法等；后者發展出細菌進化算法.

細菌趨化算法最初由Bremermann等[4]提出，后經Müller等[5-6]進一步地研究與綜合，提出了細菌趨化(bacterial chemotaxis, BC)算法.該算法是優化領域的一種新的仿生學進化算法，其利用細菌對環境中引誘劑的應激反應行為來進行函數優化.國內最早研究BC算法的是李威武等[7]，他提出細菌群體趨藥性算法(bacterial colony chemotaxis, BCC).細菌覓食優化算法(bacterial foraging optimization algorithm, BFO)最初由Passino[8]2002年提出，借鑒了大腸桿菌在覓食過程中的趨化、群聚、繁殖和消除-擴散等運動特性，設計了優化算法.在此基礎上，Tang等[9]提……