Free cookie consent management tool by TermsFeed Policy Generator

Changeset 15460


Ignore:
Timestamp:
11/08/17 07:34:46 (7 years ago)
Author:
abeham
Message:

#2747: worked on the CFSAP

  • Added problem definition that defines both sequence and assignment for a single nest
  • Added problem definition that would optimizes both sequence and assignment for multiple nests
  • Added interface
  • Added solving strategy that would use multiple instances of a template algorithm to optimize the worst nest
  • Fixed bug in parser regarding setup times
Location:
branches/CFSAP
Files:
3 added
6 edited
1 copied

Legend:

Unmodified
Added
Removed

  • branches/CFSAP/CFSAP.sln

    r14757 r15460  
    11
    22Microsoft Visual Studio Solution File, Format Version 12.00
    3 # Visual Studio 14
    4 VisualStudioVersion = 14.0.25420.1
     3# Visual Studio 15
     4VisualStudioVersion = 15.0.27004.2002
    55MinimumVisualStudioVersion = 10.0.40219.1
    66Project("{FAE04EC0-301F-11D3-BF4B-00C04F79EFBC}") = "HeuristicLab.Problems.Scheduling.CFSAP-3.3", "HeuristicLab.Problems.Scheduling.CFSAP\3.3\HeuristicLab.Problems.Scheduling.CFSAP-3.3.csproj", "{93609034-D1EE-4DC6-A381-E4CDB55E4261}"
    … …  
    6060    HideSolutionNode = FALSE
    6161  EndGlobalSection
     62  GlobalSection(ExtensibilityGlobals) = postSolution
     63    SolutionGuid = {1DA298F0-1917-4ED1-8495-507A39302C34}
     64  EndGlobalSection
    6265EndGlobal

  • branches/CFSAP/HeuristicLab.Problems.Instances.CFSAP/3.3/BozejkoCFSAPInstanceProvider.cs

    r15456 r15460  
    8989        instance.Name = id.Name;
    9090        instance.Description = id.Description;
     91        int bkct;
     92        if (bestKnownCycleTimes.TryGetValue(id.Name, out bkct))
     93          instance.BestKnownCycleTime = bkct;
    9194        return instance;
    9295      }
    … …  
    103106    }
    104107
     108    private static readonly Dictionary<string, int> bestKnownCycleTimes = new Dictionary<string, int>() {
     109{ "gi_001", 608 },
     110{ "gi_002", 623 },
     111{ "gi_003", 500 },
     112{ "gi_004", 585 },
     113{ "gi_005", 549 },
     114{ "gi_006", 629 },
     115{ "gi_007", 603 },
     116{ "gi_008", 506 },
     117{ "gi_009", 588 },
     118{ "gi_010", 493 },
     119{ "gi_011", 597 },
     120{ "gi_012", 554 },
     121{ "gi_013", 594 },
     122{ "gi_014", 505 },
     123{ "gi_015", 631 },
     124{ "gi_016", 626 },
     125{ "gi_017", 585 },
     126{ "gi_018", 529 },
     127{ "gi_019", 649 },
     128{ "gi_020", 561 },
     129{ "gi_021", 535 },
     130{ "gi_022", 586 },
     131{ "gi_023", 602 },
     132{ "gi_024", 607 },
     133{ "gi_025", 598 },
     134{ "gi_026", 572 },
     135{ "gi_027", 605 },
     136{ "gi_028", 619 },
     137{ "gi_029", 646 },
     138{ "gi_030", 591 },
     139{ "gi_031", 958 },
     140{ "gi_032", 838 },
     141{ "gi_033", 974 },
     142{ "gi_034", 904 },
     143{ "gi_035", 1002 },
     144{ "gi_036", 998 },
     145{ "gi_037", 988 },
     146{ "gi_038", 872 },
     147{ "gi_039", 1009 },
     148{ "gi_040", 1000 },
     149{ "gi_041", 992 },
     150{ "gi_042", 1097 },
     151{ "gi_043", 989 },
     152{ "gi_044", 1038 },
     153{ "gi_045", 998 },
     154{ "gi_046", 1077 },
     155{ "gi_047", 997 },
     156{ "gi_048", 921 },
     157{ "gi_049", 902 },
     158{ "gi_050", 1035 },
     159{ "gi_051", 914 },
     160{ "gi_052", 1019 },
     161{ "gi_053", 997 },
     162{ "gi_054", 928 },
     163{ "gi_055", 973 },
     164{ "gi_056", 1011 },
     165{ "gi_057", 943 },
     166{ "gi_058", 959 },
     167{ "gi_059", 1079 },
     168{ "gi_060", 940 },
     169{ "gi_061", 2176 },
     170{ "gi_062", 2100 },
     171{ "gi_063", 2147 },
     172{ "gi_064", 2289 },
     173{ "gi_065", 2171 },
     174{ "gi_066", 2185 },
     175{ "gi_067", 2152 },
     176{ "gi_068", 2321 },
     177{ "gi_069", 2173 },
     178{ "gi_070", 2242 },
     179{ "gi_071", 2222 },
     180{ "gi_072", 2403 },
     181{ "gi_073", 2305 },
     182{ "gi_074", 2279 },
     183{ "gi_075", 2283 },
     184{ "gi_076", 2014 },
     185{ "gi_077", 2185 },
     186{ "gi_078", 2236 },
     187{ "gi_079", 2223 },
     188{ "gi_080", 2136 },
     189{ "gi_081", 2147 },
     190{ "gi_082", 2285 },
     191{ "gi_083", 2270 },
     192{ "gi_084", 2264 },
     193{ "gi_085", 2192 },
     194{ "gi_086", 2052 },
     195{ "gi_087", 2130 },
     196{ "gi_088", 2172 },
     197{ "gi_089", 2530 },
     198{ "gi_090", 2498 },
     199{ "gi_091", 4465 },
     200{ "gi_092", 4269 },
     201{ "gi_093", 4201 },
     202{ "gi_094", 4330 },
     203{ "gi_095", 4158 },
     204{ "gi_096", 4355 },
     205{ "gi_097", 4363 },
     206{ "gi_098", 4268 },
     207{ "gi_099", 4143 },
     208{ "gi_100", 4313 },
     209{ "gi_101", 4285 },
     210{ "gi_102", 4421 },
     211{ "gi_103", 4288 },
     212{ "gi_104", 4295 },
     213{ "gi_105", 4295 },
     214{ "gi_106", 4257 },
     215{ "gi_107", 4610 },
     216{ "gi_108", 4579 },
     217{ "gi_109", 4578 },
     218{ "gi_110", 4219 },
     219{ "gi_111", 4472 },
     220{ "gi_112", 4460 },
     221{ "gi_113", 4446 },
     222{ "gi_114", 4504 },
     223{ "gi_115", 4417 },
     224{ "gi_116", 4503 },
     225{ "gi_117", 4442 },
     226{ "gi_118", 4411 },
     227{ "gi_119", 4506 },
     228{ "gi_120", 4556 }
     229    };
    105230  }
    106231}

  • branches/CFSAP/HeuristicLab.Problems.Instances.CFSAP/3.3/BozejkoCFSAPParser.cs

    r15456 r15460  
    6464              }
    6565            }
    66             SetupTimes.Add(sp);
    6766          }
     67          SetupTimes.Add(sp);
    6868        }
    6969        reader.Close();

  • branches/CFSAP/HeuristicLab.Problems.Instances/3.3/Types/CFSAPData.cs

    r15456 r15460  
    3333    public string Description { get; set; }
    3434    /// <summary>
     35    /// Optional! The best known cycle time.
     36    /// </summary>
     37    public int? BestKnownCycleTime { get; set; }
     38    /// <summary>
    3539    /// The number of jobs.
    3640    /// </summary>

  • branches/CFSAP/HeuristicLab.Problems.Scheduling.CFSAP/3.3/CFSAP.cs

    r15456 r15460  
    2727using HeuristicLab.Core;
    2828using HeuristicLab.Data;
     29using HeuristicLab.Encodings.BinaryVectorEncoding;
    2930using HeuristicLab.Encodings.PermutationEncoding;
    3031using HeuristicLab.Optimization;
    … …  
    3435
    3536namespace HeuristicLab.Problems.Scheduling.CFSAP {
    36   [Item("Cyclic flow shop with two machines and a single nest (CFSAP) sequencing problem", "Non-permutational cyclic flow shop scheduling problem with a single nest of two machine from W. Bozejko.")]
     37  [Item("Cyclic flow shop with two machines and a single nest (CFSAP)", "Non-permutational cyclic flow shop scheduling problem with a single nest of two machine from W. Bozejko.")]
    3738  [Creatable(CreatableAttribute.Categories.CombinatorialProblems)]
    3839  [StorableClass]
    39   public class CFSAPSequenceOnly : SingleObjectiveBasicProblem<PermutationEncoding>, IProblemInstanceConsumer<CFSAPData> {
     40  public class CFSAP : SingleObjectiveBasicProblem<MultiEncoding>, ICFSAP, IProblemInstanceConsumer<CFSAPData> {
    4041    public override bool Maximization { get { return false; } }
    4142
    … …  
    4445    }
    4546
     47    public IntMatrix ProcessingTimes {
     48      get { return ProcessingTimesParameter.Value; }
     49      set { ProcessingTimesParameter.Value = value; }
     50    }
     51
    4652    public IValueParameter<ItemList<IntMatrix>> SetupTimesParameter {
    4753      get { return (IValueParameter<ItemList<IntMatrix>>)Parameters["SetupTimes"]; }
    4854    }
    4955
     56    public ItemList<IntMatrix> SetupTimes {
     57      get { return SetupTimesParameter.Value; }
     58      set { SetupTimesParameter.Value = value; }
     59    }
     60
    5061    [StorableConstructor]
    51     protected CFSAPSequenceOnly(bool deserializing) : base(deserializing) {}
    52     protected CFSAPSequenceOnly(CFSAPSequenceOnly original, Cloner cloner)
     62    protected CFSAP(bool deserializing) : base(deserializing) {}
     63    protected CFSAP(CFSAP original, Cloner cloner)
    5364      : base(original, cloner) {}
    54     public CFSAPSequenceOnly() {
    55       Parameters.Add(new ValueParameter<IntMatrix>("ProcessingTimes", "The processing times of each job for each machine nest."));
    56       Parameters.Add(new ValueParameter<ItemList<IntMatrix>>("SetupTimes", "The sequence dependent set up times among all jobs for each machine nest."));
     65    public CFSAP() {
     66      Parameters.Add(new ValueParameter<IntMatrix>("ProcessingTimes", "The processing times of each machine and each job."));
     67      Parameters.Add(new ValueParameter<ItemList<IntMatrix>>("SetupTimes", "The sequence dependent set up times of each machine and between all jobs."));
    5768
    5869      ProcessingTimesParameter.Value = new IntMatrix(new int[,] {
    … …  
    7788      }));
    7889
    79       Encoding.Length = 5;
     90      Encoding.Add(new PermutationEncoding("sequence", 5, PermutationTypes.RelativeDirected));
     91      Encoding.Add(new BinaryVectorEncoding("assignment", 5));
    8092
    8193      Operators.RemoveAll(x => x is SingleObjectiveMoveGenerator);
    … …  
    8597
    8698    public override IDeepCloneable Clone(Cloner cloner) {
    87       return new CFSAPSequenceOnly(this, cloner);
     99      return new CFSAP(this, cloner);
    88100    }
    89101
    90102    public override double Evaluate(Individual individual, IRandom random) {
    91       var order = individual.Permutation(Encoding.Name);
    92       int T = EvaluateSequence(order);
    93       return T;
    94     }
    95 
    96     public int EvaluateSequence(Permutation order) {
    97       var N = order.Length;
    98       var processingTimes = ProcessingTimesParameter.Value;
    99       var setupTimes = SetupTimesParameter.Value;
    100 
    101       int[,,] weights = new int[2, 2 * N, 2 * N];
    102       int[,] graph = new int[2, N];
    103       int[,] prevPath = new int[2, N + 1];                     //Only for optimal assignment evaluation
    104       int[] optimalAssignment = new int[N];                //Only for optimal assignment evaluation
    105 
    106       //Calculate weights in the graph
    107       for (int S = 0; S < N; S++) { //Starting point of the arc
    108         for (int sM = 0; sM < 2; sM++) {    //Starting point machine
    109           int eM = sM == 0 ? 1 : 0;
    110           weights[sM, S, S + 1] = 0;
    111 
    112           for (int E = S + 2; E < S + N; E++)
    113             weights[sM, S, E] =
    114               weights[sM, S, E - 1] +
    115               processingTimes[eM, order[(E - 1) % N]] +
    116               setupTimes[eM][order[(E - 1) % N], order[E % N]];
    117 
    118           for (int E = S + 1; E < S + N; E++)
    119             weights[sM, S, E] += (
    120               processingTimes[sM, order[S % N]] +
    121               setupTimes[sM][order[S % N], order[(E + 1) % N]]
    122             );
    123         }
    124       }
    125 
    126       //Determine the shortest path in the graph
    127       int T = int.MaxValue / 2;
    128       for (int S = 0; S < N - 1; S++)      //Start node in graph          O(N)
    129         for (int SM = 0; SM < 2; SM++) {   //Start node machine in graph  O(1)
    130           graph[SM, S] = 0;
    131           graph[SM == 0 ? 1 : 0, S] = int.MaxValue / 2;
    132           prevPath[SM, 0] = -1;
    133           for (int E = S + 1; E < N; E++)      //Currently calculated node          O(N)
    134             for (int EM = 0; EM < 2; EM++) {   //Currently calculated node machine  O(1)
    135               graph[EM, E] = int.MaxValue / 2;
    136               for (int EC = S; EC < E; EC++) { //Nodes connected to node E          O(N)
    137                 int newWeight = graph[EM == 0 ? 1 : 0, EC] + weights[EM == 0 ? 1 : 0, EC, E];
    138                 if (newWeight < graph[EM, E]) {
    139                   graph[EM, E] = newWeight;
    140                   prevPath[EM, E] = EC;
    141                 }
    142               }
    143             }
    144 
    145           int EP = S + N; //End point.
    146           int newT = int.MaxValue / 2;
    147           for (int EC = S + 1; EC < N; EC++) { //Nodes connected to EP O(N)
    148             int newWeight = graph[SM == 0 ? 1 : 0, EC] + weights[SM == 0 ? 1 : 0, EC, EP];
    149             if (newWeight < newT) {
    150               newT = newWeight;
    151               prevPath[SM, S] = EC;
    152             }
    153           }
    154 
    155           if (newT < T) {
    156             T = newT;
    157             optimalAssignment = MakeAssignement(S, SM, prevPath, order);
    158           }
    159         }
    160 
    161       //Omitted solutions
    162       for (int machine = 0; machine < 2; machine++) {
    163         int[] assignment = Enumerable.Repeat(machine, N).ToArray();
    164         int newT = EvaluateAssignement(order, assignment, processingTimes, setupTimes);
    165         if (newT < T) { //New best solution has been found
    166           T = newT;
    167           assignment.CopyTo(optimalAssignment, N);
    168         }
    169       }
    170 
     103      var order = individual.Permutation("sequence");
     104      var assignment = individual.BinaryVector("assignment");
     105      int T = EvaluateAssignement(order, assignment.Select(x => x ? 1 : 0).ToArray(),
     106        ProcessingTimesParameter.Value, SetupTimesParameter.Value);
    171107      return T;
    172108    }
    … …  
    203139    }
    204140
    205     private int[] MakeAssignement(int start, int startMach, int[,] prevPath, Permutation order) {
    206       var N = order.Length;
    207       int[] assignment = Enumerable.Repeat(-1, N).ToArray();
    208       var inverseOrder = new int[N];
    209 
    210       for (int i = 0; i < N; i++)
    211         inverseOrder[order[i]] = i;
    212 
    213       int end = start + N;
    214 
    215       int currMach = startMach;
    216       int currNode = start;
    217       while (true) {
    218         assignment[inverseOrder[currNode]] = currMach;
    219         currNode = prevPath[currMach, currNode];
    220         currMach = currMach == 0 ? 1 : 0;
    221         if (currNode == start)
    222           break;
    223       }
    224 
    225       currMach = startMach;
    226       for (int i = 0; i < N; i++) {
    227         if (assignment[inverseOrder[i]] != -1)
    228           currMach = currMach == 0 ? 1 : 0;
    229         else
    230           assignment[inverseOrder[i]] = currMach;
    231       }
    232 
    233       return assignment;
     141    public void UpdateEncoding() {
     142      Encoding.Encodings.OfType<PermutationEncoding>().Single().Length = ProcessingTimes.Columns;
     143      Encoding.Encodings.OfType<BinaryVectorEncoding>().Single().Length = ProcessingTimes.Columns;
    234144    }
    235145
    … …  
    265175      }
    266176      SetupTimesParameter.Value = setups;
    267       Encoding.Length = data.Jobs;
     177      UpdateEncoding();
    268178      Name = data.Name + "-nest" + nest;
    269179      Description = data.Description;
     180      if (data.BestKnownCycleTime.HasValue)
     181        BestKnownQuality = data.BestKnownCycleTime.Value;
     182      else BestKnownQualityParameter.Value = null;
    270183    }
    271184  }

  • branches/CFSAP/HeuristicLab.Problems.Scheduling.CFSAP/3.3/CFSAPSequenceOnly.cs

    r15456 r15460  
    4444    }
    4545
     46    public IntMatrix ProcessingTimes {
     47      get { return ProcessingTimesParameter.Value; }
     48      set { ProcessingTimesParameter.Value = value; }
     49    }
     50
    4651    public IValueParameter<ItemList<IntMatrix>> SetupTimesParameter {
    4752      get { return (IValueParameter<ItemList<IntMatrix>>)Parameters["SetupTimes"]; }
     53    }
     54
     55    public ItemList<IntMatrix> SetupTimes {
     56      get { return SetupTimesParameter.Value; }
     57      set { SetupTimesParameter.Value = value; }
    4858    }
    4959
    … …  
    162172      for (int machine = 0; machine < 2; machine++) {
    163173        int[] assignment = Enumerable.Repeat(machine, N).ToArray();
    164         int newT = EvaluateAssignement(order, assignment, processingTimes, setupTimes);
     174        int newT = CFSAP.EvaluateAssignement(order, assignment, processingTimes, setupTimes);
    165175        if (newT < T) { //New best solution has been found
    166176          T = newT;
    167           assignment.CopyTo(optimalAssignment, N);
     177          optimalAssignment = assignment;
    168178        }
    169       }
    170 
    171       return T;
    172     }
    173 
    174     //Function to evaluate individual with the specified assignment
    175     public static int EvaluateAssignement(Permutation order, int[] assignment, IntMatrix processingTimes, ItemList<IntMatrix> setupTimes) {
    176       var N = order.Length;
    177       int T = 0;
    178 
    179       for (int i = 0; i < N; i++) {
    180         int operation = order[i];
    181         int machine = assignment[operation];
    182         T += processingTimes[machine, operation];
    183       }
    184 
    185       for (int machine = 0; machine < 2; machine++) {
    186         int first = -1;
    187         int last = -1;
    188         for (int i = 0; i < N; i++) {
    189           int operation = order[i];
    190           if (assignment[operation] == machine) {
    191             if (first == -1)
    192               first = operation;
    193             else
    194               T += setupTimes[machine][last, operation];
    195             last = operation;
    196           }
    197         }
    198         if (last != -1 && first != -1)
    199           T += setupTimes[machine][last, first];
    200179      }
    201180
    … …  
    232211
    233212      return assignment;
     213    }
     214
     215    public void UpdateEncoding() {
     216      Encoding.Length = ProcessingTimes.Columns;
    234217    }
    235218
    … …  
    265248      }
    266249      SetupTimesParameter.Value = setups;
    267       Encoding.Length = data.Jobs;
     250      UpdateEncoding();
    268251      Name = data.Name + "-nest" + nest;
    269252      Description = data.Description;
     253      if (data.BestKnownCycleTime.HasValue)
     254        BestKnownQuality = data.BestKnownCycleTime.Value;
     255      else BestKnownQualityParameter.Value = null;
    270256    }
    271257  }

  • branches/CFSAP/HeuristicLab.Problems.Scheduling.CFSAP/3.3/HeuristicLab.Problems.Scheduling.CFSAP-3.3.csproj

    r14757 r15460  
    114114  <ItemGroup>
    115115    <None Include="Plugin.cs.frame" />
     116    <Compile Include="CFSAP.cs" />
    116117    <Compile Include="CFSAPSequenceOnly.cs" />
     118    <Compile Include="ICFSAP.cs" />
     119    <Compile Include="MultiNestCFSAP.cs" />
     120    <Compile Include="MultiNestCFSAPSolvingStrategy.cs" />
    117121    <Compile Include="Plugin.cs" />
    118122    <None Include="Properties\AssemblyInfo.cs.frame" />
Note: See TracChangeset for help on using the changeset viewer.