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

static void Main(string[] args)
{
    StringBuilder sb = new StringBuilder();
    int j = 100;
    for (int i = 100; i < 101000; i++)
    {
        if (j > 999) j = 100;
        sb.Append((j*10).ToString() + " ");
        j++;
    }
    string s = sb.ToString();


    int idx = 0;
    int startidx = 0;
    int length = s.Length;
    List<int> nrs = new List<int>((int)(length*0.25));

    var watch = Stopwatch.StartNew();
    do
    {
        if (s[idx] == ' ')
        {
            if(idx>startidx)
                nrs.Add(atoi(s, startidx, idx));
            startidx = idx + 1;
        }
        idx ++;
    }
    while (idx < length);
    Console.WriteLine(watch.ElapsedMilliseconds);
    Console.ReadLine();
}


static int atoi(string c, int start, int len) {
  int res = 0;
  int i = start;
  len += start;
  while (i<len && c[i] >= '0' && c[i] <= '9')
    res = res * 10 + c[i++] - '0';
  return res;
}