rss
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. Of course simulation enables to build much more complex models.
Note: Starting from Sim# 3.1.0 the class SimSharp.Environment is deprecated and should be replaced with SimSharp.Simulation.
