JCL MTSP

 

What does the sample do?

The Minimization of Tool Switches Problem (MTSP) is a NP-Hard problem. According to Crama et al. (1994), the problem can be stated as follow: “A batch of jobs has to be successively processed on a single flexible machine. Each job requires a subset of tools, which have to be replaced in the machine before the job can be processed. Each tool has a limited capacity and the number of tools required to produce all the jobs exceeds this capacity. Hence, it is sometimes necessary to change the tools between two jobs in a sequence. The problem is to determine a job sequence and an associated sequence of tools switches, such that the total number of tool switches is minimized”.

The method chosen for this sample was recently presented by Paiva and Carvalho in 2016 and it is the state-of-the-art method for solving the MTSP problem. This method generates an initial solution using a new constructive heuristic based on graph search. After the initial solution is obtained, it is improved by an implementation of the traditional Iterated Local Search metaheuristic presented in Lourenço et al. (2003), “which consists of repeatedly applying local search methods and randomly modifying a solution until it reaches a stopping condition”. The stopping condition adopted was 200 iterations of the metaheuristic method. Additionaly, the local search methods implemented were the new 1-block grouping presented by Paiva and Carvalho (2016) and the classical 2-swap, which exchanges the positions of two elements of a permutation. Given n elements in a solution, the 2-swap algorithm may require all possible pairs of elements to exchange positions, thus, asymptotically it may perform up to n! operations. Since it is not feasible to perform this number of operations, the Iterated Local Search performs a limited search of 30% of the search space (i.e., up to 0.3 × n operations), where each pair of elements considered is randomly selected.

The JCL MTSP  accelerate the Iterated Local Search runs for multiple instances.

 

Attention !!!

This sample use a MTSP compiled version that run just in Linux 64bits OS. To run in other OS changes are need.

 

How do I run it?

        It is necessary, first, to load libjvm.so library. One way to load this library in ubuntu with java 8 is to execute the following command:

        It is necessary  to start a JCL cluster. Inside Host folder execute Host.sh:

To start JCL CBC you have two options:

          1. Execute in the terminal the command: java -jar MainMTSP.jar arg1

##################################
"Exec format:"
"java -jar MainMTSP.jar arg1"
"arg1: inputs path"
##################################

         2. To start JCL MTSP execute in the terminal the command: ./cmdStart.sh .

 

How do I use it?

Put all instance files inside both "Instancias" folders, one located in the root project folder (ToolsSwitch folder) and the other located inside the Host folder.

ToolsSwitch folder Host folder

The output of the execution are shown below:

User
Host
 

 

 


          After the execution, the output results are:

                     1 One "txt" file for each task with MTSP output.

                     2 A file named Tempo_dos_Inputs2.txt with MTSP execution time.

                     3 A file named Tempo_dos_Inputs3.txt with all times of a task get using getTaskTimes JCL method.

 

The C++ code of MTSP is inside "MTSP-JCL_Code" folder. If, for any reason, it is necessáry to recompile the MTSP, execute the command "make clean" and "make" to build a new MTSP bin.

 

The MTSP application use two Java class (JCLInterface and IteratedLocalSearch).  If, for any reason, it is necessáry to recompile these classes, execute the script "compile.sh".

 

 

The Figure below illustrates the MTSP in JCL, this way all Java/C++ and C++/Java iterations. The black arrows illustrate step by step the execution process and the red arrows illustrate the responses or results.

        

 

The MainMTSP class reads all MTSP instances and it creates one JCL task for each  MTSP instance.

Important lines: 

6--7 => Get JCL instance.

18 => Register tootlsS class.

23--29 => Read instance filename.

31--54 => Create one task for each instance.

56--117 => Recover the results and create output files.

public class MainMTSP {

