2023 美賽(美國大學生數學模組化)思路解析
2023美賽ABCDEF賽題思路解析：
https://blog.csdn.net/dc_sinor/article/details/128779911
最短時間生産計劃模型
該模型出現在好幾個競賽賽題上，預測2022今年國賽也會與該模型相關。
1 模型描述
離散系統仿真在工業生産的工序安排中起到了相當重要的作用，如何就一些内部機制複雜的離散問題建立簡單易行、可監測性強的數學模型一直是仿真技術的研究熱點．
離散事件系統現有三種仿真模組化政策，即：
- 事件排程法
- 活動掃描法
- 程序互動法．
該模型demo學長采用了其中的活動掃描法對生産中的一個實際例子進行了處理．
活動掃描法對于各事件之間相關性很強的系統有着很好的适用性．
2 執行個體
2.1 問題描述
在許多工廠生産過程中，由于裝置的數量、産品加工的次序限制，往往不能簡單地安排生産任務．我們設想，應用強大的數學軟體配合簡單易行的方法進行安排．
設某重型機械廠産品都是單件性的，其中有一工廠中的房間共有4種不同裝置，現接受6件産品的加工任務，每件産品接受的程式在指定的裝置上加工，其工序與加工周期如下表
現在我們根據這一實際問題，尋求安排的方法．
要求：
1、每件産品必須按規定的工序加工，不得颠倒．
2、每台裝置在同一時間隻能擔任一項任務（每件産品的每個工序為一個任務）．
３、在盡可能短的時間裡，完成所接受的全部任務．
為了節省電能，合理配置設定生産任務，廠方還要求：
1、做出每件産品的每個工序開工、完工時間表．
2、給出每台裝置承擔任務的時間表．
2.2 數學模型
2.2.1 模型流程
2.2.2 符号約定
2.2.3 求解模型
2.3 相關代碼
clear
clc
seq=[3 1 2 3 4 0 0 0 %各産品加工時所用的裝置的次序
1 4 2 3 0 0 0 0
3 4 1 2 1 0 0 0
2 3 4 1 4 3 0 0
4 2 3 4 1 3 4 0
1 2 1 3 4 1 3 1];
tim=[8 2 4 24 6 0 0 0 %加工對應使用的時間
4 5 3 4 0 0 0 0
3 7 15 20 8 0 0 0
7 6 21 1 16 3 0 0
10 4 8 4 12 6 1 0
1 4 7 3 5 2 5 8];
whole=[0 0 0 0];
for i=1:6
for j=1:8
if(seq(i,j)~=0)
whole(seq(i,j))=whole(seq(i,j))+tim(i,j);
end
end
end
whole %生産各件産品所需的總時間
mes=cell(4，1); %記錄各個裝置的工作時間（對應于上面tim的位置）
for k=1:4
mes{k,1}=zeros(6,8);
for j=1:8
for i=1:6
if(seq(i,j)==k)
mes{k,1}(i,j)=tim(i,j);
else
mes{k,1}(i,j)=100;
end
end
end
end
turn=cell(5,100); %記錄四個裝置的開關時間及加工對象（on(i)）
for i=1:4
for j=1:100
turn{i,j}='off';
end
end
for i=1:100
turn{5,i}=[num2str(i) '分'];
end
open=zeros(6,8);
%記錄6個産品的加工進度，0表示未進行，1表示已開始（或已結束），2表示可選,3表示沒有這個程式
for i=1:6
open(i,1)=2;
end
for i=1:6
for j=1:8
if seq(i,j)==0
open(i,j)=3;
end
end
end
gongxu=zeros(6,1);
dai=zeros(4,1);
j=1;
s=[1 1 1 1 1 3 3 3
1 1 1 1 3 3 3 3
1 1 1 1 1 3 3 3
1 1 1 1 1 1 3 3
1 1 1 1 1 1 1 3
1 1 1 1 1 1 1 1];
while isequal(open,s)==0
on=[];
for i=1:4
if turn{i,j}=='off'
%在turn矩陣中逐列搜尋，若裝置處于關機狀态，則作記錄（可用）
on=[on i];
end
end
l1=length(on);
for m=1:l1 %在整個生産計劃中（對裝置逐個）尋找能夠選作操作的步驟
[x,y]=find(open==2);
l2=length(x);
a=[x(1) y(1)];
for k=1:l2 %對某個裝置on(m)，找出目前它能操作的步驟中耗時最小的一個
if mes{on(m)}(a(1),a(2))>mes{on(m)}(x(k),y(k))
a=[x(k) y(k)];
end
end
if turn{on(m),j}=='off' & mes{on(m)}(a(1),a(2))~=100
%若時間為100則意味着這個步驟不屬于我們希望使用的那件裝置
while tim(a(1),a(2))>0
turn{on(m),tim(a(1),a(2))+j-1}=a(1);
tim(a(1),a(2))=tim(a(1),a(2))-1;
end
end
end
for i=1:4
if turn{i,j}~='off'
dai(i)=turn{i,j};
end
end
for i=1:4
if turn{i,j}~='off' & turn{i,j+1}=='off'
gongxu(turn{i,j})=gongxu(turn{i,j})+1;
open(turn{i,j},gongxu(turn{i,j}))=1;
end
if gongxu(dai(i))<8 & open(dai(i),gongxu(dai(i))+1)~=3 & turn{i,j+1}=='off'
open(dai(i),gongxu(dai(i))+1)=2;
end
end
j=j+1;
end
2.4 模型求解結果
每件産品的每個工序開工、完工時間表
每台裝置承擔任務的時間表
從結果中我們可以看到，使用這種方法，隻需７８個機關時間就可以完成所有的工序．而我們同時也可以在論文的開始部分看到，單就完成 就需耗費７５個機關時間．可見這種方法得出的結果還是相當使人滿意的，而且操作簡單，可監測性強．
2023 美賽(美國大學生數學模組化)思路解析
2023美賽ABCDEF賽題思路解析：
https://blog.csdn.net/dc_sinor/article/details/128779911