机器调度问题（JSP问题）描述为：在给定每个工件的加工流程、每个工件使用机器的序列及每个工件每道工序的加工时间确定的情况下，安排工件的加工顺序，使得待加工的工件在机器上进行加工的最大完工时刻最小。
接着上次的JSP模型（ 机器调度(JSP)问题数学模型_上善若水阳阳的博客-CSDN博客），我们给出一个具体的问题，并用java调用cplex进行求解。
我们给出各个工件加工的流程和各个工件在机器上的加工时间：
工件1工作流程：1,2,3
工件2工作流程：2,1,4,3
工件3工作流程：1,2,4
现在使用java调用cplex进行求解。
1.首先定义cplex环境变量：
IloCplex cplex1 = new IloCplex();
2.紧接着我们定义问题的决策变量。我们定义两类决策变量，一类是每个工件每道工序的最大完工时刻，另一类是使用同一台机器加工不同工件的先后顺序。
每个工件每道工序的最大完工时刻：对于第i个工件被第k台机器加工，我们定义决策变量为。
//定义决策变量 IloNumVar c11 = cplex1.numVar(0, Double.MAX_VALUE); IloNumVar c21 = cplex1.numVar(0, Double.MAX_VALUE); IloNumVar c31 = cplex1.numVar(0, Double.MAX_VALUE); IloNumVar c22 = cplex1.numVar(0, Double.MAX_VALUE); IloNumVar c12 = cplex1.numVar(0, Double.MAX_VALUE); IloNumVar c42 = cplex1.numVar(0, Double.MAX_VALUE); IloNumVar c32 = cplex1.numVar(0, Double.MAX_VALUE); IloNumVar c13 = cplex1.numVar(0, Double.MAX_VALUE); IloNumVar c23 = cplex1.numVar(0, Double.MAX_VALUE); IloNumVar c43 = cplex1.numVar(0, Double.MAX_VALUE);
同一台机器加工不同工件的先后顺序：第k台机器加工第i和第j个工件，如果机器k先加工第i个工件，紧接着加工第j个工件，我们定义决策变量为。为方便数学模型建立，同时对每一台机器虚拟一个初始工件0和最后加工的工件M。
//定义决策变量 IloNumVar x011 = cplex1.intVar(0, 1); IloNumVar x021 = cplex1.intVar(0, 1); IloNumVar x031 = cplex1.intVar(0, 1); IloNumVar x121 = cplex1.intVar(0, 1); IloNumVar x131 = cplex1.intVar(0, 1); IloNumVar x1M1 = cplex1.intVar(0, 1); IloNumVar x211 = cplex1.intVar(0, 1); IloNumVar x231 = cplex1.intVar(0, 1); IloNumVar x2M1 = cplex1.intVar(0, 1); IloNumVar x311 = cplex1.intVar(0, 1); IloNumVar x321 = cplex1.intVar(0, 1); IloNumVar x3M1 = cplex1.intVar(0, 1); IloNumVar x012 = cplex1.intVar(0, 1); IloNumVar x022 = cplex1.intVar(0, 1); IloNumVar x032 = cplex1.intVar(0, 1); IloNumVar x122 = cplex1.intVar(0, 1); IloNumVar x132 = cplex1.intVar(0, 1); IloNumVar x1M2 = cplex1.intVar(0, 1); IloNumVar x212 = cplex1.intVar(0, 1); IloNumVar x232 = cplex1.intVar(0, 1); IloNumVar x2M2 = cplex1.intVar(0, 1); IloNumVar x312 = cplex1.intVar(0, 1); IloNumVar x322 = cplex1.intVar(0, 1); IloNumVar x3M2 = cplex1.intVar(0, 1); IloNumVar x013 = cplex1.intVar(0, 1); IloNumVar x023 = cplex1.intVar(0, 1); IloNumVar x123 = cplex1.intVar(0, 1); IloNumVar x1M3 = cplex1.intVar(0, 1); IloNumVar x213 = cplex1.intVar(0, 1); IloNumVar x2M3 = cplex1.intVar(0, 1); IloNumVar x024 = cplex1.intVar(0, 1); IloNumVar x034 = cplex1.intVar(0, 1); IloNumVar x234 = cplex1.intVar(0, 1); IloNumVar x2M4 = cplex1.intVar(0, 1); IloNumVar x324 = cplex1.intVar(0, 1); IloNumVar x3M4 = cplex1.intVar(0, 1);
3.定义目标函数
这里我们考虑最小化最大完工时间，考虑将每一个工件的最后一道工序的完工时间最小化，在本问题中即最小化c31,c32,c43中的最大值，minimize max{c31,c32,c43}。
//定义目标函数 IloNumExpr obj = cplex1.numExpr(); IloNumExpr c = cplex1.intVar(0, (int) Double.MAX_VALUE); cplex1.addGe(c,c31); cplex1.addGe(c,c32); cplex1.addGe(c,c43); obj = cplex1.sum(obj,cplex1.prod(c, 1)); cplex1.addMinimize(obj);
4.约束条件
首先定义约束：
//约束条件 IloNumExpr cs1 = cplex1.numExpr(); IloNumExpr cs2 = cplex1.numExpr(); IloNumExpr cs3 = cplex1.numExpr(); IloNumExpr cs4 = cplex1.numExpr(); IloNumExpr cs5 = cplex1.numExpr(); IloNumExpr cs6 = cplex1.numExpr(); IloNumExpr cs7 = cplex1.numExpr(); IloNumExpr cs8 = cplex1.numExpr(); IloNumExpr cs9 = cplex1.numExpr(); IloNumExpr cs10 = cplex1.numExpr(); IloNumExpr cs11= cplex1.numExpr(); IloNumExpr cs12 = cplex1.numExpr(); IloNumExpr cs13 = cplex1.numExpr(); IloNumExpr cs14 = cplex1.numExpr(); IloNumExpr cs15 = cplex1.numExpr(); IloNumExpr cs16 = cplex1.numExpr(); IloNumExpr cs17 = cplex1.numExpr(); IloNumExpr cs18 = cplex1.numExpr(); IloNumExpr cs19 = cplex1.numExpr(); IloNumExpr cs20 = cplex1.numExpr(); IloNumExpr cs21 = cplex1.numExpr(); IloNumExpr cs22 = cplex1.numExpr(); IloNumExpr cs23 = cplex1.numExpr(); IloNumExpr cs24 = cplex1.numExpr(); IloNumExpr cs25 = cplex1.numExpr(); IloNumExpr cs26 = cplex1.numExpr(); IloNumExpr cs27 = cplex1.numExpr(); IloNumExpr cs28 = cplex1.numExpr(); IloNumExpr cs29 = cplex1.numExpr(); IloNumExpr cs30 = cplex1.numExpr(); IloNumExpr cs31 = cplex1.numExpr(); IloNumExpr cs32 = cplex1.numExpr(); IloNumExpr cs33 = cplex1.numExpr(); IloNumExpr cs34 = cplex1.numExpr(); IloNumExpr cs35 = cplex1.numExpr(); IloNumExpr cs36 = cplex1.numExpr(); IloNumExpr cs37 = cplex1.numExpr(); IloNumExpr cs38 = cplex1.numExpr(); IloNumExpr cs39 = cplex1.numExpr(); IloNumExpr cs40 = cplex1.numExpr(); IloNumExpr cs41 = cplex1.numExpr(); IloNumExpr cs42 = cplex1.numExpr(); IloNumExpr cs43 = cplex1.numExpr(); IloNumExpr cs44 = cplex1.numExpr(); IloNumExpr cs45 = cplex1.numExpr(); IloNumExpr cs46 = cplex1.numExpr(); IloNumExpr cs47 = cplex1.numExpr(); IloNumExpr cs48 = cplex1.numExpr(); IloNumExpr cs49 = cplex1.numExpr(); IloNumExpr cs50 = cplex1.numExpr(); IloNumExpr cs51 = cplex1.numExpr(); IloNumExpr cs52 = cplex1.numExpr(); IloNumExpr cs53 = cplex1.numExpr(); IloNumExpr cs54 = cplex1.numExpr();
流程约束条件（每一个工件第一道工序的完工时间大于等于工件第一道工序的加工时间）：
cs1 = cplex1.sum(cs1,cplex1.prod(c11,1)); cs2 = cplex1.sum(cs2,cplex1.prod(c22,1)); cs3 = cplex1.sum(cs3,cplex1.prod(c13,1));
每一个工件的流程：
//工件1的流程
cs4 = cplex1.sum(cs4,cplex1.prod(c21,1));
cs4 = cplex1.sum(cs4,cplex1.prod(c11,-1));
cs5 = cplex1.sum(cs5,cplex1.prod(c31, 1));
cs5 = cplex1.sum(cs5,cplex1.prod(c21, -1));
//工件2的流程
cs6 = cplex1.sum(cs6,cplex1.prod(c12, 1));
cs6 = cplex1.sum(cs6,cplex1.prod(c22, -1));
cs7 = cplex1.sum(cs7,cplex1.prod(c42, 1));
cs7 = cplex1.sum(cs7,cplex1.prod(c12, -1));
cs8 = cplex1.sum(cs8,cplex1.prod(c32, 1));
cs8 = cplex1.sum(cs8,cplex1.prod(c42, -1));
//工件3的流程
cs9 = cplex1.sum(cs9,cplex1.prod(c23, 1));
cs9 = cplex1.sum(cs9,cplex1.prod(c13, -1));
cs10 = cplex1.sum(cs10,cplex1.prod(c43, 1));
cs10 = cplex1.sum(cs10,cplex1.prod(c23, -1));
//备注：括号内逗号后的数字分别表示每一道工序的加工时间
cplex1.addGe(cs1,10);
cplex1.addGe(cs2,8);
cplex1.addGe(cs3,4);
cplex1.addGe(cs4,8);
cplex1.addGe(cs5,4);
cplex1.addGe(cs6,3);
cplex1.addGe(cs7,5);
cplex1.addGe(cs8,6);
cplex1.addGe(cs9,7);
cplex1.addGe(cs10,3);
同一台机器加工不同零件先后顺序的约束条件：
- (1,1),(1,2),(1,3)构成的三角形流程
//机器加工顺序约束条件
//(1,1),(1,2),(1,3)构成的三角形流程
//虚拟的开始工件0
cs11 = cplex1.sum(cs11,cplex1.prod(x011,1));
cs11 = cplex1.sum(cs11,cplex1.prod(x021,1));
cs11 = cplex1.sum(cs11,cplex1.prod(x031,1));
cplex1.addEq(cs11,1);
//虚拟的结束工件M
cs12 = cplex1.sum(cs12,cplex1.prod(x1M1,1));
cs12 = cplex1.sum(cs12,cplex1.prod(x2M1,1));
cs12 = cplex1.sum(cs12,cplex1.prod(x3M1,1));
cplex1.addEq(cs12,1);
//每一个中间节点只有一个紧前工序和一个紧后工序
cs13 = cplex1.sum(cs13,cplex1.prod(x011,1));
cs13 = cplex1.sum(cs13,cplex1.prod(x211,1));
cs13 = cplex1.sum(cs13,cplex1.prod(x311,1));
cs14 = cplex1.sum(cs14,cplex1.prod(x121,1));
cs14 = cplex1.sum(cs14,cplex1.prod(x131,1));
cs14 = cplex1.sum(cs14,cplex1.prod(x1M1,1));
cplex1.addEq(cs13,1);
cplex1.addEq(cs14,1);
cs15 = cplex1.sum(cs15,cplex1.prod(x021,1));
cs15 = cplex1.sum(cs15,cplex1.prod(x121,1));
cs15 = cplex1.sum(cs15,cplex1.prod(x321,1));
cs16 = cplex1.sum(cs16,cplex1.prod(x211,1));
cs16 = cplex1.sum(cs16,cplex1.prod(x231,1));
cs16 = cplex1.sum(cs16,cplex1.prod(x2M1,1));
cplex1.addEq(cs15,1);
cplex1.addEq(cs16,1);
cs17 = cplex1.sum(cs17,cplex1.prod(x031,1));
cs17 = cplex1.sum(cs17,cplex1.prod(x231,1));
cs17 = cplex1.sum(cs17,cplex1.prod(x131,1));
cs18 = cplex1.sum(cs18,cplex1.prod(x311,1));
cs18 = cplex1.sum(cs18,cplex1.prod(x321,1));
cs18 = cplex1.sum(cs18,cplex1.prod(x3M1,1));
cplex1.addEq(cs17,1);
cplex1.addEq(cs18,1);
//紧前工序的完工时刻加上紧后工序的加工时间小于等于紧后工序的完工时刻
cs19 = cplex1.sum(cs19,cplex1.prod(c11,1));
cs19 = cplex1.sum(cs19,cplex1.prod(c12,-1));
cs19 = cplex1.sum(cs19,cplex1.prod(x121,1000));
cplex1.addLe(cs19,1000-3);
cs20 = cplex1.sum(cs20,cplex1.prod(c12,1));
cs20 = cplex1.sum(cs20,cplex1.prod(c11,-1));
cs20 = cplex1.sum(cs20,cplex1.prod(x211,1000));
cplex1.addLe(cs20,1000-10);
cs21 = cplex1.sum(cs21,cplex1.prod(c11,1));
cs21 = cplex1.sum(cs21,cplex1.prod(c13,-1));
cs21 = cplex1.sum(cs21,cplex1.prod(x131,1000));
cplex1.addLe(cs21,1000-4);
cs22 = cplex1.sum(cs22,cplex1.prod(c13,1));
cs22 = cplex1.sum(cs22,cplex1.prod(c11,-1));
cs22 = cplex1.sum(cs22,cplex1.prod(x311,1000));
cplex1.addLe(cs22,1000-10);
cs23 = cplex1.sum(cs23,cplex1.prod(c12,1));
cs23 = cplex1.sum(cs23,cplex1.prod(c13,-1));
cs23 = cplex1.sum(cs23,cplex1.prod(x231,1000));
cplex1.addLe(cs23,1000-4);
cs24 = cplex1.sum(cs24,cplex1.prod(c13,1));
cs24 = cplex1.sum(cs24,cplex1.prod(c12,-1));
cs24 = cplex1.sum(cs24,cplex1.prod(x321,1000));
cplex1.addLe(cs24,1000-3);
- (2,1),(2,2),(2,3)构成的三角形流程
//(2,1),(2,2),(2,3)构成的三角形流程
//虚拟的开始工件0
cs25 = cplex1.sum(cs25,cplex1.prod(x012,1));
cs25 = cplex1.sum(cs25,cplex1.prod(x022,1));
cs25 = cplex1.sum(cs25,cplex1.prod(x032,1));
cplex1.addEq(cs25,1);
//虚拟的结束工件M
cs26 = cplex1.sum(cs26,cplex1.prod(x1M2,1));
cs26 = cplex1.sum(cs26,cplex1.prod(x2M2,1));
cs26 = cplex1.sum(cs26,cplex1.prod(x3M2,1));
cplex1.addEq(cs26,1);
//每一个中间节点只有一个紧前工序和一个紧后工序
cs27 = cplex1.sum(cs27,cplex1.prod(x012,1));
cs27 = cplex1.sum(cs27,cplex1.prod(x212,1));
cs27 = cplex1.sum(cs27,cplex1.prod(x312,1));
cs28 = cplex1.sum(cs28,cplex1.prod(x122,1));
cs28 = cplex1.sum(cs28,cplex1.prod(x132,1));
cs28 = cplex1.sum(cs28,cplex1.prod(x1M2,1));
cplex1.addEq(cs27,1);
cplex1.addEq(cs28,1);
cs29 = cplex1.sum(cs29,cplex1.prod(x022,1));
cs29 = cplex1.sum(cs29,cplex1.prod(x122,1));
cs29 = cplex1.sum(cs29,cplex1.prod(x322,1));
cs30 = cplex1.sum(cs30,cplex1.prod(x212,1));
cs30 = cplex1.sum(cs30,cplex1.prod(x232,1));
cs30 = cplex1.sum(cs30,cplex1.prod(x2M2,1));
cplex1.addEq(cs29,1);
cplex1.addEq(cs30,1);
cs31 = cplex1.sum(cs31,cplex1.prod(x032,1));
cs31 = cplex1.sum(cs31,cplex1.prod(x232,1));
cs31 = cplex1.sum(cs31,cplex1.prod(x132,1));
cs32 = cplex1.sum(cs32,cplex1.prod(x312,1));
cs32 = cplex1.sum(cs32,cplex1.prod(x322,1));
cs32 = cplex1.sum(cs32,cplex1.prod(x3M2,1));
cplex1.addEq(cs31,1);
cplex1.addEq(cs32,1);
//紧前工序的完工时刻加上紧后工序的加工时间小于等于紧后工序的完工时刻
cs33 = cplex1.sum(cs33,cplex1.prod(c21,1));
cs33 = cplex1.sum(cs33,cplex1.prod(c22,-1));
cs33 = cplex1.sum(cs33,cplex1.prod(x122,1000));
cplex1.addLe(cs33,1000-8);
cs34 = cplex1.sum(cs34,cplex1.prod(c22,1));
cs34 = cplex1.sum(cs34,cplex1.prod(c21,-1));
cs34 = cplex1.sum(cs34,cplex1.prod(x212,1000));
cplex1.addLe(cs34,1000-8);
cs35 = cplex1.sum(cs35,cplex1.prod(c21,1));
cs35 = cplex1.sum(cs35,cplex1.prod(c23,-1));
cs35 = cplex1.sum(cs35,cplex1.prod(x132,1000));
cplex1.addLe(cs35,1000-7);
cs36 = cplex1.sum(cs36,cplex1.prod(c23,1));
cs36 = cplex1.sum(cs36,cplex1.prod(c21,-1));
cs36 = cplex1.sum(cs36,cplex1.prod(x312,1000));
cplex1.addLe(cs36,10000-8);
cs37 = cplex1.sum(cs37,cplex1.prod(c22,1));
cs37 = cplex1.sum(cs37,cplex1.prod(c23,-1));
cs37 = cplex1.sum(cs37,cplex1.prod(x232,1000));
cplex1.addLe(cs37,1000-7);
cs38 = cplex1.sum(cs38,cplex1.prod(c23,1));
cs38 = cplex1.sum(cs38,cplex1.prod(c22,-1));
cs38 = cplex1.sum(cs38,cplex1.prod(x322,1000));
cplex1.addLe(cs38,1000-8);
- (3,1),(3,2)构成的流程
//(3,1),(3,2)构成的流程
//虚拟的开始工件0
cs39 = cplex1.sum(cs39,cplex1.prod(x013,1));
cs39 = cplex1.sum(cs39,cplex1.prod(x023,1));
cplex1.addEq(cs39,1);
//虚拟的结束工件0
cs40 = cplex1.sum(cs26,cplex1.prod(x1M3,1));
cs40 = cplex1.sum(cs26,cplex1.prod(x2M3,1));
cplex1.addEq(cs40,1);
//每一个中间节点只有一个紧前工序和一个紧后工序
cs41 = cplex1.sum(cs41,cplex1.prod(x013,1));
cs41 = cplex1.sum(cs41,cplex1.prod(x213,1));
cs42 = cplex1.sum(cs42,cplex1.prod(x123,1));
cs42 = cplex1.sum(cs42,cplex1.prod(x1M3,1));
cplex1.addEq(cs41,1);
cplex1.addEq(cs42,1);
cs43 = cplex1.sum(cs43,cplex1.prod(x023,1));
cs43 = cplex1.sum(cs43,cplex1.prod(x123,1));
cs44 = cplex1.sum(cs44,cplex1.prod(x213,1));
cs44 = cplex1.sum(cs44,cplex1.prod(x2M3,1));
cplex1.addEq(cs43,1);
cplex1.addEq(cs44,1);
//紧前工序的完工时刻加上紧后工序的加工时间小于等于紧后工序的完工时刻
cs45 = cplex1.sum(cs45,cplex1.prod(c31,1));
cs45 = cplex1.sum(cs45,cplex1.prod(c32,-1));
cs45 = cplex1.sum(cs45,cplex1.prod(x123,1000));
cplex1.addLe(cs45,1000-6);
cs46 = cplex1.sum(cs46,cplex1.prod(c32,1));
cs46 = cplex1.sum(cs46,cplex1.prod(c31,-1));
cs46 = cplex1.sum(cs46,cplex1.prod(x213,1000));
cplex1.addLe(cs36,1000-4);
- (4,2),(4,3)构成的流程
//(4,2),(4,3)构成的流程 //虚拟的开始工件0 cs47 = cplex1.sum(cs47,cplex1.prod(x024,1)); cs47 = cplex1.sum(cs47,cplex1.prod(x034,1)); cplex1.addEq(cs47,1); //虚拟的结束工件0 cs48 = cplex1.sum(cs48,cplex1.prod(x2M4,1)); cs48 = cplex1.sum(cs48,cplex1.prod(x3M4,1)); cplex1.addEq(cs48,1); //每一个中间节点只有一个紧前工序和一个紧后工序 cs49 = cplex1.sum(cs49,cplex1.prod(x024,1)); cs49 = cplex1.sum(cs49,cplex1.prod(x324,1)); cs50 = cplex1.sum(cs50,cplex1.prod(x234,1)); cs50 = cplex1.sum(cs50,cplex1.prod(x2M4,1)); cplex1.addEq(cs49,1); cplex1.addEq(cs50,1); cs51 = cplex1.sum(cs51,cplex1.prod(x034,1)); cs51 = cplex1.sum(cs51,cplex1.prod(x234,1)); cs52 = cplex1.sum(cs52,cplex1.prod(x324,1)); cs52 = cplex1.sum(cs52,cplex1.prod(x3M4,1)); cplex1.addEq(cs51,1); cplex1.addEq(cs52,1); //紧前工序的完工时刻加上紧后工序的加工时间小于等于紧后工序的完工时刻 cs53 = cplex1.sum(cs53,cplex1.prod(c42,1)); cs53 = cplex1.sum(cs53,cplex1.prod(c43,-1)); cs53 = cplex1.sum(cs53,cplex1.prod(x234,1000)); cplex1.addLe(cs53,1000-3); cs54 = cplex1.sum(cs54,cplex1.prod(c43,1)); cs54 = cplex1.sum(cs54,cplex1.prod(c42,-1)); cs54 = cplex1.sum(cs54,cplex1.prod(x324,1000)); cplex1.addLe(cs54,1000-5);
5.求解
//求解
if(cplex1.solve()) {
cplex1.output().println("Solution status = " + cplex1.getStatus());
cplex1.output().println("Solution value = " + cplex1.getObjValue());
double val1 = cplex1.getValue(x121);
double val2 = cplex1.getValue(x211);
double val3 = cplex1.getValue(x131);
double val4 = cplex1.getValue(x311);
double val5 = cplex1.getValue(x231);
double val6 = cplex1.getValue(x321);
double val7 = cplex1.getValue(x122);
double val8 = cplex1.getValue(x212);
double val9 = cplex1.getValue(x132);
double val10 = cplex1.getValue(x312);
double val11 = cplex1.getValue(x232);
double val12 = cplex1.getValue(x322);
double val13 = cplex1.getValue(x123);
double val14 = cplex1.getValue(x213);
double val15 = cplex1.getValue(x234);
double val16 = cplex1.getValue(x324);
System.out.println("x121="+val1);
System.out.println("x211="+val2);
System.out.println("x131="+val3);
System.out.println("x311="+val4);
System.out.println("x231="+val5);
System.out.println("x321="+val6);
System.out.println("x122="+val7);
System.out.println("x212="+val8);
System.out.println("x132="+val9);
System.out.println("x312="+val10);
System.out.println("x232="+val11);
System.out.println("x322="+val12);
System.out.println("x123="+val13);
System.out.println("x213="+val14);
System.out.println("x234="+val15);
System.out.println("x324="+val16);
}
cplex1.end();