	public MainMTSP(String[] args) throws InterruptedException, ExecutionException {		
		
		//Vars		
		JCL_CPfacade jclCP = JCL_CPFacadeImpl.getInstance();
		JCL_facade jcl = jclCP.PacuHPC;			
		List<String> fileInputName = new ArrayList<String>();
		Map<Future<JCL_result>,String> tMTSP = new HashMap<Future<JCL_result>,String>();

		String inputFilePre = args[0];
		
		try
        {			
			//Register
			System.out.println("Number of cores:"+jcl.getClusterCores());
			jcl.register(toolsS.class, "toolsS");
			Long ini = System.nanoTime();

			
			//List input			
			File[] filesDir = new File(inputFilePre).listFiles();
			for (File f:filesDir) {
			    if (f.isFile()) {
					fileInputName.add(f.getName());
			    }
			}
									
			//Execute MTSP
			System.out.println("Inicio");
			int contExec = 0;
										
				for(String name:fileInputName){
					
					ArrayList<String>  array = new ArrayList<String>();
					array.add(new String("./MTSP.exe"));
					array.add(new String("-t"));
					array.add(new String("-file=Instancias/"+name));
					array.add(new String("-method=14"));
					String[] cmd = new String[array.size()]; 
					array.toArray(cmd); 
					
					Object[] arg4 = {cmd,contExec};	
					Future<JCL_result> t = jcl.execute("toolsS","ExecTS",arg4);
					contExec++;
					tMTSP.put(t,name);
					array = null;
					cmd = null;
				}
			
			System.out.println("Call "+contExec+" executes ...");

			int cont=0;
			long soma = 0;
			PrintWriter outT2 = new PrintWriter("Tempo_dos_Inputs2.txt");
			PrintWriter outT3 = new PrintWriter("Tempo_dos_Inputs3.txt");
			
			for(Entry<Future<JCL_result>, String> t:tMTSP.entrySet()){
				JCL_result result = t.getKey().get();								
				String[] ResultCBC = (String[])result.getCorrectResult();
								
				if (ResultCBC[1].length()==0){
					PrintWriter out = new PrintWriter("Saida_"+t.getValue()+".txt");
					out.println(ResultCBC[0]);
					out.close();
				}else{
					PrintWriter out = new PrintWriter("Saida_"+t.getValue()+".txt");
					out.println(ResultCBC[1]);
					out.println(ResultCBC[0]);
					
					out.close();
				}
				try {
					soma+=Long.parseLong(ResultCBC[3]);	
					outT2.println(ResultCBC[2]+";"+ResultCBC[3]);
				} catch (Exception e) {
					// TODO: handle exception
					outT2.println("ERRO: "+t.getValue());
					e.printStackTrace();
				}
				
				try {
					List<Long> times = jclCP.getTaskTimes(t.getKey());
					outT3.print(ResultCBC[2]+";"+times.size()+";");
					for(Long ti:times){outT3.print(ti.toString()+";");}
					outT3.print(System.getProperty("line.separator"));
				} catch (Exception e) {
					// TODO: handle exception
					outT3.println("ERRO: "+t.getValue());
					e.printStackTrace();
				}

				System.out.println("Results file "+t.getValue()+" Return Name "+ResultCBC[2]+" cont:"+cont);
				outT2.flush();
				outT3.flush();
				result = null;
				ResultCBC = null;
				try {
				//	jcl.removeResult(t.getKey());
				} catch (Exception e) {
					// TODO: handle exception
					System.out.println("Erro Remove result");
					e.printStackTrace();
				}
				cont++;
			}
			
			outT2.println("Total nao Paralelo:"+soma);			
			outT2.println("Final Paralelo:"+(System.nanoTime()-ini));
			outT2.close();
			outT3.close();
			
			
			
			System.out.println("Criando arquivo de tempo");
			
			jcl.destroy();							
        }
		
		
        catch (IOException exc)
        {
            System.out.println(exc);
            System.exit(1);
        }
	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		if (args.length!=1){
			System.out.println("##################################");
			System.out.println("Exec format:");
			System.out.println("java -jar MainMTSP.jar arg1");
			System.out.println("arg1: inputs path");
			System.out.println("############## FIM ###############");
		}else{
		try {
			new MainMTSP(args);
		} catch (InterruptedException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		} catch (ExecutionException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
		}
	}
}

 

The toolsS class creates a process for the C++ application: 

 Important lines: 

7--55 => Create MTSP process.

 

public class toolsS {
	
	private List<Integer> timeCpu = Collections.synchronizedList(new ArrayList<Integer>());
	private int timeCpuMean;

	
	public String[] ExecTS(String[] cmd, int id){
		
		try {
		
			//Start Process
			System.out.println("Exec TS:"+cmd[2]);

			Long ini = System.nanoTime();
			ProcessBuilder pb = new ProcessBuilder(cmd);
			Process process = pb.start();
		
			//Read STDOut and STDErr
			BufferedReader reader = new BufferedReader(new InputStreamReader(process.getInputStream()));
			BufferedReader erro = new BufferedReader(new InputStreamReader(process.getErrorStream()));

			//Create buffer
			StringBuilder builder = new StringBuilder();
			StringBuilder builderErro = new StringBuilder();

			//Read STDOut
			String line = null;
			while ( (line = reader.readLine()) != null) {
				builder.append(line);
				builder.append(System.getProperty("line.separator"));
			}

			//Read STDErr
			line = null;
			while ( (line = erro.readLine()) != null) {
				builderErro.append(line);
				builderErro.append(System.getProperty("line.separator"));
			}
		
			process.waitFor();
			
			long time = (System.nanoTime()-ini);
			String[] result = {builder.toString(),builderErro.toString(),(cmd[2]+"_"+id),(String.valueOf(time))};
			
			System.out.println("Fim Exec "+cmd[2]+" MTSP:"+(System.nanoTime()-ini));			
			return result;

		} catch (IOException | InterruptedException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
			return null;
		}
	}
			
}

 

The MTSP.cpp creates a JVM and calls the method CreateTasks of JCLInterface class.

Important lines: 

26 => Create JVM.

29 => Load class.

36 =>  Call "CreateTasks" method.

 

