JSS

jss.odin

package jss

import "core:fmt"
import "core:time"
import "core:mem"
import "core:math"
import "core:math/rand"

Task :: distinct int

Machine :: struct {
	tasks: [dynamic]Task,
}

machine_create :: proc() -> (m: Machine) {
	m.tasks = make([dynamic]Task)
	return
}

machine_destroy :: proc(m: ^Machine){
	delete(m.tasks)
}

machine_add_task :: proc(m: ^Machine, task: Task){
	append(&m.tasks, task)
	// m.makespan += int(task)
}

machine_add_task_list :: proc(m: ^Machine, tasks: []Task){
	append(&m.tasks, ..tasks)
	acc := 0
	for t in tasks { acc += int(t) }
	// m.makespan += acc
}

machine_makespan :: proc(m: Machine) -> int {
	span := 0
	for t in m.tasks {
		span += int(t)
	}
	return span
}

machine_del_task :: proc(m: ^Machine, task_id: int) -> Task {
	t := m.tasks[task_id]
	unordered_remove(&m.tasks, task_id)
	// m.makespan -= int(t)
	return t
}

machine_highest_task :: proc(m: Machine) -> (max_task: Task, max_idx: int) {
	if !(len(m.tasks) > 0){
		fmt.println(m)
	}

	for task, i in m.tasks {
		if task > max_task {
			max_task = task
			max_idx = i
		}
	}

	return
}

MachineGroup :: struct {
	machines: []Machine,
}

group_create :: proc(mach_count: int) -> (group: MachineGroup) {
	group.machines = make([]Machine, mach_count)
	for &mach in group.machines {
		mach = machine_create()
	}
	return
}

group_destroy :: proc(mg: ^MachineGroup){
	for &mach in mg.machines {
		machine_destroy(&mach)
	}
	delete(mg.machines)
}

group_most_loaded_machine :: proc(mg: MachineGroup) -> (mach_idx: int) {
	assert(len(mg.machines) > 0, "No machines")

	max_load := 0
	for mach, id in mg.machines {
		span := machine_makespan(mach)
		if span > max_load {
			max_load = span
			mach_idx = id
		}
	}
	assert(machine_makespan(mg.machines[mach_idx]) > 0)
	return
}

group_least_loaded_machine :: proc(mg: MachineGroup) -> (mach_idx: int) {
	assert(len(mg.machines) > 0, "No machines")

	min_load := max(int)
	for mach, id in mg.machines {
		span := machine_makespan(mach)
		if span < min_load {
			min_load = span
			mach_idx = id
		}
	}
	return
}

// Transfer the highest task from source to destination
group_transfer_highest :: proc(mg: ^MachineGroup, source_id, dest_id: int){
	source := &mg.machines[source_id]
	dest := &mg.machines[dest_id]

	task, task_idx := machine_highest_task(source^)
	machine_del_task(source, task_idx)
	machine_add_task(dest, task)
}

group_makespan :: proc(mg: MachineGroup) -> int {
	span := 0
	for mach in mg.machines {
		span = max(span, machine_makespan(mach))
	}
	return span
}

group_select_neighbor_random :: proc(mg: MachineGroup, target: int) -> int {
	assert(len(mg.machines) > 1, "No possible neighbors")
	for {
		idx := int(rand.int31_max(cast(i32)len(mg.machines)))
		if idx != target {
			return idx
		}
	}
}

group_select_neighbor_least_loaded :: proc(mg: MachineGroup, target: int) -> int {
	assert(len(mg.machines) > 1, "No possible neighbors")
	neighbor := group_least_loaded_machine(mg)

	if neighbor == target {
		return (target + 1) % len(mg.machines)
	}
	return neighbor
}

simmulated_annealing :: proc(mg: ^MachineGroup, threshold: int, initial_temp: f64, alpha: f64){
	previous_makespan := group_makespan(mg^)

	temperature := initial_temp

	accepted_swaps := 0
	rejected_swaps := 0

	for {
		defer temperature *= alpha
		current := group_most_loaded_machine(mg^)
		neighbor := group_select_neighbor_least_loaded(mg^, current)

		group_transfer_highest(mg, current, neighbor)
		new_makespan := group_makespan(mg^)

		delta := f64(new_makespan - previous_makespan)
		if delta >= 0 {
			// Energy was NOT reduced, randomly decide if answer can be accepted
			p := math.exp(-delta / temperature)
			r := rand.float64_range(0, 1)

			if r > p {
				// Reject, revert changes
				neighbor_mach := &mg.machines[neighbor]
				current_mach := &mg.machines[current]
				
				task := machine_del_task(neighbor_mach, len(neighbor_mach.tasks) - 1)
				machine_add_task(current_mach, task)
				rejected_swaps += 1
			}
			else {
				// Randomly accept, even though it's a worse state
				previous_makespan = new_makespan
			}
		}
		else {
			// Energy was reduced, accept changes
			accepted_swaps += 1
			previous_makespan = new_makespan
		}
		
		if new_makespan <= threshold { fmt.println("REACHED THRESHOLD"); break }
		if temperature < 1e-20 { fmt.println("REACHED LOW TEMP"); break }
	}

	fmt.println("Accepted:", accepted_swaps, "Rejected:", rejected_swaps)
}

display_group :: proc(mg: MachineGroup){
	mach_n := len(mg.machines)
	task_n := 0
	for m in mg.machines {
		task_n += len(m.tasks)
	}

	fmt.printfln("--- Makespan: %v | Machines: %v | Tasks: %v ---", group_makespan(mg), mach_n, task_n)
	for mach, id in mg.machines {
		fmt.printf("(S=%d) M{:d} ", machine_makespan(mach), id)
		for task in mach.tasks {
			fmt.printf("%d, ", task)
		}
		fmt.println()
	}
}

generate_random_tasks :: proc(n: int) -> []Task {
	tasks := make([]Task, n, context.temp_allocator)
	for &task in tasks {
		v := rand.int31_max(98) + 1
		task = Task(v)
	}
	return tasks
}

main :: proc(){
	tasks := generate_random_tasks(20)

	group := group_create(4)
	machine_add_task_list(&group.machines[0], tasks)

	display_group(group)
	simmulated_annealing(&group, 0, 400, 0.9)
	display_group(group)
}