package de.tutorials;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.BitSet;
import java.util.HashSet;
import java.util.List;
import java.util.Random;
import java.util.Set;
public class MachineAssignmentPlanOptimizationExample {
public static class MachineSchedule {
private int totalDuration = -1;
private final int[] orderIndexSequence;
private final ProductionPlant productionPlant;
private final ProductionPlan productionPlan;
private MachineSchedule(ProductionPlant productionPlant,ProductionPlan productionPlan, int... orderIndexSequence) {
this.productionPlant = productionPlant;
this.productionPlan = productionPlan;
this.orderIndexSequence = orderIndexSequence;
}
public int getTotalDuration() {
if (this.totalDuration == -1) {
this.totalDuration = computeTotalDuration();
}
return this.totalDuration;
}
private int computeTotalDuration() {
int totalDuration = 0;
int[] timeSlots = new int[productionPlant.getMachineCount()];
for (int i = 0; i < orderIndexSequence.length; i++) {
int orderIndex = orderIndexSequence[i];
ProductionOrder productionOrder = productionPlan.getProductionOrder(orderIndex);
for (int m = 0, mCount = productionPlant.getMachineCount(); m < mCount; m++) {
if (m > 0) {
timeSlots[m] = Math.max(timeSlots[m], timeSlots[m - 1]);
}
timeSlots[m] += productionOrder.getDurationOnMachine(m);
totalDuration = Math.max(totalDuration, timeSlots[m]);
}
}
return totalDuration;
}
@Override
public String toString() {
StringBuilder sb = new StringBuilder();
for (int i = 0; i < orderIndexSequence.length; i++) {
sb.append(i + 1).append(" ").append(productionPlan.getProductionOrder(orderIndexSequence[i])).append("\n");
}
return sb.toString();
}
public boolean allDifferent() {
BitSet alreadySeenIndices = new BitSet(orderIndexSequence.length);
for(int i = 0; i < orderIndexSequence.length;i++){
if(alreadySeenIndices.get(orderIndexSequence[i])){
return false;
}else{
alreadySeenIndices.set(orderIndexSequence[i]);
}
}
boolean allIndicesSeen = alreadySeenIndices.cardinality() == orderIndexSequence.length;
return allIndicesSeen;
}
}
public static class ProductionPlant {
private final int machineCount;
public ProductionPlant(int machineCount) {
this.machineCount = machineCount;
}
public void execute(ProductionPlan productionPlan) {
System.out.println("Computing optimal production plan...");
MachineSchedule machineSchedule = optimizeMachineAssignmentFor(productionPlan);
System.out.println("Finished! Total Schedule Duration: " + machineSchedule.getTotalDuration());
System.out.println(machineSchedule);
}
private MachineSchedule optimizeMachineAssignmentFor(ProductionPlan productionPlan) {
GeneticSolver<MachineSchedule> geneticSolver = new GeneticSolver<>();
SolutionFitness<MachineSchedule> best = geneticSolver.solve(new OptimalProductionScheduleProblem(this,productionPlan));
return best.solution;
}
public int getMachineCount() {
return this.machineCount;
}
}
public static class ProductionOrder {
private final String id;
private final int[] machineProcessingDurations;
public ProductionOrder(String id, int... machineProcessingDurations) {
this.id = id;
this.machineProcessingDurations = machineProcessingDurations;
}
public int getDurationOnMachine(int machineIndex) {
return this.machineProcessingDurations[machineIndex];
}
@Override
public String toString() {
return "ProductionOrder [id=" + id + "]";
}
}
public static class ProductionPlan {
private final List<ProductionOrder> productionOrders = new ArrayList<>();
public void add(ProductionOrder productionOrder) {
this.productionOrders.add(productionOrder);
}
public ProductionOrder getProductionOrder(int orderIndex) {
return productionOrders.get(orderIndex);
}
public int getOrderCount() {
return this.productionOrders.size();
}
}
public static void main(String[] args) {
ProductionPlant productionPlant = new ProductionPlant(2);
ProductionPlan productionPlan = new ProductionPlan();
productionPlan.add(new ProductionOrder("O1", 3, 1));
productionPlan.add(new ProductionOrder("O2", 2, 3));
productionPlan.add(new ProductionOrder("O3", 1, 4));
productionPlant.execute(productionPlan);
}
static class OptimalProductionScheduleProblem implements Problem<MachineSchedule> {
private final ProductionPlant productionPlant;
private final ProductionPlan productionPlan;
private final Random randomizer = new Random();
public OptimalProductionScheduleProblem(ProductionPlant productionPlant, ProductionPlan productionPlan) {
this.productionPlant = productionPlant;
this.productionPlan = productionPlan;
}
@Override
public double fitness(MachineSchedule solution) {
double fitness = -solution.getTotalDuration();
if(!solution.allDifferent()){
fitness = Double.NEGATIVE_INFINITY;
}
return fitness;
}
@Override
public MachineSchedule generate() {
int[] orderIndices = new int[productionPlan.getOrderCount()];
for (int i = 0; i < orderIndices.length; i++) {
orderIndices[i] = randomizer.nextInt(orderIndices.length);
}
return new MachineSchedule(productionPlant, productionPlan,orderIndices);
}
@Override
public MachineSchedule combine(MachineSchedule first,MachineSchedule second) {
int[] combinationOrderIndices = new int[productionPlan.getOrderCount()];
int crossOverIndex = randomizer.nextInt(combinationOrderIndices.length);
for (int i = 0; i < crossOverIndex; i++) {
combinationOrderIndices[i] = first.orderIndexSequence[i];
}
for (int i = crossOverIndex; i < combinationOrderIndices.length; i++) {
combinationOrderIndices[i] = second.orderIndexSequence[i];
}
return new MachineSchedule(productionPlant, productionPlan,combinationOrderIndices);
}
@Override
public MachineSchedule mutate(MachineSchedule solution) {
int[] mutatedOrderSequence = solution.orderIndexSequence.clone();
int temp = mutatedOrderSequence[0];
mutatedOrderSequence[0] = mutatedOrderSequence[mutatedOrderSequence.length-1];
mutatedOrderSequence[mutatedOrderSequence.length-1] = temp;
return new MachineSchedule(productionPlant, productionPlan,mutatedOrderSequence);
}
}
static interface Problem<TSolution> extends FitnessFunction<TSolution>, SolutionGenerator<TSolution>, Combiner<TSolution>, Mutator<TSolution> {
}
static class Population<TSolution> {
private final List<TSolution> solutions = new ArrayList<TSolution>();
public Population() {
}
public Population(SolutionFitness<TSolution>[] topElite) {
for (SolutionFitness<TSolution> soluationFitness : topElite) {
solutions.add(soluationFitness.solution);
}
}
public int size() {
return solutions.size();
}
TSolution get(int index) {
return solutions.get(index);
}
void add(TSolution solution) {
solutions.add(solution);
}
}
static interface FitnessFunction<TSolution> {
double fitness(TSolution solution);
}
static interface SolutionGenerator<TSolution> {
TSolution generate();
}
static interface Combiner<TSolution> {
TSolution combine(TSolution first, TSolution second);
}
static interface Mutator<TSolution> {
TSolution mutate(TSolution solution);
}
static class SolutionFitness<TSolution> implements Comparable<SolutionFitness<TSolution>> {
private final TSolution solution;
private final double fitness;
public SolutionFitness(TSolution solution, double fitness) {
this.solution = solution;
this.fitness = fitness;
}
@Override
public int compareTo(SolutionFitness<TSolution> that) {
return -Double.compare(this.fitness, that.fitness);
}
}
static class GeneticSolver<TSolution> {
private SolutionGenerator<TSolution> solutionGenerator;
private Combiner<TSolution> combiner;
private Mutator<TSolution> mutator;
private FitnessFunction<TSolution> fitnessFunction;
private Random randomizer = new Random();
private int populationSize = 20;
private int maxIterations = 100;
private int maxIterationsWithNoImprovement = maxIterations;
private double eliteRatioToKeep = 0.3;
private double mutationProbability = 0.4;
public SolutionFitness<TSolution> solve(Problem<TSolution> problem) {
init(problem);
System.out.println("Starting genetic search...");
SolutionFitness<TSolution> currentBest = null;
Population<TSolution> currentPopulation = generatePopulation();
int eliteCount = (int) (populationSize * eliteRatioToKeep);
int iterationsWithNoImprovement = 0;
for (int i = 0; i < maxIterations; i++) {
SolutionFitness<TSolution>[] solutionFitnesses = evaluate(currentPopulation);
SolutionFitness<TSolution>[] rankedSolutions = computeRankingBestSolutionsFirst(solutionFitnesses);
SolutionFitness<TSolution>[] topElite = takeTopEliteSolutions(eliteCount, rankedSolutions);
currentPopulation = new Population<TSolution>(topElite);
while (currentPopulation.size() < populationSize) {
TSolution candidate = applyGeneticOperators(topElite);
currentPopulation.add(candidate);
}
SolutionFitness<TSolution> nextBest = topElite[0];
if (currentBest != null) {
if (currentBest.fitness == nextBest.fitness) {
iterationsWithNoImprovement++;
} else {
iterationsWithNoImprovement = 0;
}
if (iterationsWithNoImprovement > maxIterationsWithNoImprovement) {
System.out.println("No improvement for " + maxIterationsWithNoImprovement + " iterations");
break;
}
}
currentBest = nextBest;
}
return currentBest;
}
private SolutionFitness<TSolution>[] takeTopEliteSolutions(int eliteCount, SolutionFitness<TSolution>[] rankedSolutions) {
return Arrays.copyOf(rankedSolutions, eliteCount);
}
void init(Problem<TSolution> problem) {
this.solutionGenerator = problem;
this.combiner = problem;
this.mutator = problem;
this.fitnessFunction = problem;
}
TSolution applyGeneticOperators(SolutionFitness<TSolution>[] topElite) {
TSolution candidate;
if (randomizer.nextDouble() < mutationProbability) {
TSolution mutationCandidate = topElite[randomizer.nextInt(topElite.length)].solution;
TSolution mutation = mutator.mutate(mutationCandidate);
candidate = mutation;
} else {
TSolution firstCandidate = topElite[randomizer.nextInt(topElite.length)].solution;
TSolution secondCandidate = topElite[randomizer.nextInt(topElite.length)].solution;
TSolution combination = combiner.combine(firstCandidate,secondCandidate);
candidate = combination;
}
return candidate;
}
SolutionFitness<TSolution>[] computeRankingBestSolutionsFirst(SolutionFitness<TSolution>[] individualFitnesses) {
Arrays.sort(individualFitnesses);
return individualFitnesses;
}
SolutionFitness<TSolution>[] evaluate(Population<TSolution> population) {
SolutionFitness<TSolution>[] solutionFitnesses = new SolutionFitness[populationSize];
for (int i = 0; i < solutionFitnesses.length; i++) {
TSolution solution = population.get(i);
double fitness = fitnessFunction.fitness(solution);
solutionFitnesses[i] = new SolutionFitness<TSolution>(solution,fitness);
}
return solutionFitnesses;
}
Population<TSolution> generatePopulation() {
Population<TSolution> population = new Population<TSolution>();
for (int i = 0; i < populationSize; i++) {
TSolution individual = solutionGenerator.generate();
population.add(individual);
}
return population;
}
}
}
