使用CPLEX求解小规模能量高效的FJSP

发布时间:2022-12-09 08:30

CPLEX在车间调度问题中,是验证你的模型是否正确的重要指标。通过定义变量,约束,目标等。让CPLEX优化器求解。如果能找到可行解,说明该模型的正确性。CPLEX可以被matlab、java、c++等语言作为外部求解器调用。本篇博客主要介绍如何用matlab调用CPLEX求解小规模的模糊柔性作业车间调度问题。

自我介绍

本人是中国地质大学(武汉)计算机学院,研二研究生一枚。目前在投SCI 3篇已发表EI一篇,获得2021届国奖,十七届华为杯三等奖。导师龚文引教授(省杰青)。 研究方向是智能优化算法在车间调度问题的应用。
感兴趣方向:机器学习,强化学习,深度学习,迁移优化进化,数据驱动优化,多目标优化,约束多目标优化,车间调度问题。

本文将介绍如何,使用OPL语言,在OPLIDE上用CPELX求解器对于小规模的FJSP柔性作业车间调度问题进行求解。

下载CPLEX

这篇博客中的链接是学术版
也可以去CPLEX官网下载使用版,需要注册IBM账号,通过邮箱验证等等。学生有免费使用版一个月,网上有很多破解版,或者共享的学术版,推荐用12.x版本的。因为经过泣血的几天8-23点的学习,发现20.x开头的会有各种问题。

CPLEX安装

这里不用matlab等语言调用直接用的是IBM ILOG CPLEX 12.6.3版本

使用CPLEX求解小规模能量高效的FJSP_第1张图片
使用CPLEX求解小规模能量高效的FJSP_第2张图片
使用CPLEX求解小规模能量高效的FJSP_第3张图片
使用CPLEX求解小规模能量高效的FJSP_第4张图片
使用CPLEX求解小规模能量高效的FJSP_第5张图片
使用CPLEX求解小规模能量高效的FJSP_第6张图片
Microsoft Visual C++2010 SP1 Redistributable Package x64下载连接
使用CPLEX求解小规模能量高效的FJSP_第7张图片

新解一个OPL项目

使用CPLEX求解小规模能量高效的FJSP_第8张图片
新建完之后会在红框看到你的配置环境。只有把你的mod和dat右键添加到运行配置,且全路径必须是英文配置器的名字也得是英文才能正常运行。
使用CPLEX求解小规模能量高效的FJSP_第9张图片

OPL语言基本语法

  1. 自定义变量类型

自定义变量,通常是读取FJSP中已经确定的变量,如工件数J,机器数M,工序数OpNum,加工时间pTime。 float运行速度快于int。…表示 引用dat数据文件中同名的变量。一般将模型写在mod的文件中,dat写入模型需要输入的数据。

 int JobNum=...;
 int MacNum=...;
 int MaxOpNum=...;
 int MaxMState=...;
 //读取数据并确定变量的范围
 int M=10000;
 range JobIndex=0..JobNum-1;
 range MIndex=0..MacNum-1;
 range OpIndex=0..MaxOpNum-1;
 range MState=0..MaxMState;
 int OpNum[JobIndex]=...;
 //int x[JobIndex][OpIndex][MIndex]=...;
 int x[MIndex][JobIndex][OpIndex]=...;
 //float pTime[JobIndex][OpIndex][MIndex]=...;
 float pTime[MIndex][JobIndex][OpIndex]=...;
  1. 决策变量
    决策变量用于表达,在求解过程中,一直处于变化的,动态的变量。dvar关键字表示决策变量,后面接数据类型。决策变量不能被初始化。
//设置决策变量 未知的
dvar boolean X[JobIndex][OpIndex][MIndex][MState];
dvar boolean Y[MIndex][MState];//机器是否在该状态
//设置待计算的目标函数,以及开始加工时间
dvar float OpSTime[JobIndex][OpIndex];// 每个工序开始加工的时间
dvar float MSTime[MIndex][MState];// 每个机器开始加工的时间
dvar float EnergyIdle[MIndex][MState];
dvar float Cmax; //Cmax 就是每一个工序最后一个完成时间 最大的那个
  1. 决策表达式
    决策表达式用于,综合自定义变量和关键变量,写出一个公式,多半是最后需要优化的目标或者其一部分。由关键字 dexpr表示 后面接返回值类型,变量名,表达式。常用的公式中的关键字有sum,max,min。语法中内循环用逗号隔开。
