智能算法(GA、DBO等)求解阻塞流水車間調度問題(BFSP)

先做一個聲明：文章是由我的個人公眾號中的推送直接復制粘貼而來，因此對智能優化算法感興趣的朋友，可關注我的個人公眾號：啟發式算法討論。我會不定期在公眾號里分享不同的智能優化算法，經典的，或者是近幾年提出的新型智能優化算法，并附MATLAB代碼。

主要參考資料：

[1] 潘全科, 高亮, 李新宇. 流水車間調度及其優化算法[M]. 武漢: 華中科技大學出版社, 2013.

由于機器中間緩沖區或生產溫度的限制，使得工件加工完成后被阻塞在當前機器上，這就是阻塞流水車間調度問題(blocking flow-shop scheduling problem, BFSP)。譬如，在化學制造過程中，由于溫度的要求，當藥品在上游機器上完成后，為了保持此時的高溫,應立即離開當前的機器而轉向下游機器。但是如果下游機器處于忙的狀態，此時藥品只能被阻塞在上游機器上。圖1所示為一個3×3的BFSP的甘特圖。當工件2在第一臺機器上加工完畢時，機器2正在加工工件1。由于沒有中間緩沖區，工件2工并不能立刻離開該機器，而是等到工件1加工完畢后才運輸到機器2上加工。這樣就造成了工件3延遲開工。

圖片

圖1 阻塞流水車間調度問題

01
問題描述

這里主要討論以最大完工時間(Cmax)為優化目標的阻塞流水車間調度問題(blocking flow-shop scheduling problem, BFSP)，記為Fm|blocking|Cmax。研究表明，m≥3時，這類調度問題也是NP-Hard 問題。

Fm|blocking|Cmax問題可描述為：有n個工件按照相同的工藝路線在m臺機器上加工。約定所有機器上工件的加工次序都相同。要求相鄰機器之間沒有緩沖區。也就是說工件j在機器i上完成后，如果下一臺機器i+1正在使用，那么工件j將被阻塞在機器i上，直到第i+1個機器空閑出來。一個工件不能同時由多臺機器加工，一臺機器也不能同時加工多個工件。已知工件在各機器上的加工時間。問題是如何安排各工件的生產次序，使得最大完成時間最小。

02
數學模型

（以下內容截自推文開頭提到的參考書籍，潘老師的那本書。）

圖片

圖片

03
加工性能指標計算

最大完成時間(Cmax)是研究阻塞流水車間調度問題最常用的加工性能指標。Cmax通常有三種計算方法：前向計算法、反向計算法和雙向計算法。

這里主要介紹前向計算法。（以下內容截自推文開頭提到的參考書籍，潘老師的那本書。）其他計算方法也可以在這本書籍里查閱。

圖片

圖片

04
智能算法(GA、DBO等)編碼方法

對于遺傳算法(GA)，因為其算法本身是離散的，通過選擇、交叉、變異產生下一代。因此，一條染色體就代表一種調度方案。即工件的排序即是它的個體編碼。例如，10個工件的排序方案，用MATLAB初始化GA的一個個體(一條染色體)就是：

x=randperm(10);

效果如下所示：

圖片

但是對于粒子群優化(PSO)、麻雀搜索算法(SSA)、蜣螂優化(DBO)等，它們本身是針對連續優化問題提出的，所以在編碼時需要經過進一步的處理。與GA一樣，一個調度方案(工件排序)表示一個個體，可以采用SPV規則，將實數編碼轉成整數編碼。例如，10個工件的排序方案，用MATLAB初始化DBO的一個個體(一條染色體)就是：

jobNum=10; %?工件數x=unifrnd(0,1,[1?jobNum]);?%?產生10個[0,1]之間隨機數os?=?1:1:jobNum;?%?產生從1到10的數列[~,?up_index]?=?sort(x);?%?對x進行降序排序, 得到位置序列x?=?os(up_index);?%?按照位置序列排序工件,?得到一個調度方案

效果如下：

圖片

此外，與SPV規則相反，Li等提出最大排序值法(Largest rank value, LRV)，也是將連續值映射成離散排列常用的方法之一。如圖2所示，LRV將代表種群個體的一組連續值按降序排列生成一組工件排序。(參考文獻：[2] LI X, YIN M. An opposition-based differential evolution algorithm for permutation flow shop scheduling based on diversity measure [J]. Advances in Engineering Software, 2013, 55(8): 10-31.)

