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