Click here to Skip to main content
15,919,778 members
Home / Discussions / Algorithms
   

Algorithms

 
Question"Best Fit" Algorithm Request && Teach A Man To Fish Pin
Michael Fritzius17-Apr-10 13:10
professionalMichael Fritzius17-Apr-10 13:10 
AnswerRe: "Best Fit" Algorithm Request && Teach A Man To Fish Pin
Luc Pattyn17-Apr-10 13:45
sitebuilderLuc Pattyn17-Apr-10 13:45 
GeneralRe: "Best Fit" Algorithm Request && Teach A Man To Fish Pin
Radhakrishnan G.18-May-10 3:44
Radhakrishnan G.18-May-10 3:44 
GeneralRe: "Best Fit" Algorithm Request && Teach A Man To Fish Pin
harold aptroot17-Apr-10 14:31
harold aptroot17-Apr-10 14:31 
GeneralRe: "Best Fit" Algorithm Request && Teach A Man To Fish Pin
Som Shekhar17-Apr-10 20:46
Som Shekhar17-Apr-10 20:46 
GeneralRe: "Best Fit" Algorithm Request && Teach A Man To Fish Pin
harold aptroot18-Apr-10 2:01
harold aptroot18-Apr-10 2:01 
GeneralRe: "Best Fit" Algorithm Request && Teach A Man To Fish Pin
Som Shekhar18-Apr-10 2:18
Som Shekhar18-Apr-10 2:18 
GeneralRe: "Best Fit" Algorithm Request && Teach A Man To Fish [modified] Pin
harold aptroot18-Apr-10 2:38
harold aptroot18-Apr-10 2:38 
Time for some code! Smile | :)

This code is clearly crap, I just wrote it quickly in a console app to see whether it would work. It calculates the optimal solution with a simple branch and bound algorithm (without any tricks that can make it faster) - all cases that I tested worked.

For anything above 16 jobs it becomes really really slow. As a quick guestimate, the time complexity is about O(m^j) where m is the number of machines and j is the number of jobs.

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];
        }
    }
}


Edit: but I don't think using rectangles will help at all - if anything, it will just make it harder without having any benefits. The problem would still be the same, but you'd have "the width of a rectangle" instead of just "some integer or float" which is really just the same thing.
modified on Sunday, April 18, 2010 8:44 AM

GeneralRe: "Best Fit" Algorithm Request && Teach A Man To Fish Pin
Som Shekhar18-Apr-10 2:56
Som Shekhar18-Apr-10 2:56 
GeneralRe: "Best Fit" Algorithm Request && Teach A Man To Fish Pin
harold aptroot18-Apr-10 3:16
harold aptroot18-Apr-10 3:16 
GeneralRe: "Best Fit" Algorithm Request && Teach A Man To Fish Pin
Som Shekhar18-Apr-10 3:40
Som Shekhar18-Apr-10 3:40 
GeneralRe: "Best Fit" Algorithm Request && Teach A Man To Fish Pin
harold aptroot18-Apr-10 3:44
harold aptroot18-Apr-10 3:44 
GeneralRe: "Best Fit" Algorithm Request && Teach A Man To Fish Pin
Som Shekhar18-Apr-10 3:53
Som Shekhar18-Apr-10 3:53 
GeneralRe: "Best Fit" Algorithm Request && Teach A Man To Fish Pin
Michael Fritzius18-Apr-10 9:40
professionalMichael Fritzius18-Apr-10 9:40 
GeneralRe: "Best Fit" Algorithm Request && Teach A Man To Fish Pin
Luc Pattyn18-Apr-10 10:02
sitebuilderLuc Pattyn18-Apr-10 10:02 
GeneralRe: "Best Fit" Algorithm Request && Teach A Man To Fish Pin
Luc Pattyn18-Apr-10 10:07
sitebuilderLuc Pattyn18-Apr-10 10:07 
GeneralRe: "Best Fit" Algorithm Request && Teach A Man To Fish Pin
harold aptroot18-Apr-10 11:39
harold aptroot18-Apr-10 11:39 
GeneralRe: "Best Fit" Algorithm Request && Teach A Man To Fish Pin
Michael Fritzius19-Apr-10 11:59
professionalMichael Fritzius19-Apr-10 11:59 
GeneralRe: "Best Fit" Algorithm Request && Teach A Man To Fish Pin
Luc Pattyn19-Apr-10 12:45
sitebuilderLuc Pattyn19-Apr-10 12:45 
GeneralRe: "Best Fit" Algorithm Request && Teach A Man To Fish Pin
Tim Craig19-Apr-10 12:48
Tim Craig19-Apr-10 12:48 
GeneralRe: "Best Fit" Algorithm Request && Teach A Man To Fish [modified] Pin
harold aptroot19-Apr-10 12:56
harold aptroot19-Apr-10 12:56 
GeneralRe: "Best Fit" Algorithm Request && Teach A Man To Fish Pin
Tadeusz Westawic23-Apr-10 2:24
Tadeusz Westawic23-Apr-10 2:24 
AnswerRe: "Best Fit" Algorithm Request && Teach A Man To Fish Pin
Tadeusz Westawic23-Apr-10 3:57
Tadeusz Westawic23-Apr-10 3:57 
QuestionCSMA / CA Pin
hairy_hats14-Apr-10 4:59
hairy_hats14-Apr-10 4:59 
AnswerRe: CSMA / CA Pin
Anshul R9-Jun-10 4:14
Anshul R9-Jun-10 4:14 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.