约束满足问题(Constraint Satisfaction Problem, CSP)的Java实现（五）工作安排问题Job constraint problem

约束满足问题(Constraint Satisfaction Problem, CSP)的Java实现（五）工作安排问题Job constraint problem

工作约束定义

import java.util.List;public class JobShopConstraint extends AbstractConstraint{int durationTime;int durationTime1;int durationTime2;String type = "default";public JobShopConstraint(List vars, int time, String targetType){variableList = vars;durationTime = time;type = targetType;}public JobShopConstraint(List vars, int time1, int time2, String targetType){variableList = vars;durationTime1 = time1;durationTime2 = time2;type = targetType;}@Overrideboolean satisfied(AbstractAssignment assignment){String day1 = variableList.get(0);String day2 = variableList.get(1);if(!assignment.hasVariable(day1)||(!assignment.hasVariable(day2))){return true;}int T1 = assignment.getDomain(variableList.get(0));int T2 = assignment.getDomain(variableList.get(1));if(type.equals("default")){return T1 + durationTime <= T2;}else{return (T1 + durationTime1 <= T2) || (T2 + durationTime2 <= T1);}}
}

测试类

import java.util.*;public class JobShopConstraintTest {public static void main(String[] args) throws Exception {List variables = new ArrayList<>(Arrays.asList("J1", "J2", "J3", "J4", "J5", "J6", "J7"));Map> domains = new HashMap<>();for(int i=0;i());for(int j=0;j<5;j++){domains.get(variables.get(i)).add(j+i*4);}}BaseCSP csp = new BaseCSP<>(variables, domains);csp.addConstraint(new JobShopConstraint(new ArrayList(Arrays.asList("J1","J2")), 5, "default"));csp.addConstraint(new JobShopConstraint(new ArrayList(Arrays.asList("J2","J3")), 5, "default"));csp.addConstraint(new JobShopConstraint(new ArrayList(Arrays.asList("J3","J4")), 5, "default"));csp.addConstraint(new JobShopConstraint(new ArrayList(Arrays.asList("J4","J5")), 5, "default"));csp.addConstraint(new JobShopConstraint(new ArrayList(Arrays.asList("J5","J6")), 5, "default"));csp.addConstraint(new JobShopConstraint(new ArrayList(Arrays.asList("J6","J7")), 5, "default"));AbstractAssignment ass = csp.backTrackingSearch();if (ass != null) {ass.display();}else{System.out.println("No solution!");}}
}

import java.io.File;
import java.io.FileNotFoundException;
import java.util.*;public class JobTestClass {public static void main(String[] args) throws Exception {String fileName = "Job.txt";File file = new File(fileName);List fileString = new ArrayList<>();try {Scanner sc = new Scanner(file);while (sc.hasNextLine()) {fileString.add(sc.nextLine());}sc.close();}catch (FileNotFoundException e) {e.printStackTrace();}if(fileString.size()==0){System.out.println("NO DATA FOUND IN THE FILE!");return;}List variables = new ArrayList<>();Map durations = new HashMap<>();List domains = new ArrayList<>();Map> variableDomains = new HashMap<>();List jobShopConstraints = new ArrayList<>();int start = 0;int maxDuration = 0;boolean startGetOtherConstraints = false;for(int i=1;i wordList = new ArrayList<>(Arrays.asList(fileString.get(i).split(" ")));if(!variables.contains(wordList.get(0))){int temp = 0;try {temp = Integer.parseInt(wordList.get(0));}catch (NumberFormatException e){e.printStackTrace();}maxDuration = temp;startGetOtherConstraints = true;//update variable domainsfor(String variable:variables){variableDomains.put(variable,new ArrayList<>());for(int k=start;k<=maxDuration-durations.get(variable);k++){variableDomains.get(variable).add(k);}}}if(!startGetOtherConstraints){int temp = 0;try {temp = Integer.parseInt(wordList.get(1));}catch (NumberFormatException e){e.printStackTrace();}durations.put(wordList.get(0), temp);}}else{List wordList = new ArrayList<>(Arrays.asList(fileString.get(i).split(" ")));if(wordList.get(1).equals("before")){JobShopConstraint constraint = new JobShopConstraint(new ArrayList<>(Arrays.asList(wordList.get(0), wordList.get(2))),durations.get(wordList.get(0)), "default");jobShopConstraints.add(constraint);}else{JobShopConstraint constraint = new JobShopConstraint(new ArrayList<>(Arrays.asList(wordList.get(0), wordList.get(2))),durations.get(wordList.get(0)), durations.get(wordList.get(2)), "disjoint");jobShopConstraints.add(constraint);}}}
//        BaseCSP csp = new BaseCSP<>(variables, variableDomains);
//        SimpleCSP csp = new SimpleCSP<>(variables, variableDomains);ClassicCSP csp = new ClassicCSP<>(variables, variableDomains);csp.addOderAlgorithm(new MRV<>());csp.addOderAlgorithm(new DegreeHeuristic<>());csp.addInferenceAlgorithm(new AC3<>());for(JobShopConstraint jobShopConstraint:jobShopConstraints){csp.addConstraint(jobShopConstraint);}AbstractAssignment ass = csp.backTrackingSearch();if(ass!=null){ass.display();}else{System.out.println("No solution!");}}
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！