			sscomando << "./MTSP.exe -t -method=3 -file=" << filePath_.c_str() <<  " -seq=" <<  ss.str().c_str();
			
			string comando = string(sscomando.str());



//			printf("%s\n", comando.c_str());
			

			//Code aded by André Luís (JCL)
			//VAR
			JavaVMOption options[1];
			JavaVMInitArgs vm_args;
			JNIEnv *env;
			JavaVM *jvm;
		

			options[0].optionString = "-Djava.class.path=./:./jclUser.jar";
//			options[1].optionString = "-Djava.library.path=./jclUser.jar";
			memset(&vm_args, 0, sizeof(vm_args));
			vm_args.version = JNI_VERSION_1_8;
   			vm_args.nOptions = 1;
   			vm_args.options = options;

			long status = JNI_CreateJavaVM(&jvm, (void**)&env, &vm_args);
//			if (status != JNI_ERR){			
//			printf("Create JVM\n");
			jclass cls = env->FindClass("JCLInterface");
//			if(cls !=0){
//				printf("Class Found\n");
			jmethodID constructor = env->GetMethodID(cls, "<init>", "()V");	
			jobject simpleJNITestInstance = env->NewObject(cls, constructor);
			jmethodID MTSP_Parallel = env->GetMethodID(cls, "CreateTasks", "(Ljava/lang/String;)Ljava/lang/String;");
			jstring jstr1 = env->NewStringUTF(comando.c_str());		
			jstring result_j = (jstring) env->CallObjectMethod(simpleJNITestInstance , MTSP_Parallel, jstr1);
			const char* str = env->GetStringUTFChars(result_j, 0);
	     		string retorno = str;
     			env->ReleaseStringUTFChars(result_j, str);

			printf("TA RETORNANDO DO JCl%s\n", retorno.c_str());
		
			
//			}
//		}

		/*End Code aded by André Luís (JCL)*/


			/*Chamar JCL aqui!*/


			//string retorno = string("2208 13.31.18.14.12.11.10.33.15.25.37.39.2.19.22.1.0.38.35.9.20.6.3.8.32.30.17.23.36.24.27.21.34.16.28.5.26.4.7.29.\n");

 

The JCLInterface class uses JCL munti-core version to make the parallel local Search.

Important lines: 

12 => Get JCL munti-core version instance.

30 => Register IteratedLocalSearch class.

36 -- 45 =>  Call "ExecILS" method. 

46 -- 103 => Recouver result and create output files.

 

public class JCLInterface
 {

   static final AtomicInteger number = new AtomicInteger(0);
   static final AtomicLong to = new AtomicLong(0);


