目錄
1 概述
2 遺傳優化算法
3 工廠中的房間排程
4 Matlab代碼實作
5 運作結果
6 參考文獻
7 寫在最後
1 概述
排程通過合理安排生産資源,以縮短生産時間和提高資源使用率為目的,在生産系統中扮演着重要的角色。作業工廠中的房間排程問題(Job-shop Schedu-ling Problem，JSP)是一類經典的排程問題,其通過安排n個工件在m台機器上的加.工順序來優化一個或多個排程名額。在JSP中,每個工件由一道或多道具有固定加工順序的工序構成,且每道工序的加工機器唯一。柔性作業工廠中的房間排程問題(FlexibleJob-shop Scheduling Problem，FJSP)是JSP的擴充,它允許一道工序有多台可供選擇的加工機器,且
在不同機器上的加工時間可能存在差異,即相對于JSP,FJSP具有一般性,更符合柔性制造系統的實際情況。在FJSP中,機器柔性雖然能夠提高制造系統的執行效率,但是擴大了可行解的範圍,增加了求解問題的難度和複雜性。
柔性作業工廠中的房間排程(FJSP)是一類具有廣泛應用背景的排程問題,作為求解FISP最受歡迎的算法
之一,遺傳算法引起了廣泛關注。針對求解FJSP的遺傳算法,特别是5類主要染色體編碼方法以及相關的交叉和變異算子進行全面綜述,并從編碼可行性、編碼空間與解空間的映射關系、染色體存儲空間、解碼複雜性、編碼完備性、遺傳操作複雜性和遺傳操作多樣性7個次元綜合評價了5類編碼方法。結果表明,MSOS-I編碼是遺傳算法求解FJSP較好的染色體編碼方法,其染色體結構簡單,并可選用較多類型的交叉和變異算子。
2 遺傳優化算法
| 智能優化算法——遺傳算法（Python&Matlab實作） |
| 智能優化算法——遺傳算法 |
3 工廠中的房間排程
定每道工.序的加工機器（路徑子問題),開确定所有工序在機器上的加工順序(排程子問題),以實作對一個或多個排程目标的優化,如最大完工時間、總機器負荷、總延遲時間、最大松弛時間等。
求解FJSP通常需要滿足如下假設條件:
(l)0時刻,所有工件均處于待加工.狀态,所有機器均處于空閑狀态。
(2)同一時刻,同一台機器隻能加工一個工件的某道工序。
(3)同一時刻,同一工件隻能被一台機器加且不允許中斷正在加工的T序。
(4)同一工件的工序加工順序固定且不可更改，不同工件的工序間沒有順序限制關系。
基于上述FJSP的描述,很多學者提出求解FJSP的O-l整數規劃模型,另外析取圖模型也常用于描述FJSPL,本文不再給出這些模型的數學定義。
4 Matlab代碼實作
本文僅展現部分代碼，全部代碼及文章見：
基于遺傳算法的柔性工廠中的房間排程（Matlab代碼實作）
function [Z,machine_weight,pvals] = fitness(chroms,num_machine,e,num_job,num_op)
sizepop=size(chroms,1);
pvals=cell(1,sizepop);
Z1=zeros(1,sizepop);
Z2=Z1;
total_op_num=sum(num_op); % 總工序數
for k=1:sizepop
chrom=chroms(k,:);
machine=zeros(1,num_machine); % 記錄各機器變化時間
job=zeros(1,num_job); % 記錄各工件變化時間
machine_time=zeros(1,num_machine); % 計算各機器的實際加工時間
pval=zeros(2,total_op_num); % 記錄各工序開始和結束時間
for i=1:total_op_num
% 機器時間大于工件時間
if machine(chrom(total_op_num+i))>=job(chrom(i))
pval(1,i)=machine(chrom(total_op_num+i)); % 記錄工件開始時間
machine(chrom(total_op_num+i))=machine(chrom(total_op_num+i))+chrom(total_op_num*2+i);
job(chrom(i))=machine(chrom(total_op_num+i));
pval(2,i)=machine(chrom(total_op_num+i)); % 記錄工件結束時間
% 機器時間小于工件時間
else
pval(1,i)=job(chrom(i));
job(chrom(i))=job(chrom(i))+chrom(total_op_num*2+i);
machine(chrom(total_op_num+i))=job(chrom(i));
pval(2,i)=job(chrom(i));
end
machine_time(chrom(total_op_num+i))=machine_time(chrom(total_op_num+i))+chrom(total_op_num*2+i);
end
Z1(k)=max(machine); % 最大機器時間值，對應makespan
% machine_weight=machine_time/sum(machine_time); % 計算各機器的負荷
machine_weight=machine_time;
Z2(k)=max(machine_weight)-min(machine_weight);
pvals{k}=pval;
end
% min_makespan=min(Z1);%所有染色體的makespan最優值
% max_makespan=max(Z1);
% min_weight=min(Z2);%負載最優值
% max_weight=max(Z2);
% Z=e*((Z1-min_makespan)./(max_makespan-min_makespan))+(1-e)*((Z2-min_weight)./(max_weight-min_weight));%計算适應度
Z=e*Z1+(1-e)*Z2;
5 運作結果
