Posts by author Andreas Beham

Modeling scheduling problems with HeuristicLab

HeuristicLab makes it very easy to model scheduling problems. HeuristicLab comes included with the simulation framework Sim#, a port of SimPy to C#. With Sim# writing process-based simulation models requires little effort. Here, I demonstrate in only a few lines of code how to implement a permutation flow shop problem using a Programmable Problem (single-objective). You can create this problem in the GUI from the New Item dialog and paste following code into the editor pane, then hit compile. You can optimize solutions after you dragged it to the Problem tab of an algorithm that can handle programmable permutation-based problems (e.g. Genetic Algorithm).

using System;
using System.Linq;
using System.Collections.Generic;
using HeuristicLab.Core;
using HeuristicLab.Data;
using HeuristicLab.Encodings.PermutationEncoding;
using HeuristicLab.Optimization;
using IRandom = HeuristicLab.Core.IRandom;
using SimSharp;
using SysEnv = System.Environment;
using SimEnv = SimSharp.Environment;

namespace HeuristicLab.Problems.Programmable {
  public class FlowShopProblemDefinition : CompiledProblemDefinition,
                                           ISingleObjectiveProblemDefinition {
    private static readonly string[] machineSep = new [] { SysEnv.NewLine };
    private static readonly string[] jobSep = new [] { " ", "\t" };
    // from http://mistic.heig-vd.ch/taillard/problemes.dir/ordonnancement.dir/flowshop.dir/tai20_5.txt
    private static readonly string instance = @"
 54 83 15 71 77 36 53 38 27 87 76 91 14 29 12 77 32 87 68 94
 79  3 11 99 56 70 99 60  5 56  3 61 73 75 47 14 21 86  5 77
 16 89 49 15 89 45 60 23 57 64  7  1 63 41 63 47 26 75 77 40
 66 58 31 68 78 91 13 59 49 85 85  9 39 41 56 40 54 77 51 31
 58 56 20 85 53 35 53 41 69 13 86 72  8 49 47 87 58 18 68 28
";
    private int M, J; // number of machines, jobs
    private List<List<int>> pij; // processing times per machine, job
    
    // objective is to minimize makespan
    public bool Maximization { get { return false; } }

    public override void Initialize() {
      // processing times are parsed from the instance
      pij = instance.Split(machineSep, StringSplitOptions.RemoveEmptyEntries)
              .Select(x => x.Split(jobSep, StringSplitOptions.RemoveEmptyEntries)
                            .Select(y => int.Parse(y)).ToList()).ToList();
      M = pij.Count;
      J = pij[0].Count;
      // encoding is created
      Encoding = new PermutationEncoding("p", length: J,
                                         type: PermutationTypes.Absolute);
    }

    public double Evaluate(Individual ind, IRandom random) {
      // create a new Sim# environment
      var env = new SimEnv();
      // create the M machines
      var machines = Enumerable.Range(0, M).Select(x => new Resource(env)).ToArray();
      // add the jobs in order given by the permutation
      foreach (var o in ind.Permutation("p"))
        env.Process(Job(env, o, machines));
      // run the simulation
      env.Run();
      // return the current simulation time (last finish time)
      return env.NowD;
    }
    
    private IEnumerable<Event> Job(SimEnv env, int j, Resource[] machines) {
      // for each of the M machines in order from 0 to M-1
      for (var m = 0; m < M; m++) {
        // create a new request for the next machine
        // the machine is freed after the using block
        using (var req = machines[m].Request()) {
          // wait upon obtaining the machine
          yield return req;
          // process the job j on machine m
          yield return env.TimeoutD(pij[m][j]);
        }
      }
    }

    public void Analyze(Individual[] individuals, double[] qualities,
                        ResultCollection results, IRandom random) { }
    
    // for move-based algorithms, all possible swap2 neighbors are returned
    public IEnumerable<Individual> GetNeighbors(Individual ind, IRandom random) {
      var p = ind.Permutation("p");
      foreach (var move in ExhaustiveSwap2MoveGenerator.Apply(p)) {
        var neighbor = ind.Copy();
        var perm = neighbor.Permutation("p");
        Swap2Manipulator.Apply(perm, move.Index1, move.Index2);
        yield return neighbor;
      }
    }
  }
}

This includes a "simple" 5 machine / 20 job problem instance from Taillard's instances.