   public String CreateTasks(String n) throws InterruptedException, ExecutionException { 
	long ini = System.nanoTime();

	//varibles started	
	JCL_facade jcl = JCL_FacadeImpl.getInstanceLambari();	
	Map<Future<JCL_result>,Integer> tMTSP = new HashMap<Future<JCL_result>,Integer>();
	PrintWriter out = null;
//	PrintWriter out3 = null;
        String menorR = null;


	try{
		out = new PrintWriter(new FileWriter("Saida_result.txt",true));
//		out3 = new PrintWriter(new FileWriter("Saida_result2.txt",true));

	}catch(IOException exc){
 		System.out.println(exc);
	}	

	//Register
	System.out.println("CMD: "+n);
	jcl.register(IteratedLocalSearch.class, "IteratedLocalSearch"); 
	
	//Comand	
	String[] cmd = n.split(" ");
	
	//Execute call
	int randC = ThreadLocalRandom.current().nextInt(4,17);
    	for(int cont=0;cont<randC;cont++){
		Object[] arg = {cmd,number.get()};	
		Future<JCL_result> t = jcl.execute("IteratedLocalSearch","ExecILS",arg);		
		tMTSP.put(t,cont);
		System.out.println("Execute local:"+cont+" Execute global:"+number.get());
		number.getAndIncrement();
	}
	
	//recover result
	int con = 0;
	int menor = 100000;

	for(Entry<Future<JCL_result>, Integer> t:tMTSP.entrySet()){
		JCL_result result = t.getKey().get();
		String[] ResultCBC = (String[])result.getCorrectResult();
		if (ResultCBC[1].length()==0){
			out.println(n+";"+t.getValue()+";"+ResultCBC[2]+";"+ResultCBC[0]);
			String[] mini = ResultCBC[0].split(" ");
			if(Integer.parseInt(mini[0]) < menor){
				menor = Integer.parseInt(mini[0]);
				System.out.println("Menor: "+menor);
				menorR = ResultCBC[0];
			}
		}else{
			System.out.println("Erro:");
			System.out.println(ResultCBC[1]);
		}
		
//		try {
//			List<Long> times = jclCP.getTaskTimes(t.getKey());
//			out3.print(ResultCBC[2]+";"+times.size()+";");
//			for(Long ti:times){out3.print(ti.toString()+";");}
//			out3.print(System.getProperty("line.separator"));
//		} catch (Exception e) {
//		// TODO: handle exception
//			out3.println("ERRO: "+t.getValue());
//			e.printStackTrace();
//		}

		System.out.println("Results file "+t.getValue()+" Return Name "+ResultCBC[2]+" cont:"+con);
		out.flush();
//		out3.flush();
		con++;

		result = null;
		ResultCBC = null;
		try {
//			jcl.removeResult(t.getKey());
		} catch (Exception e) {
		// TODO: handle exception
			System.out.println("Erro Remove result");
			e.printStackTrace();
		}

	}
	out.close();
//	out3.close();
	Long t = (System.nanoTime() - ini);
	System.out.println("Tempo current interation:"+t);
	System.out.println("Tempo total:"+to.addAndGet(t));

	return menorR;
   }

   public boolean booleanMethod(boolean bool) {
        return !bool;
   }

   public static void main (String[] arg) {
	
        JCLInterface s = new JCLInterface();
	try {
		System.out.println(s.CreateTasks("Teste"));
	} catch (InterruptedException | ExecutionException e) {
		// TODO Auto-generated catch block
		e.printStackTrace();
	}    
    }
}

 

The IteratedLocalSearch class creates the MTSP process to perform the local search.

Important lines: 

3--48 =>Create the MTSP process (local search).

 

public class IteratedLocalSearch
{
	public String[] ExecILS(String[] cmd, int id){
		
	try {		
		System.out.println("Exec MTSP:"+id);

		Long ini = System.nanoTime();
		ProcessBuilder pb = new ProcessBuilder(cmd);
		Process process = pb.start();
		
		//Read STDOut and STDErr
		BufferedReader reader = new BufferedReader(new InputStreamReader(process.getInputStream()));
		BufferedReader erro = new BufferedReader(new InputStreamReader(process.getErrorStream()));

		//Create buffer
		StringBuilder builder = new StringBuilder();
		StringBuilder builderErro = new StringBuilder();

		//Read STDOut
		String line = null;
		while ( (line = reader.readLine()) != null) {
			builder.append(line);
			builder.append(System.getProperty("line.separator"));
		}

		//Read STDErr
		line = null;
		while ( (line = erro.readLine()) != null) {
			builderErro.append(line);
			builderErro.append(System.getProperty("line.separator"));
		}
		
		process.waitFor();
			
		long time = (System.nanoTime()-ini);
		String[] result = {builder.toString(),builderErro.toString(),String.valueOf(id),(String.valueOf(time))};
			
		System.out.println("Fim Exec "+id+" MTSP:"+(System.nanoTime()-ini));			
		return result;

		} catch (IOException | InterruptedException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
			return null;
		}
	}
}

 

 

This project can be imported in eclipse IDE and all Java source files are inside "src" folder. 

 

Questions or comments, where can I go?

 

Questions about the API or about the codes of this application? See our Programming Guide and Installation Guide.

If you have any questions, please contact the JCL team.

 

Bibliography

Yves Crama, Antoon W. J. Kolen, Alwin G. Oerlemans, and Frits C. R. Spieksma. Minimizing the number of tool switches on a flexible machine. International Journal of Flexible Manufacturing Systems, 6(1):33–54, 1994. ISSN 1572-9370. doi: 10.1007/BF01324874. URL http://dx.doi.org/10.1007/BF01324874.

Gustavo Silva Paiva and Marco Antonio Moreira Carvalho. Um método para planejamento da produção em sistemas de manufatura flexível. In Simpósio Brasileiro de Pesquisa Operacional, 2016. 

Helena R Lourenço, Olivier C Martin, and Thomas Stützle. Iterated local search. In Handbook of metaheuristics, pages 320–353. Springer, 2003.