圖片

圖2 最大排序值法的表示方法

05
數值實驗

這里對DBO求解BFSP的效果進行簡單測試，調度問題算例選用Rec(21個)。最大迭代次數T設置為2000，種群規模NP設為60。下面展示的結果都是算法隨機運行一次得到的結果。

首先，以Rec05(20工件×5機器為例)，展示DBO隨機運行一次的求解結果。圖3繪制了種群每代的最優適宜度收斂曲線和平均適宜度收斂曲線：

圖片

圖3 DBO-BFSP對于Rec05的收斂曲線

圖4繪制了調度結果的甘特圖：

圖片

圖4 DBO-BFSP對于Rec05的甘特圖

其次，以Rec11(20工件×10機器為例)，展示DBO隨機運行一次的求解結果，如圖5和圖6所示。

圖片

圖5 DBO-BFSP對于Rec11的收斂曲線

圖片

圖6 DBO-BFSP對于Rec11的甘特圖

最后，以Rec41(75工件×20機器為例)，展示DBO隨機運行一次的求解結果，如圖7和圖8所示。

圖片

圖7 DBO-BFSP對于Rec41的收斂曲線

圖片

圖8 DBO-BFSP對于Rec41的甘特圖

06
MATLAB代碼

智能算法(GA、PSO、DE、GWO、SSA、DBO等)求解阻塞流水車間調度問題(blocking flow-shop scheduling problem, BFSP)的MATLAB代碼，其中：main.m是主函數，直接運行即可；以算法簡稱命名的.m算法代碼；gantt_chart.m用來繪制甘特圖；objective.m是目標函數，即計算Makespan；method.pdf用來說明Makespan的計算方法，代碼采用的是前向計算方法；Car.xlsx和Rec.xlsx是流水車間調度的兩個經典測試集。

輸出結果包括Makespan、工件排序、計算時間、最優適宜度收斂曲線、平均適宜度收斂曲線、甘特圖。

博主挑選了十種算法來求解BFSP。主要是幾種經典算法和幾個近幾年的高引算法。對應的MATLAB代碼鏈接如下：

遺傳算法(GA)求解BFSP關注公眾號，里面有鏈接
差分進化(DE)求解BFSP關注公眾號，里面有鏈接
粒子群優化(PSO)求解BFSP關注公眾號，里面有鏈接
灰狼優化(GWO)求解BFSP關注公眾號，里面有鏈接
鯨魚優化算法(WOA)求解BFSP關注公眾號，里面有鏈接
哈里斯鷹優化(HHO)求解BFSP關注公眾號，里面有鏈接
麻雀搜索算法(SSA)求解BFSP關注公眾號，里面有鏈接
非洲禿鷲優化算法(AVOA)求解BFSP關注公眾號，里面有鏈接
蜣螂優化(DBO)求解BFSP關注公眾號，里面有鏈接
星鴉優化算法(NOA)求解BFSP關注公眾號，里面有鏈接
以上十種智能優化算法(GA、DE、PSO、GWO、WOA、HHO、SSA、AVOA、DBO、NOA)求解BFSP的全家桶關注公眾號，里面有鏈接

可通過下方鏈接下載代碼清單，在里面尋找需要的算法代碼，然后去對應的鏈接獲取。清單會同步更新，一旦有新的代碼，就可以在清單里找到。清單里面有部分代碼是開源獲取的。可隨時免費下載。

鏈接：https://pan.baidu.com/s/1SFDMplrL7tiqGZlrpOSGYg

提取碼：8023

此外，歡迎添加算法交流群進行交流：912369858

本文來自互聯網用戶投稿，該文觀點僅代表作者本人，不代表本站立場。本站僅提供信息存儲空間服務，不擁有所有權，不承擔相關法律責任。
如若轉載，請注明出處：http://www.pswp.cn/news/384400.shtml
繁體地址，請注明出處：http://hk.pswp.cn/news/384400.shtml
英文地址，請注明出處：http://en.pswp.cn/news/384400.shtml

如若內容造成侵權/違法違規/事實不符，請聯系多彩編程網進行投訴反饋email:809451989@qq.com，一經查實，立即刪除！

相關文章

Linux socket編程，對套接字進行封裝

Linux socket編程，對套接字進行封裝

轉自：http://www.cnblogs.com/-Lei/archive/2012/09/04/2670942.html 下面是對socket操作的封裝，因為在Linux下寫中文到了windows里面會亂碼，所以注釋用英文來寫，有空再查下解決方法吧 socket.h #ifndef SOCKET_H #define SOCKET_…
閱讀更多...
Linux系統編程（九）線程同步

