ga #2

import java.util.*;

public class Main {
    static int M = 2; //number of the machines
    static int N; //number of the jobs excluding dummy job
    static Job[] jobs;
    static int machineCapacity;
    static Random random = new Random();
    static List<int[]> population = new ArrayList<>();
    static int populationSize = 20;
    static int iterations = 500;

    public static void main(String[] args) {
        jobs = new Job[]{
                new Job(0, 0, 0),
                new Job(1, 3, 3),
                new Job(2, 3, 5),
                new Job(3, 5, 8),
                new Job(4, 4, 6)};
        N = jobs.length - 1;//number of the jobs excluding dummy job
        machineCapacity = N + 1;

        initPopulation();
        int[] best = getBestChromosome();

        for (int i = 0; i < iterations; i++) {
            List<int[]> newPopulation = new ArrayList<>();

            for (int j = 0; j < populationSize; j++) {
                int[] chromosome1 = tournamentSelection();
                int[] chromosome2 = tournamentSelection();

                if (shouldCrossover()) {
                    int[] child = crossover(chromosome1, chromosome2);

                    if (shouldMutateJobs())
                        mutateJobs(child, jobs);

                    if (shouldMutateMachines())
                        mutateMachines(child);

                    newPopulation.add(child);
                } else {
                    if (shouldMutateJobs())
                        mutateJobs(chromosome1, jobs);

                    if (shouldMutateMachines())
                        mutateMachines(chromosome1);

                    newPopulation.add(chromosome1);
                }
            }
            population = newPopulation;
            int[] populationBest = getBestChromosome();

            if (getMaximumLateness(populationBest) < getMaximumLateness(best)) {
                best = Arrays.copyOf(populationBest, populationBest.length);
            }
        }

        displayChromosome(best);
        printJobs();
        System.out.println(getMaximumLateness(best));
    }

    static int[] tournamentSelection() {
        int size = 5;
        List<int[]> selected = new ArrayList<>();
        for (int i = 0; i < size; i++) {
            selected.add(population.get(random.nextInt(populationSize)));
        }

        Collections.sort(selected, (ints, t1) -> {
            int a = getMaximumLateness(ints);
            int b = getMaximumLateness(t1);

            return Integer.compare(a, b);
        });

        return Arrays.copyOf(selected.get(0), selected.get(0).length);
    }

    static void initPopulation() {
        for (int i = 0; i < populationSize; i++) {
            int[] chromosome = createChromosome();
            population.add(chromosome);
        }
    }

    static int[] getBestChromosome() {
        int[] best = population.get(0);
        int bestFitness = getMaximumLateness(best);
        for (int[] chromosome : population) {
            int fitness = getMaximumLateness(chromosome);
            if (fitness < bestFitness) {
                best = chromosome;
            }
        }
        return Arrays.copyOf(best, best.length);
    }

    static void printJobs() {
        for (Job job : jobs) System.out.print(job.number + " ");
        System.out.println();
    }

    private static int[] createChromosome() {
        int[] chromosome = new int[machineCapacity * M];

        //set dummy job
        for (int i = 0; i < chromosome.length; i += machineCapacity)
            chromosome[i] = 1;

        //assign each job to the random machine
        for (int i = 1; i <= N; i++) {
            int machine = getRandomMachine();
            chromosome[i + machine * machineCapacity] = 1;
        }

        return chromosome;
    }

    private static void displayChromosome(int[] chromosome) {
        for (int i = 0; i < M; i++) {
            for (int j = 0; j < machineCapacity; j++)
                System.out.print(j);

            System.out.print('|');
        }
        System.out.println();

        for (int i = 0; i < chromosome.length; i++) {
            System.out.print(chromosome[i]);
            if ((i + 1) % machineCapacity == 0 && i < chromosome.length - 1) {
                System.out.print('|');
            }
        }
        System.out.println();
    }

    private static void mutateJobs(int[] chromosome, Job[] jobs) {
        //First, a machine is randomly selected then two jobs are selected at random on that
        // machine and replaced with each other (i.e., they are swapped)
        int machine = getRandomMachine();
        int firstJobOnMachine = machine * machineCapacity + 1;

        //before swapping check if there are at least 2 jobs on machine
        if (areAtLeast2JobsOnMachine(machine, chromosome)) {
            int job1Index = getRandomJobNumber(firstJobOnMachine, N);
            int job2Index = getRandomJobNumber(firstJobOnMachine, N);

            // (we have to swap initial jobs (change its order), because chromosome can only hold
            // position info, not job values)
            if (doesJobExist(chromosome, job1Index) && doesJobExist(chromosome, job2Index)) {
                int job1RealIndex = job1Index % machineCapacity;
                int job2RealIndex = job2Index % machineCapacity;

                Job temp = jobs[job1RealIndex];
                jobs[job1RealIndex] = jobs[job2RealIndex];
                jobs[job2RealIndex] = temp;
            }
        }
    }

