我的上一篇博客Cplex解决FSP问题 - 加油，陌生人！ - 博客园 (cnblogs.com)用Cplex完成了FSP的建模，这篇文章主要是解决JSP问题（车间调度问题）。
JSP问题：n个工件，m台机器，每个工件都有自己的加工路线，要求找出最佳的加工顺序，使得完工时间最小。从问题的描述来看，FSP是一种特殊的JSP，因为它所有工件的加工路线都是相同的。
下面就来考虑如何解决JSP问题。
先附上数据文件（.dat），如下
数据文件.dat
n=4;//工件数量
m=3;//机器数量
p=[[20,87,31],
[25,32,24],
[72,23,28],
[86,76,97]];//各工件在各机器上的加工时间
/*prec=[[1,3,2],
[3,1,2],
[3,2,1],
[2,3,1]];*/
temp=[ [[0,0,0,0],//表示加工顺序
[0,0,0,1],
[0,0,0,0],
[0,0,1,0]],
[[0,0,0,0],
[0,0,1,0],
[0,0,0,0],
[0,1,0,0]],
[[0,0,0,0],
[0,0,0,0],
[0,1,0,0],
[0,0,1,0]],
[[0,0,0,0],
[0,0,0,0],
[0,0,0,1],
[0,1,0,0]] ];
p表示各工件在各机器上的加工时间，例如工件1在机器1上的加工时间为20。temp用来表示每个工件的加工工艺，是个三维矩阵，里面包含了n个(m+1)*(m+1)的二维矩阵。例如在第一个二维矩阵arr中
可以看到arr[1][3]=1，表示机器1-->机器3；arr[3][2]=1，表示机器3-->2。于是工件1的加工顺序为m1-->m3-->m2，其他的工件也是类似的原理。
模型文件.mod
int n=...;//工件数量
int m=...;//机器数量，也可以理解为工序数量，因为一道工序只有一台机器
int M=100000;//一个非常大的数
range r1=1..n;
range r2=1..m;
int temp[r1][0..m][0..m]=...;
dvar float+ c[r1][r2];//表示完工时间
int p[r1][r2]=...;
dvar boolean a[r1][0..m][0..m];//i,h,k.机器h优先于机器k加工工件i
dvar boolean x[0..n][0..n][r2];//i,j,k.工件i优先于工件j在机器k上加工
minimize max(i in r1,k in r2) c[i][k];//机器i在机器k上的完工时间
subject to{
forall(i in r1,h in r2,k in r2)
c[i][k]-p[i][k]+M*(1-a[i][h][k])>=c[i][h];//机器h优先于机器k加工工件i
forall(i in r1,j in r1,k in r2)
c[j][k]-c[i][k]+M*(1-x[i][j][k])>=p[i][k];//工件i优先于工件j在机器k上加工
forall(j in r1,k in r2)
//对于任意一台机器上的工件j，必然有一个紧前作业i
sum(i in 0..n) x[i][j][k]==1;
forall(i in r1,k in r2)
//对于任意一台机器上的工件i，必然有一个紧后作业j
sum(j in 0..n) x[i][j][k]==1;
forall(k in r2)
//对于每台机器来说，只能由一个作业位于最后
sum(i in 0..n) x[i][0][k]<=1;
forall(k in r2)
//对于每台机器来说，只能有一个作业首先加工
sum(j in 0..n) x[0][j][k]<=1;
/*************************/
forall(i in r1,k in r2)
//对于任意一个工件，必然有一个紧前工序
sum(h in 0..m) a[i][h][k]==1;
forall(i in r1,h in r2)
//对于任意一个工件，必然有一个紧后工序
sum(k in 0..m) a[i][h][k]==1;
forall(i in r1)
//对于每个工件来说，只能有一个工序处于第一位
sum(k in 0..m) a[i][0][k]<=1;
forall(i in r1)
//对于每个工件来说，只能有一个工序处于最后一位
sum(h in 0..m) a[i][h][0]<=1;
/************************/
forall(i in r1)
sum(h in 0..m,k in 0..m) temp[i][h][k]*a[i][h][k]==2;
}
execute{
writeln("每台机器上工件加工的顺序：");
for(var k in r2){
for(var i in r1){
for(var j in r1){
if(x[i][j][k]==1){
writeln(k+":"+i+"-->"+j);
}
}
}
}
writeln("每个工件的加工顺序：")
for(var i in r1){
for(var h in r2){
for(var k in r2){
if(a[i][h][k]==1){
writeln(i+":"+h+"-->"+k);
}
}
}
}
}
结果：
// solution (optimal) with objective 220
// Quality Incumbent solution:
// MILP objective 2.2000000000e+002
// MILP solution norm |x| (Total, Max) 2.58900e+003 2.20000e+002
// MILP solution error (Ax=b) (Total, Max) 0.00000e+000 0.00000e+000
// MILP x bound error (Total, Max) 0.00000e+000 0.00000e+000
// MILP x integrality error (Total, Max) 0.00000e+000 0.00000e+000
// MILP slack bound error (Total, Max) 0.00000e+000 0.00000e+000
//
c = [[0
118 31]
[87 220 62]
[148 76 0]
[220 0 97]];
a = [[[0 1 0 0]
[0 0 0 1]
[1 0 0 0]
[0 0 1 0]]
[[0 0 0 1]
[0 0 1 0]
[1 0 0 0]
[0 1 0 0]]
[[0 0 0 1]
[1 0 0 0]
[0 1 0 0]
[0 0 1 0]]
[[0 0 1 0]
[1 0 0 0]
[0 0 0 1]
[0 1 0 0]]];
x = [[[0 0 0]
[1 0 0]
[0 0 0]
[0 0 1]
[0 1 0]]
[[0 0 0]
[0 0 0]
[1 1 1]
[0 0 0]
[0 0 0]]
[[0 1 0]
[0 0 0]
[0 0 0]
[1 0 0]
[0 0 1]]
[[0 0 0]
[0 1 1]
[0 0 0]
[0 0 0]
[1 0 0]]
[[1 0 1]
[0 0 0]
[0 0 0]
[0 1 0]
[0 0 0]]];
/*----------------脚本信息---------------*/
// solution (optimal) with objective 220
每台机器上工件加工的顺序：
1:1-->2
1:2-->3
1:3-->4
2:1-->2
2:3-->1
2:4-->3
3:1-->2
3:2-->4
3:3-->1
每个工件的加工顺序：
1:1-->3
1:3-->2
2:1-->2
2:3-->1
3:2-->1
3:3-->2
4:2-->3
4:3-->1