Problem

Job Placement Scheduler (C)

Topics: backtracking, constraint satisfaction, scheduling

Problem

Place jobs onto nodes under capacity, affinity, and anti-affinity constraints — a constraint-satisfaction search shaped like N-Queens, but the "board" is a cluster.

typedef struct { const char *name; int cpu; } Job;   // cpu = consumed
typedef Job Node;                                     // cpu = capacity
typedef struct { const char *a, *b; } Pair;           // two job names

bool place(const Job *jobs, int njobs, const Node *nodes, int nnodes,
           const Pair *affinity, int naff, const Pair *antiAffinity, int nanti,
           int *out_node);

Find an assignment of every job to a node such that:

per node, the total CPU of jobs placed on it <= that node's capacity;
every affinity pair ends up on the same node;
no antiAffinity pair ends up on the same node.

On success, write out_node[j] = the node index job j is placed on, and return true; otherwise return false.

Key concepts

Place one job at a time, backtrack on dead ends: seat jobs[idx] on a node that has room and doesn't violate a constraint, recurse on the rest, and if that fails, restore the node's capacity and try the next node. An early choice that strands a later job (especially an affinity partner) gets revisited.
Check against jobs already placed: an affinity partner already on a node forces this job to the same node; an anti-affinity partner forces a different one. Partners not yet placed impose no constraint yet — that's what makes affinity need real backtracking.
Capacity is a running budget: subtract on placement, add back on undo.

A remaining[] capacity array and the out_node[] assignment track state — no allocation.

Run

cc -std=c11 -O2 -Wall tests.c -o /tmp/scheduler && /tmp/scheduler

Leaderboard score: lower is better, 1.0 ≈ reference

#	Name	score	ns/op	allocs

Output

No submission yet.