dexpr float TotalPEnergy=sum(i in JobIndex,j in OpIndex, m in MIndex, t in MState)X[i][j][m][t]*pTime[m][i][j]*Ep;
dexpr float TotalIdleEnergy=sum(m in MIndex, t in MState) EnergyIdle[m][t];
dexpr float TEC=TotalPEnergy+TotalIdleEnergy+Et;

优化目标

CPLEX不支持多目标优化问题,只能一次优化一个目标。且决策变量的维度超过1000维就无法进行求解。所以要控制所有决策变量在1000以内

minimize Cmax;
//minimize TEC;

设置约束条件

约束条件是混合整数线性规划问题中精髓,只要最后决策变量包含整数变量的组合优化问题,就是混合整数线性规划MILP。用关键字 subject to表示,论文中用s.t.缩写表示。基本是用forall,然后加上不等式作为约束,不能表达赋值,只能表达==。满足某某条件时两个必须相等。

//设置约束条件
subject to{
Cmax<=405; 

forall(i in JobIndex, j in OpIndex){
	sum(m in MIndex, t in MState:x[m][i][j]>0)X[i][j][m][t]==1;//同一时刻只有一个机器加工
}

//最大完工时间约束
forall(i in JobIndex){
OpSTime[i][OpNum[i]-1]+sum(m in MIndex, t in MState:x[m][i][OpNum[i]-1]>0)pTime[m][i][OpNum[i]-1]*X[i][OpNum[i]-1][m][t]<=Cmax;
}

//同一个工件的先后工序约束
forall(i in JobIndex, j in 0..OpNum[i]-2){
OpSTime[i][j]+sum(m in MIndex,t in MState:x[m][i][j]>0)pTime[m][i][j]*X[i][j][m][t]<=OpSTime[i][j+1];
}

forall(m in MIndex,t in MState) {//所有工厂所有机器所有位置的 决策变量总和小于等于1
sum(i in JobIndex,j in OpIndex:x[m][i][j]>0)X[i][j][m][t]<=1;}

forall(m in MIndex,t in 0..MaxMState-2){ //所有工厂 所有机器的所有位置 总结当前工件所有工序的决策变量大于等于下一个的
sum(i in JobIndex,j in OpIndex:x[m][i][j]>0)X[i][j][m][t]>=
sum(i in JobIndex,j in OpIndex:x[m][i][j]>0)X[i][j][m][t+1];}

//所有工厂 所有机器 所有位置的 下一个机器位置的开始时间要大于等于上一个机器的开始时间+开关的最大忍耐时间
forall(m in MIndex,t in 0..MaxMState-2){  
  MSTime[m][t+1]-MSTime[m][t]>=
  sum(i in JobIndex,j in OpIndex:x[m][i][j]>0)pTime[m][i][j]*X[i][j][m][t];}
  
//所有的工厂所有的机器所有的位置 每个机器的能量消耗必须大于等于 该机器的总能量消耗乘以 是否该机器在该工厂的该位置
forall(m in MIndex,t in 0..MaxMState-2){ 
//总的能量消耗远大于 等待时间的能量消耗 减去一个很大的数还要大
EnergyIdle[m][t]+Y[m][t]*M>=
(MSTime[m][t+1]-MSTime[m][t]-sum(i in JobIndex,j in OpIndex:x[m][i][j]>0)
pTime[m][i][j]*X[i][j][m][t])*Es;  
} 
//所有工厂中所有机器的位置都要小于3
forall(m in MIndex){
  sum(t in 0..MaxMState-2)Y[m][t]<=3;}
 //所有工件所有工序所有工厂所有机器所有位置每一个机器每一个位置的开始时间都要远等于该工序的开始时间,如果在这上面加工
forall(i in JobIndex,j in 0..OpNum[i]-1,m in MIndex,t in MState:x[m][i][j]>0){  
  MSTime[m][t]>=OpSTime[i][j]-M*(1-X[i][j][m][t]);
  MSTime[m][t]<=OpSTime[i][j]+M*(1-X[i][j][m][t]);
} 

//所有的工件所有的工序在所有工厂开始时间都要大于等于0且小于等于一个很大的数   
forall(i in JobIndex,j in OpIndex){
OpSTime[i][j]>=0;
OpSTime[i][j]<=M;
}
//所有的机器的所有位置在所有工厂开始时间都要大于等于0且小于等于一个很大的数   
forall(m in MIndex,t in MState){
  MSTime[m][t]>=0;   
 EnergyIdle[m][t]>=0;}
}

代码块