    static int getRandomMachine() {
        return random.nextInt(M);
    }

    static int getRandomJobNumber(int begin, int range) {
        return random.nextInt(range) + begin;
    }

    static boolean doesJobExist(int[] chromosome, int jobNumber) {
        return chromosome[jobNumber] == 1;
    }

    static boolean areAtLeast2JobsOnMachine(int machine, int[] chromosome) {
        int startIndex = machine * machineCapacity + 1;
        int sum = 0;

        for (int i = startIndex; i < startIndex + N; i++)
            if (chromosome[i] == 1) sum++;

        return sum > 1;
    }

    private static void mutateMachines(int[] chromosome) {
        //First, a job number is randomly selected
        //ensure job is not dummy job -> start from `1` index
        int jobNumber = getRandomJobNumber(1, N);

        // then two machines are selected at random.
        int machine1 = getRandomMachine();
        int machine2 = getRandomMachine();

        // The selected job is replaced on two machines
        int machine1JobNumber = machine1 * machineCapacity + jobNumber;
        int machine2JobNumber = machine2 * machineCapacity + jobNumber;

        int temp = chromosome[machine1JobNumber];
        chromosome[machine1JobNumber] = chromosome[machine2JobNumber];
        chromosome[machine2JobNumber] = temp;
    }

    private static int[] crossover(int[] chromosome1, int[] chromosome2) {
        // A random value, r, is created in the range of [1, (N+1)*M]
        int r = getRandomJobNumber(1, machineCapacity * M);

        int[] child1 = Arrays.copyOf(chromosome1, chromosome1.length);
        int[] child2 = Arrays.copyOf(chromosome2, chromosome2.length);

        //All digits from the first one to the r th one are replaced on two chromosomes.
        for (int i = 0; i < r; i++) {
            int temp = child1[0];
            child1[i] = child2[i];
            child2[i] = temp;
        }

        // Then, both offspring are checked with the rule to create feasible chromosomes.
        repair(child1);
        return child1;
    }

    private static void repair(int[] chromosome) {
        Map<Integer, Integer> jobsOccurrence = new HashMap<>();

        //store job positions
        for (int i = 0; i < machineCapacity; i++) {
            jobsOccurrence.put(i, 0);
        }

        //count all jobs
        for (int i = 0; i < chromosome.length; i++) {
            int jobPosition = i % machineCapacity;
            int occurrence = jobsOccurrence.get(jobPosition);
            jobsOccurrence.put(jobPosition, occurrence + chromosome[i]);
        }

        for (Integer jobPosition : jobsOccurrence.keySet()) {
            if (jobPosition != 0) {
                int occurrence = jobsOccurrence.get(jobPosition);
                if (occurrence < 1) {
                    chromosome[jobPosition] = 1;
                }
                if (occurrence > 1) {
                    boolean removed = false;
                    for (int i = jobPosition; i < chromosome.length && !removed; i += machineCapacity) {
                        if (chromosome[i] == 1) {
                            chromosome[i] = 0;
                            removed = true;
                        }
                    }
                }
            }
        }
    }

    private static class Job {
        int number;
        int processingTime;
        int deadLine;

        public Job(int number, int processingTime, int deadLine) {
            this.number = number;
            this.processingTime = processingTime;
            this.deadLine = deadLine;
        }

        public Job(Job other) {
            this.number = other.number;
            this.processingTime = other.processingTime;
            this.deadLine = other.deadLine;
        }
    }

    static int getMaximumLateness(int[] chromosome) {
        int maxLateness = 0;
        int elapsedTime = 0;
        for (int machine = 0; machine < M; machine++) {
            int machineFirstJobNumber = machine * machineCapacity + 1;

            for (int i = machineFirstJobNumber; i < machineFirstJobNumber + N; i++) {
                if (chromosome[i] == 1) {
                    int realJobIndex = i % machineCapacity;
                    Job job = jobs[realJobIndex];

                    elapsedTime += job.processingTime;

                    int jobLateness = elapsedTime - job.deadLine;

                    maxLateness = Math.max(maxLateness, jobLateness);
                }
            }
            elapsedTime = 0;
        }
        return maxLateness;
    }

    static boolean shouldCrossover() {
        return random.nextDouble() <= 0.75;
    }

    static boolean shouldMutateJobs() {
        return random.nextDouble() <= 0.03;
    }

    static boolean shouldMutateMachines() {
        return random.nextDouble() <= 0.03;
    }
}