Thread: For those of you who helped - thanks! SOLUTION

Hi guys,

Thanks to those of you who helped with my scheduling problem. I have finally gotten it to work, and will post the iterative solution. Special thanks to codeplug for the assistance with the recursive stack frame imitation. Also, others had a lot of interest in this problem ( PJYelton for one ) My code has a few bounds in it, to attempt to speed it up ( I check to see if it is possible to beat my current best solution...if not, then I stop traversing. Also, if a job doesn't conflict with any other jobs, then I don't give it the option to NOT be scheduled. ) If anyone can think of other "bounds" that would allow me to prune the tree, that would be great!

Thanks again guys!

Code:

void solveIter()
{
   
    stack<StackStructType> callStack;
    StackStructType current, previous;

    previous.job = -1;
    previous.comp = '-';
    
    current.job = 0;
    current.comp = '-';
    callStack.push(current);
    for (int i = Job::getMachPerJob() - 1; i >= 0 ; i--)
    {
        current.comp = jobs[current.job].getComp(i);   
        callStack.push(current);
    }
    while (!callStack.empty())
    {
        current = callStack.top();
        callStack.pop();
         
        if (previous.job >= current.job && previous.comp != '-' && jobs[previous.job].getScheduled())
        {
            computers[previous.comp - 97].removeJob();
            numOfJobs--;
            jobs[previous.job].setSchedule('-'); // Probably don't need this
            jobs[previous.job].setScheduled(false);            
        }

        if (jobs[current.job].getScheduled())
        {
            computers[jobs[current.job].getSchedule() - 97].removeJob();
            numOfJobs--;
            jobs[current.job].setSchedule('-');
            jobs[current.job].setScheduled(false);            
        }

        previous = current;

            if (current.comp != '-' && !computers[current.comp - 97].isAvailable(jobs[current.job].getStart()))
            {
                continue;
            }
            
            if (current.comp != '-' && computers[current.comp - 97].isAvailable(jobs[current.job].getStart()))
            {
                 
                numOfJobs++;
                jobs[current.job].setSchedule(current.comp);
                jobs[current.job].setScheduled(true);
                if (numOfJobs > currentBest)
                {
                    currentBest = numOfJobs;
                    best = jobs;
                }
                computers[current.comp - 97].addJob(jobs[current.job].getEnd());
                
                if (numOfJobs + 1 + jobSize - current.job - 1 - numOfConflicts(current.job) <= currentBest)
                {
                    numOfJobs--;
                    computers[current.comp - 97].removeJob();
                    jobs[current.job].setSchedule('-');
                    jobs[current.job].setScheduled(false);
                    continue;
                }
            }
            
            
            if (current.job + 1 < jobSize)
            {
                current.job += 1;
                current.comp = '-';
                callStack.push(current);
                for (int i = Job::getMachPerJob() - 1; i >= 0; i--)
                {
                    current.comp = jobs[current.job].getComp(i);   
                    callStack.push(current);
                }                
            }
    }
}