Linux系統編程（九）線程同步

Linux系統編程（九）線程同步一、什么是線程同步？二、互斥量三、條件變量pthread_cond_wait函數pthread_cond_signal函數生產者和消費者模型一、什么是線程同步？ 線程同步，指一個線程發出某一功能調用時，在沒…
閱讀更多...
linux網絡編程（一）網絡基礎傳輸知識

linux網絡編程（一）網絡基礎傳輸知識

linux網絡編程（一）網絡傳輸基礎知識一、什么是協議？二、使用步驟典型協議2.網絡應用程序設計模式C/S模式B/S模式優缺點3.分層模型4.TCP/IP四層模型通信過程5.協議格式數據包封裝以太網幀格式ARP數據報格式IP段格式UDP數據報格式TCP數據報格式…
閱讀更多...
linux網絡編程:使用多進程實現socket同時收發數據

linux網絡編程:使用多進程實現socket同時收發數據

轉載：http://blog.csdn.net/li_wen01/article/details/52685844 前面已講過使用一個進程實現服務端和客戶端P2P通信的實例，但是它只能同時處理一個客戶端的連接。如果要實現并發處理多個客戶端的連接并且實現P2P通信，可以使用多進程來處理。相…
閱讀更多...
Linux 進程學習（四）------ sigaction 函數

Linux 進程學習（四）------ sigaction 函數

轉自：http://www.cnblogs.com/wblyuyang/archive/2012/11/13/2768923.html 使用 sigaction 函數： signal 函數的使用方法簡單，但并不屬于 POSIX 標準，在各類 UNIX 平臺上的實現不盡相同，因此其用途受 到了一定的限制…
閱讀更多...
linux網絡編程（二）高并發服務器

linux網絡編程（二）高并發服務器

linux網絡編程&#xff08;二&#xff09;高并發服務器錯誤處理高并發服務器多進程并發服務器客戶端錯誤處理 #include "wrap.h"int Bind(int fd, const struct sockaddr* sa, socklen_t salen) {int ret;if ((ret bind(fd, sa, salen)) < 0){perror("bind…
閱讀更多...
linux知識（一） 程序、進程與線程

linux知識（一） 程序、進程與線程

linux知識&#xff08;一&#xff09; 程序、進程與線程程序進程程序如何變成進程&#xff1f;線程線程與進程fork和創建新線程的區別優點程序 程序&#xff1a;程序是已編譯好的二進制文件&#xff0c;存儲在磁盤中&#xff0c;不占用系統資源 程序包括&#xff1a; RO段&am…
閱讀更多...
linux 信號signal和sigaction理解

linux 信號signal和sigaction理解

轉載&#xff1a;http://blog.csdn.net/beginning1126/article/details/8680757 今天看到unp時發現之前對signal到理解實在淺顯&#xff0c;今天拿來單獨學習討論下。 signal&#xff0c;此函數相對簡單一些&#xff0c;給定一個信號&#xff0c;給出信號處理函數則可&#xff…
閱讀更多...
linux知識（二）互斥量、信號量和生產者消費者模型

linux知識（二）互斥量、信號量和生產者消費者模型

linux知識&#xff08;二&#xff09;互斥量、信號量和生產者消費者模型一、互斥量產生原因二、信號量生產者消費者模型一、互斥量 產生原因 使用多線程常常會碰到數據混亂的問題&#xff0c;那么使用互斥量&#xff0c;相當于“加鎖”的操作&#xff0c;將有助于解決數據混亂…
閱讀更多...
基于Linux的Socket編程之TCP全雙工Server-Client聊天程序

基于Linux的Socket編程之TCP全雙工Server-Client聊天程序

轉載&#xff1a;http://blog.csdn.net/apollon_krj/article/details/53437764#0-tsina-1-58570-397232819ff9a47a7b7e80a40613cfe1 一、引言&#xff1a; 由于accept函數、read、write、recv、send等函數都是是阻塞式的&#xff0c;在同一個進程之中&#xff0c;只要有任何一個…
閱讀更多...
數據結構（一）線性表

數據結構（一）線性表

