Maschinenbelegungsproblem @ tutorials.de: Tutorials, Forum & Hilfe

publicstatic · 28.12.11 11:54

Hallo,

Muss eine Art scheduling problem lösen. Dabei müssen n Aufträge an m Maschinen bearbeitet werden.
Das ganze soll mit Hilfe von genetischem Algorithmen geschehen.

Bin noch ganz am Anfang. Wie kann ich Individuen(Lösungsvorschläge) erzeugen? Ein derartiger Maschinenbelegungsplan wird ja meist in einem Gantt-Diagramm dargestellt. Wie kann ich so einen Plan codieren(z.B in ein Array, dass die Auftragsfolge darstellt)?

Wenn man z.B 3 Aufträge hat, die jeweils an 3 Maschinen bearbeitet werden müssen, wie würde eine mögliche Lösung aussehen? Es ist sinnvoll die Lösung in einem array darzustellen, oder?

Wie stelle ich sicher, dass meine Individuen alle zulässige Lösungen sind(keine Überschneidungen etc.)?

Was ich auch nicht verstehe ist wie man diese Lösungen(Arrays) automatisch generiert?

Danke und lg

j2se · 28.12.11 12:17

Bevor Du Dich mit java rumschlägst, solltest Du im Bereich des Operations Research stöbern. Dort werden genau derartige Probleme gelöst, z.B. der Johnson-Algorithmus. Bei Deiner Problembeschreibung ist mir noch nicht klar, ob die Problemlösung zu einer Doktorarbeit ausartet.

publicstatic · 28.12.11 13:29

Wie ein genetischer Algorithmus funktioniert, versteh ich so halbwegs. Aber dieser braucht Individuen, von denen er ausgeht. Diese müsste ich irgendwie generieren, aber so, dass es wirklich zulässige Lösungen für das Maschinenbelegungsproblem sind.

Bin erst im 3. Semester, zur Doktorarbeit sollte es also nicht werden.

Hier noch einmal die genaue Angabe:

Das Java-Programm soll einen optimalen Belegungsplan für n Aufträge,die an m>2 Maschinen bearbeitet werden müssen nach der Idee der genetischen Algorithmen bestimmen.

j2se · 28.12.11 13:42

Die Individuen können ja Instanzen sein oder eine Sammlung von Objekten wie z.B. ein Array, eine List, Map oder was auch immer sich für Dein Algorithmus eignet.

**Thomas Darimont** · 02.01.12 08:21

Hallo,

du musst noch etwas mehr Angaben zu deinem Problem machen.
1) Wodurch sind ein deinem System Aufträge charakterisiert?

Auftrag = (Id, Dauer, Spätester Endtermin, Priorität, Ressourcen / bestimmte Maschinen-Voraussetzungen)?

2) Wodurch sind ein deinem System Maschinen charakterisiert?
Maschine=(Id, Kapazität, Verarbeitungsdauer, Maschinen-Fähigkeiten, Kosten pro Auftrag / Zeiteinheit)?

3) Müssen die Aufträge nur von einer oder auch von mehreren Maschinen bearbeitet werden?

4) Was willst du denn im Belegungsplan Optimieren?
4.1) Die Durchlaufzeit minimieren?
4.2) Die Kapazitätsauslastung (Maschinenauslastung) maximieren?
4.3) Die Terminabweichungen minimieren?
4.4) Die Verarbeitungskosten minimieren?
...
4.x) eine Kombination mehrerer Kriterien?

zu deinen Fragen:

Wie stelle ich sicher, dass meine Individuen alle zulässige Lösungen sind(keine Überschneidungen etc.)?

In deiner Fitness-Funktion kodierst du die Ermittlung der Güte eines konkreten Belegungsplans (deines Individuums) (Aufträge auf Maschinen verteilt). Dabei kannst du sowohl positive Einflüsse (Termintreue, Kostengünstigkeit, Gesamtauslastungsgrad) als auch negative Einflüsse (ungültige Belegungen, Terminverzug, etc.) einbeziehen.
...
in dem du in deiner Fitness-Funktion unzulässige Lösungen maximal bestrafst (maximal schlechte Fitness) werden diese vom genetischen Algorithmus automatisch gemieden.

Was ich auch nicht verstehe ist wie man diese Lösungen(Arrays) automatisch generiert?

Die (möglichen) Lösungen -> Lösungskandidaten -> Individuen generierst du mithilfe eines Zufallszahlengenerators zufällig. In deinem Fall verteilst du einfach die gegeben Auftrage auf die
zur Verfügung stehenden Maschinen.

Bin noch ganz am Anfang. Wie kann ich Individuen(Lösungsvorschläge) erzeugen? Ein derartiger Maschinenbelegungsplan wird ja meist in einem Gantt-Diagramm dargestellt. Wie kann ich so einen Plan codieren(z.B in ein Array, dass die Auftragsfolge darstellt)?