和java类似OPL中的代码块是需要关键字execute表示执行的。而且代码块是

execute
{
writeln("最大完工时间:",Cmax);
writeln("TEC: ",TEC);

}

一个小型的柔性作业车测试问题

MFJS01 5个工件,6个机器,每个工件3个工序

/*********************************************
 * OPL 12.6.3.0 Data
 * Author: d
 * Creation Date: 2021-12-9 at 上午9:48:10
 *********************************************/
MaxOpNum=3;
JobNum =5;
MacNum =6;
MaxMState=6;
OpNum=[3,3,3,3,3];

x=
[
[
[1,0,0,],
[1,0,0,],
[1,0,0,],
[1,0,0,],
[1,0,0,],
],
[
[1,1,0,],
[0,1,0,],
[1,0,0,],
[1,0,0,],
[1,0,0,],
],
[
[1,0,0,],
[1,1,0,],
[0,1,0,],
[0,0,0,],
[1,1,0,],
],
[
[0,1,1,],
[0,0,0,],
[0,1,1,],
[0,0,1,],
[0,1,0,],
],
[
[0,0,1,],
[0,0,1,],
[0,0,1,],
[0,1,0,],
[0,1,1,],
],
[
[0,0,0,],
[0,0,1,],
[0,0,1,],
[0,0,1,],
[0,0,1,],
],
];

pTime =
[
[
[147,0,0],
[214,0,0],
[87,0,0],
[87,0,0],
[128,0,0]
],
[
[123,130,0],
[0,66,0],
[62,0,0],
[65,0,0],
[123,0,0]
],
[
[145,0,0],
[150,87,0],
[0,180,0],
[0,0,0],
[145,86,0]
],
[
[0,140,150],
[0,0,0],
[0,105,190],
[0,0,145],
[0,65,0]
],
[
[0,0,160],
[0,0,178],
[0,0,100],
[0,173,0],
[0,47,110]
],
[
[0,0,0],
[0,0,95],
[0,0,153],
[0,0,136],
[0,0,85]
]
];


EE-FJSP的MILP模型

/*********************************************
 * OPL 12.6.3.0 Model
 * Author: d
 * Creation Date: 2021-12-8 at 下午3:26:58
 *********************************************/
 int JobNum=...;
 int MacNum=...;
 int MaxOpNum=...;
 int MaxMState=...;
 //读取数据并确定变量的范围
 int M=10000;
 range JobIndex=0..JobNum-1;
 range MIndex=0..MacNum-1;
 range OpIndex=0..MaxOpNum-1;
 range MState=0..MaxMState;
 int OpNum[JobIndex]=...;
 //int x[JobIndex][OpIndex][MIndex]=...;
 int x[MIndex][JobIndex][OpIndex]=...;
 //float pTime[JobIndex][OpIndex][MIndex]=...;
 float pTime[MIndex][JobIndex][OpIndex]=...;
  //设置求解器的时间阈值,线程数,误差率
 execute {
 cplex.tilim = 600;
 cplex.threads=3;//线程
 cplex.epagap=0;//绝对容差
 cplex.epgap=0;//相对容差
 }
 
 //设置 加工功率,等待功率,开关功率
float Ep=0.5;//加工功率 500kw每s 0.5Mw
float Es=0.04;//等待功率 40kw每s
float Et=0.06;//开机关机功率 60kw每s 

//设置决策变量 未知的
dvar boolean X[JobIndex][OpIndex][MIndex][MState];
dvar boolean Y[MIndex][MState];//机器是否在该状态
//设置待计算的目标函数,以及开始加工时间
dvar float OpSTime[JobIndex][OpIndex];// 每个工序开始加工的时间
//dvar float OpCTime[JobIndex][OpIndex];// 每个工序完成加工的时间
//dvar float OpDTime[JobIndex][OpIndex];// 每个工序开始加工前的等待时间
dvar float MSTime[MIndex][MState];// 每个机器开始加工的时间
//dvar float MCTime[MIndex][MState];// 每个机器完成加工的时间
dvar float EnergyIdle[MIndex][MState];
//dvar float MCTime[MIndex];// 每个机器当前的完工时间


//CPLEX只能优化单目标问题,所以两个目标的优化的分开进行求下界
//目标函数 Cmax TEC的表达式
dvar float Cmax; //Cmax 就是每一个工序最后一个完成时间 最大的那个

