Job Shop Problem（机器调度问题）java代码实现

在之前的两篇文章中我们建立了JSP问题的数学模型(机器调度(JSP)问题数学模型)和使用java调用cplex求解JSP问题(JSP（机器调度问题）使用java进行数学建模并调用cplex求解)。本篇文章将使用java编程语言给出更一般的JSP模型的代码，使得可以从键盘输入任意数据进行求解。

首先我们给出JSP问题的数学模型：

我们将从键盘上依次输入以下信息：工件的个数，机器的个数，每个工件的工序（即在哪些机器上面加工），每个工件的加工时间。

因为需要从键盘输入，所以我们需要创建一个Scanner对象：

//创建一个sc对象
Scanner sc = new Scanner(System.in);

现在编写从键盘输入工件数量和机器数量的代码：

//输入工件数量capacity
System.out.println("请输入工件的数量：");
int capacity = sc.nextInt();
		
//输入机器数量numberOfMachine
System.out.println("请输入机器的数量：");
int numberOfMachine = sc.nextInt();

然后我们需要从键盘输入每个工件的工序。为了使JSP的数学模型转换成图的模型（每一个工序代表图上的一个顶点），以及方便后续边的集合创建，所以我们准备将所有的工序按照工件来划分。由于数组在定义的时候需要确定数组的长度，而JSP问题的一般模型可能是不确定长度的，因此我们使用List，这里需要使用List嵌套。我们来定义与工序相关的一些集合，如每道工序的加工机器，每道工序的加工时间，以及按照每个工件来进行划分的工序集合。

//将工序按机器进行划分
List<List<Integer>> machine = new ArrayList<>();
//定义加工时间，从键盘输入
List<List<Integer>> processedTime = new ArrayList<>();
//定义按照工件划分的点集合
List<List<Vertex>> vertexSetOfAll = new ArrayList<>();

现在开始编写从键盘上开始输入数据的代码，由于从键盘上面输入的是字符串类型的数据，我们要将其转换成为int整数型的数据，以方便后续的调用以及使用。为确保输入数据的正确性，我们将每一组数据输入后进行打印，方便我们确认数据输入的正确性。

//输入每个工件的工序，即输入工件在各个工序上加工的机器
int i = 1;
while(i <= capacity) {
	System.out.println("请以数组的形式输入第"+i+"个工件的流程,并用逗号隔开：");
	String str = sc.next();
	String arrProcess[] = str.split(",");//将输入的数组按逗号分隔开
	int strArrLen = arrProcess.length;
	int[] intArrProcess = new int[strArrLen];//定义intArrProcess数组，方便后续取出元素
			
			
    //定义按照工件划分的点集合vertexSet
    List<Vertex> vertexSet = new ArrayList<>();//创建按工件划分的工序（点）集合
    for(int a = 0; a < strArrLen; a++) {
	    Vertex v = new Vertex();
	    vertexSet.add(v);//向vertexSet中添加元素
	    graph.UJMid.add(v);//向UJMid中添加元素
    }
    vertexSetOfAll.add(vertexSet);//向vertexSetOfAll中添加元素
		
			
    for(int a = 0; a < strArrLen; a++) {
	    try {
		    intArrProcess[a] = Integer.parseInt(arrProcess[a]);
	    }catch (NumberFormatException e) {
		    e.printStackTrace();
		    return;
	     }
    }
			
    //将数组转换为List类型	
    ArrayList<Integer> list = new ArrayList<>();
    for(int j = 0;j < intArrProcess.length; j++) {
	    list.add(intArrProcess[j]);
    }
    System.out.println(" ");
    i++;
    System.out.println(list);
    machine.add(list);
}
System.out.println(machine);//工件1从0开始，依次为0，1，2，3……

类似的，我们输入各个工件的加工时间，代码如下：

//输入每个工件的加工时间
int j = 1;
while(j <= capacity) {
	System.out.println("请按顺序以数组的形式输入第"+j+"个工件的加工时间,并用逗号隔开：");
	String str = sc.next();
	String arrProcessedTime[] = str.split(",");//将输入的数组按逗号分隔开
	int strArrLen = arrProcessedTime.length;
	int[] intArrProcessTime = new int[strArrLen];//定义intArrProcess数组，方便后续取出元素
	for(int a = 0; a < strArrLen; a++) {
		try {
			intArrProcessTime[a] = Integer.parseInt(arrProcessedTime[a]);
		}catch (NumberFormatException e) {
			e.printStackTrace();
			return;
		}
	}
    //将数组转换为List类型
	ArrayList<Integer> list = new ArrayList<>();
	for(int k = 0;k < arrProcessedTime.length; k++) {
	    list.add(intArrProcessTime[k]);
	}
	j++;
	System.out.println(list);
	processedTime.add(list);
}	
System.out.println(processedTime);//工件1从0开始，依次为0，1，2，3……
		

