Algorithms

harold aptroot wrote:

veryone seems to use heuristic algorithms because solving an ILP problem is too slow for them

static int[] Schedule(int[] jobs, int machines)
{
    int[] targets = new int[jobs.Length];
    int[] lengths = new int[machines];
    _bestFoundScore = int.MaxValue;
    _bestSolution = null;
    _schedule(jobs, targets, 0, lengths);
    return _bestSolution;
}
static int _bestFoundScore = int.MaxValue;
static int[] _bestSolution = null;
static void _schedule(int[] jobs, int[] targets, int index, int[] lengths)
{
    if (index == jobs.Length)
    {   // reached bottom
        int max = 0;
        for (int j = 0; j < lengths.Length; j++)
            if (lengths[j] > max)
                max = lengths[j];
        if (max >= _bestFoundScore)
            return; // not good

        // found better
        _bestFoundScore = max;
        int[] res = new int[targets.Length];
        Array.Copy(targets, res, res.Length);
        _bestSolution = res;
    }
    else
    {
        for (int i = 0; i < lengths.Length; i++)
        {   // for each machine

            // add unused job to that machine
            targets[index] = i + 1;
            lengths[i] += jobs[index];
            // check bounds
            int max = 0;
            for (int j = 0; j < lengths.Length; j++)
                if (lengths[j] > max)
                    max = lengths[j];
            if (max < _bestFoundScore)
            {
                // recurse for next job
                _schedule(jobs, targets, index + 1, lengths);
            }
            // undo changes
            targets[index] = 0;
            lengths[i] -= jobs[index];
        }
    }
}

harold aptroot wrote:

For anything above 16 jobs it becomes really really slow

Luc Pattyn wrote:

IMO the more jobs the more "biggest job first" gets nearer to the optimal solution