數據結構&#xff08;一&#xff09;線性表一、線性表定義二、順序表定義動態數組三、單鏈表定義不帶頭結點帶頭結點頭結點與不帶頭結點的區別頭插法與尾插法雙鏈表循環鏈表循環單鏈表循環雙鏈表靜態鏈表一、線性表定義 線性表是具有相同數據類型的n個數據元素的有限序列 特點…
閱讀更多...
linux網絡編程（二）TCP通訊狀態

linux網絡編程（二）TCP通訊狀態

linux網絡編程&#xff08;二&#xff09;TCP通訊狀態TCP狀態轉換為什么需要等待2MSL&#xff1f;端口復用TCP狀態轉換 tcp協議連接開始會經過三次握手&#xff0c;客戶端和服務器開始都會處于CLOSED狀態 第一次握手&#xff1a;客戶端會先發送SYN請求給服務器&#xff0c;客戶…
閱讀更多...
gethostbyname() 函數說明

gethostbyname() 函數說明

轉載&#xff1a;http://www.cnblogs.com/cxz2009/archive/2010/11/19/1881611.html gethostbyname()函數說明——用域名或主機名獲取IP地址 包含頭文件 #include <netdb.h> #include <sys/socket.h> 函數原型 struct hostent *gethostbyna…
閱讀更多...
linux網絡編程（三）select、poll和epoll

linux網絡編程（三）select、poll和epoll

linux網絡編程&#xff08;三&#xff09;select、poll和epoll一、為什么會有多路I/O轉接服務器&#xff1f;二、select三、poll三、epoll一、為什么會有多路I/O轉接服務器&#xff1f; 為什么會有多路I/O轉接服務器呢&#xff1f;在學這個之前&#xff0c;我們同使用的是多線…
閱讀更多...
Linux socket編程（一） 對套接字操作的封裝

Linux socket編程（一） 對套接字操作的封裝

轉載:http://www.cnblogs.com/-Lei/archive/2012/09/04/2670942.html 以前寫的&#xff0c;現在回顧一下&#xff1a; 下面是對socket操作的封裝&#xff0c;因為在Linux下寫中文到了windows里面會亂碼&#xff0c;所以注釋用英文來寫&#xff0c;有空再查下解決方法吧 socket.…
閱讀更多...
數據結構（二）棧

數據結構（二）棧

棧一、棧順序棧線性棧(不帶頭結點)線性棧(帶頭結點)共享棧一、棧 棧是只允許在一端進行插入或刪除操作的線性表。 棧頂&#xff1a;線性表允許進行插入刪除的那一端 棧底&#xff1a;固定的&#xff0c;不允許進行插入和刪除的那一端 空棧&#xff1a;不含如何元素的空表 順序…
閱讀更多...
如何在linux上安裝sqlite數據庫

如何在linux上安裝sqlite數據庫

如何在linux上安裝sqlite數據庫一、下載二、解壓三、配置&#xff08;configure&#xff09;四、編譯和安裝五、執行sqlite3程序六、測試代碼一、下載 首先要先下載sqlite3源碼包 鏈接&#xff1a;https://pan.baidu.com/s/1_70342ZLlPjLlqGzpy5IHw 提取碼&#xff1a;84ne …
閱讀更多...
數據結構（三）隊列

數據結構（三）隊列

數據結構&#xff08;三&#xff09;隊列隊列隊列&#xff08;順序存儲&#xff09;循環隊列&#xff08;順序存儲&#xff09;隊列&#xff08;鏈式存儲&#xff09;隊列 隊列是一種受限制的線性表&#xff0c;只允許表的一端插入&#xff0c;在表的另一端刪除 隊列&#xf…
閱讀更多...
Linux fcntl函數詳解

Linux fcntl函數詳解

轉載&#xff1a;http://www.cnblogs.com/xuyh/p/3273082.html 功能描述&#xff1a;根據文件描述詞來操作文件的特性。 文件控制函數 fcntl -- file control 頭文件&#xff1a; #include <unistd.h> #include <fcntl.h> 函數原型&#xff1a; …
閱讀更多...
vs2019使用sqlite數據庫遠程連接linux

vs2019使用sqlite數據庫遠程連接linux

vs2019使用sqlite數據庫遠程連接linux一、sqlite3添加到目錄二、添加依賴庫三、測試一、sqlite3添加到目錄 將兩個sqlite3頭文件放入目錄中 二、添加依賴庫 打開項目屬性 添加完成 三、測試 #include <stdio.h> #include <sqlite3.h>int main(int argc, cha…
閱讀更多...
最新文章

Copyright @ 2022~2023