然后我们按照各个工件的加工工序，来定义实线弧集合。为确保我们输入数据的正确性，我们在本代码段结尾处打印实线弧集合的大小：

//定义实现弧集合EI
for(List<Vertex> vertexOfSet : vertexSetOfAll) {
	for(int a = 0; a < vertexOfSet.size()-1; a++) {  //注意：边的数目是顶点的数目减1
		Edge e = new Edge();//定义实线边
		e.head = vertexOfSet.get(a+1);//定义边的头顶点
		e.tail =  vertexOfSet.get(a);//定义边的尾顶点
		graph.EI.add(e);//向EI中添加实线边			
	}
}
System.out.println("实线弧集合的大小为"+graph.EI.size());//输出EI的大小

现在我们给每一道工序（即工序对应的顶点）添加加工时间和所使用的机器：

//给每个顶点赋予machine和processedTime两个值
for(int a = 0; a < vertexSetOfAll.size(); a++) {
	for(int b = 0; b < vertexSetOfAll.get(a).size(); b++) {
		vertexSetOfAll.get(a).get(b).machine = machine.get(a).get(b);
		vertexSetOfAll.get(a).get(b).processedTime = processedTime.get(a).get(b);
	}
}

为定义对于每一台机器所有加工工序的之间待求的弧，我们需要将在同一台机器上加工的工序(点）组成新的集合，使得新的集合是按照机器来划分的。同样的，我们使用List嵌套来创建集合。

//定义MachineSetOfAll，将在同一台机器上完成的工序组成新的集合
List<List<Vertex>> MachineSetOfAll = new ArrayList<>();//使用List嵌套创建新的集合
for(int a = 1; a <= numberOfMachine; a++) {
	List<Vertex> MachineSet = new ArrayList<>();//创建在同一台机器上加工工序的集合
	for(Vertex v : graph.UJMid) {
		if(v.machine == a) {
			MachineSet.add(v);//将工序（点）添加到集合中
		}
	}
	MachineSetOfAll.add(MachineSet);
}

现在我们向属于同一个机器里的工序添加虚线弧A1：

//向属于同一个机器里的工序添加虚线弧A1
for(int a = 0 ; a < MachineSetOfAll.size(); a++) {
	for(int b = 0 ; b < MachineSetOfAll.get(a).size(); b++) {
		for(int c = 0 ; c < MachineSetOfAll.get(a).size(); c++) {
			while(!(b == c)) {
				Edge e = new Edge();
				e.head = MachineSetOfAll.get(a).get(b);
				e.tail = MachineSetOfAll.get(a).get(c);
				graph.A1.add(e);
				graph.A2.add(e);
				break;
			}
		}
	}
}
System.out.println("虚线弧集合A1的大小为"+graph.A1.size());//输出虚线弧集合A的大小

开始向属于同一个机器里的工序添加UJIN和UJOUT：

//向属于同一个机器里的工序添加UJIN和UJOUT
for(int a = 0 ; a < MachineSetOfAll.size(); a++) {
	Vertex v0 = new Vertex();
	Vertex vM = new Vertex();
	for(int b = 0 ; b < MachineSetOfAll.get(a).size(); b++) {
		Edge e = new Edge();//虚拟的开始弧
		Edge w = new Edge();//虚拟的结束弧
		e.head = MachineSetOfAll.get(a).get(b);
		e.tail = v0;
		w.head = vM;
		w.tail = MachineSetOfAll.get(a).get(b);
		v0.flowOutEdges.add(e);
		vM.flowInEdges.add(w);
		graph.A2.add(e);
		graph.A2.add(w);
	}
	graph.UJIN.add(vM);
	graph.UJOUT.add(v0);
}
System.out.println("加入虚拟开始和结束顶点后虚线弧集合A2的大小为"+graph.A2.size());//输出虚线弧集合A的大小

给所有实际工序（实际的点）添加流入边集合和流出边集合：

//给所有中间点添加流入边集合
for(Edge e : graph.A2) {
	for(Vertex v : graph.UJMid) {
		if(e.head == v) {
		    v.flowInEdges.add(e);
		}
	}
}
//给所有中间点添加流出边集合
for(Edge e : graph.A2) {
	for(Vertex v : graph.UJMid) {
		if(e.tail == v) {
			v.flowOutEdges.add(e);
		}
	}
}

现在我们调用cplex进行求解

下面的链接是：使用java进行对JSP问题数学建模，分析并调用cplex求解的文章
JSP（机器调度问题）使用java进行数学建模并调用cplex求解https://blog.csdn.net/whq002/article/details/126050391