# Assign jobs to machines so that the maximum workload of any machine is minimized.
import random

jobs = [4, 7, 3, 8, 5]
size = 30
generations = 100
mutation = 0.1

def fitness(x):
    m1 = sum(jobs[i] for i in range(5) if x[i] == 0)
    m2 = sum(jobs[i] for i in range(5) if x[i] == 1)
    return -max(m1,m2)

def create():
    return [[random.randint(0,1) for _ in range(5)]
            for _ in range(size)]

def select(pop):
    return max(random.sample(pop,3), key=fitness)

def crossover(a,b):
    p = random.randint(1,4)
    return a[:p]+b[p:]

def mutate(x):
    for i in range(5):
        if random.random() < mutation:
            x[i] = 1-x[i]
    return x

pop = create()

for gen in range(generations):
    pop.sort(key=fitness, reverse=True)
    best = pop[0]

    new = [best]
    while len(new) < size:
        child = crossover(select(pop),select(pop))
        new.append(mutate(child))

    pop = new

best = max(pop, key=fitness)

print("Job Assignment:", best)
print("Machine 1 Jobs:", [jobs[i] for i in range(5) if best[i] == 0])
print("Machine 2 Jobs:", [jobs[i] for i in range(5) if best[i] == 1])
print("Minimum Maximum Workload:", -fitness(best))
