1: /*
2: * Copyright (C) 2013 changedi
3: *
4: * Licensed under the Apache License, Version 2.0 (the "License");
5: * you may not use this file except in compliance with the License.
6: * You may obtain a copy of the License at
7: *
8: * http://www.apache.org/licenses/LICENSE-2.0
9: *
10: * Unless required by applicable law or agreed to in writing, software
11: * distributed under the License is distributed on an "AS IS" BASIS,
12: * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13: * See the License for the specific language governing permissions and
14: * limitations under the License.
15: */
16: package com.jybat.dp;
17:
18: import java.util.HashSet;
19: import java.util.Set;
20:
21: //Flowshop Problem
22: public class FLOWSHOP { 23:
24: private static int[] first = { 3, 4, 8, 10 }; // sum=25 25: private static int[] second = { 6, 2, 9, 15 }; // sum=32 26: // upper bound on final completion time is 25+32:
27: private static int sum = 57;
28: private static int m = first.length;
29:
30: private static Set<Integer> setOfAllItems = new HashSet<Integer>();
31:
32: static{ 33: setOfAllItems.add(0);
34: setOfAllItems.add(1);
35: setOfAllItems.add(2);
36: setOfAllItems.add(3);
37: }
38:
39: private static int fct(int t, int d) { 40: return Math.max(t - first[d], 0) + second[d];
41: }
42:
43: public static double f(Set<Integer> set, int t){ 44: if(set.isEmpty())
45: return t;
46: double min = Double.MAX_VALUE;
47: for(int d : set){ 48: Set<Integer> tmpSet = copySet(set);
49: tmpSet.remove(d);
50: double tmp = first[d]+f(tmpSet,fct(t,d));
51: if(tmp<min){ 52: min=tmp;
53: }
54: }
55: return min;
56: }
57:
58: private static Set<Integer> copySet(Set<Integer> set) { 59: Set<Integer> s = new HashSet<Integer>();
60: for(int x : set){ 61: s.add(x);
62: }
63: return s;
64: }
65:
66: /**
67: * @param args
68: */
69: public static void main(String[] args) { 70: System.out.println(f(setOfAllItems,0));
71: }
72:
73: }