dexpr float TotalPEnergy=sum(i in JobIndex,j in OpIndex, m in MIndex, t in MState)X[i][j][m][t]*pTime[m][i][j]*Ep;
dexpr float TotalIdleEnergy=sum(m in MIndex, t in MState) EnergyIdle[m][t];
dexpr float TEC=TotalPEnergy+TotalIdleEnergy+Et;
//设置优化目标
minimize Cmax;
//minimize TEC;

//设置约束条件
subject to{
Cmax<=405; 

forall(i in JobIndex, j in OpIndex){
	sum(m in MIndex, t in MState:x[m][i][j]>0)X[i][j][m][t]==1;//同一时刻只有一个机器加工
}

//最大完工时间约束
forall(i in JobIndex){
OpSTime[i][OpNum[i]-1]+sum(m in MIndex, t in MState:x[m][i][OpNum[i]-1]>0)pTime[m][i][OpNum[i]-1]*X[i][OpNum[i]-1][m][t]<=Cmax;
}

//同一个工件的先后工序约束
forall(i in JobIndex, j in 0..OpNum[i]-2){
OpSTime[i][j]+sum(m in MIndex,t in MState:x[m][i][j]>0)pTime[m][i][j]*X[i][j][m][t]<=OpSTime[i][j+1];
}

forall(m in MIndex,t in MState) {//所有工厂所有机器所有位置的 决策变量总和小于等于1
sum(i in JobIndex,j in OpIndex:x[m][i][j]>0)X[i][j][m][t]<=1;}

forall(m in MIndex,t in 0..MaxMState-2){ //所有工厂 所有机器的所有位置 总结当前工件所有工序的决策变量大于等于下一个的
sum(i in JobIndex,j in OpIndex:x[m][i][j]>0)X[i][j][m][t]>=
sum(i in JobIndex,j in OpIndex:x[m][i][j]>0)X[i][j][m][t+1];}

//所有工厂 所有机器 所有位置的 下一个机器位置的开始时间要大于等于上一个机器的开始时间+开关的最大忍耐时间
forall(m in MIndex,t in 0..MaxMState-2){  
  MSTime[m][t+1]-MSTime[m][t]>=
  sum(i in JobIndex,j in OpIndex:x[m][i][j]>0)pTime[m][i][j]*X[i][j][m][t];}
  
//所有的工厂所有的机器所有的位置 每个机器的能量消耗必须大于等于 该机器的总能量消耗乘以 是否该机器在该工厂的该位置
forall(m in MIndex,t in 0..MaxMState-2){ 
//总的能量消耗远大于 等待时间的能量消耗 减去一个很大的数还要大
EnergyIdle[m][t]+Y[m][t]*M>=
(MSTime[m][t+1]-MSTime[m][t]-sum(i in JobIndex,j in OpIndex:x[m][i][j]>0)
pTime[m][i][j]*X[i][j][m][t])*Es;  
} 
//所有工厂中所有机器的位置都要小于3
forall(m in MIndex){
  sum(t in 0..MaxMState-2)Y[m][t]<=3;}
 //所有工件所有工序所有工厂所有机器所有位置每一个机器每一个位置的开始时间都要远等于该工序的开始时间,如果在这上面加工
forall(i in JobIndex,j in 0..OpNum[i]-1,m in MIndex,t in MState:x[m][i][j]>0){  
  MSTime[m][t]>=OpSTime[i][j]-M*(1-X[i][j][m][t]);
  MSTime[m][t]<=OpSTime[i][j]+M*(1-X[i][j][m][t]);
} 

//所有的工件所有的工序在所有工厂开始时间都要大于等于0且小于等于一个很大的数   
forall(i in JobIndex,j in OpIndex){
OpSTime[i][j]>=0;
OpSTime[i][j]<=M;
}
//所有的机器的所有位置在所有工厂开始时间都要大于等于0且小于等于一个很大的数   
forall(m in MIndex,t in MState){
  MSTime[m][t]>=0;   
 EnergyIdle[m][t]>=0;}
}

execute
{
writeln("最大完工时间:",Cmax);
writeln("TEC: ",TEC);

}

改进MOEA/D求解模糊柔性作业车间调度问题

论文解读附带源码

学者主页

https://meiyi1986.github.io/ 新西兰威灵顿大学 张孟杰组教授梅一的主页
http://ischedulings.com/shares.html 山东师范李俊青教授
https://wewnyin.github.io/wenyingong/ 中国地质大学(武汉)龚文引教授

ItVuer - 免责声明 - 关于我们 - 联系我们

本网站信息来源于互联网,如有侵权请联系:561261067@qq.com

桂ICP备16001015号