Da die Kodierung die Lösungsfindung in einem genetischen Algorithmus stark beeinflussen kann, möchte ich noch auf die Antworten zu den obigen Fragen warten, bevor ich einen Vorschlag mache.

Gruß Tom

publicstatic · 02.01.12 11:36

Hi!

Versuche mal deine Fragen zu beantworten:

1) Jeder Auftrag muss an jeder Maschine bearbeitet werden. Jeder Auftrag hat eine nummer(Id) und einen Zeitwert für jede Maschine. Das wars auch schon. Ressourcen, deadline etc. sollten keine Rolle spielen.

2) Wichtig ist, dass jede Maschine immer nur einen Auftrag bearbeiten kann(nicht 2 Aufträge zur gleichen zeit). Und dass Auftrag 1 nicht an Maschine1 bearbeitet werden kann, wenn er gerade an Maschine2 bearbeitet wird.

3) Wie gesagt,jeder Auftrag an jeder Maschine.

4) Die Durchlaufzeit minimieren. Allerdings nicht die Zeit für einen Auftrag, sondern die Zeit, bis alle n Aufträge fertig bearbeitet worden sind.

Vielen Dank dass du deine Hilfe anbietest!

lg

**Thomas Darimont** · 02.01.12 14:47

Hallo,

3) Wie gesagt,jeder Auftrag an jeder Maschine.

Ist die Reihenfolge des Maschineneinsatzes für eine Auftrag beliebig?

Bsp.: Wenn der Auftrag 1 bei 3 Maschinen 3 Zeit-Einheiten von Maschine 1 (M1), 1 Zeit-Einheit von M2 und 4 Zeit-Einheiten von M3 braucht -> A_i := (M1_i, M2_i, M3_i) -> A_1 := (3,1,4), kann ich dann mit 4 Zeit-Einheiten auf M3 beginnen oder muss ich mit 3 Einheiten bei M1 und anschließend M2 etc. anfangen?

Gruß Tom

publicstatic · 02.01.12 22:23

Die Angabe ist leider etwas knapp. Gehe aber davon aus, dass die Reihenfolge beliebig ist.

**Thomas Darimont** · 02.01.12 23:21

Hallo,

da ich den entsprechenden Code noch vorrätig hatte (http://www.tutorials.de/archiv/35834...gorithmus.html), habe ich dir mal ein kleines Beispiel gebastelt, schau mal hier:

//Edit: ich weiß, dass das Beispielproblem für die Parameterisierung des genetischen Algorithmus etwas unterdimensioniert ist, aber ich hatte keine Muße mehr mir ein größeres Beispiel auszudenken.

Code java:

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() {
//          //naive approach...
//          Set<Integer> set = new HashSet<>();
//          for(int i : orderIndexSequence){
//              set.add(i);
//          }
//          return set.size() == orderIndexSequence.length;
            
            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) {
        
        /*
         * Problem Setting:
         * 
         * Production Plant with 2 Machines (M1, M2)
         * 3 Production Orders to be scheduled.
         * 
         * Order 1 (O1) needs 3 time units on M1 and 1 time unit on M2
         * Order 2 (O2) needs 2 time units on M1 and 3 time units on M2
         * Order 3 (O3) needs 1 time unit on M1 and 4 time units on M2
         * 
         * Optimization Goal: Minimize total processing duration!
         * 
         * Example for an Optimal Production Setting: O3, O1, O2
         * 
         *   M1 O3 O1 O1 O1 O2 O2
         *   M2    O3 O3 O3 O3 O1 O2 O2 O2
         *   ---------------------------------------------
         * Time 01 02 03 04 05 06 07 08 09 10 11 12 13 
         * 
         */
        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(); // Minimize total duration
            
            if(!solution.allDifferent()){ //penalty for invalid solutions
                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()];
            
            //single point crossover
            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) {
            
            //swap first and last production order
            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();
 
        /*
         * tuning options
         */
        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;
                
                //System.out.println("Current best: " + currentBest.solution + " " + currentBest.fitness);
            }
 
            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;
        }
    }
}

Ausgabe:

Code :

Computing optimal production plan...
Starting genetic search...
Finished! Total Schedule Duration: 9
1 ProductionOrder [id=O3]
2 ProductionOrder [id=O1]
3 ProductionOrder [id=O2]

Gruß Tom

publicstatic · 04.01.12 12:10

Danke für deine Mühe!

Muss mir deinen Code genauer ansehen. Falls Fragen auftreten, meld ich mich wieder.

lg

tut orials.de	tut verbinden	tut dir helfen	tut kooperieren
©2000-2012 tutorials.de Alle Rechte vorbehalten	tut informieren » Impressum » Nutzungsregeln » Netiquette » Team » Redaktion	» Tutorials » Videotutorials » Showroom » Events & Contests » Chat » RSS-Feed » Blogs	» der-webdesigner.net » DesignerInAction » Design Nation » Directorforum » Flashhilfe » PHP-Resource » PHPwelt » PSD-Tutorials

Themen-Optionen

Anzeige

E-Mail:

Abonnieren Abbestellen