Scheduling Algorithm Help Please

  • 0 Replies
  • 2436 Views
*

robby87

  • Guest
Scheduling Algorithm Help Please
« on: August 25, 2009, 02:21:02 am »
I have written an algorithm based on heuristic assignments. This is how it works, it orders all events (Ei) by a set of heuristics, then iteratively solves each Ei such that no constraints are violated. It starts from the topmost event, and establishes Domain (Di) for the current Event, Ei, based on constraints. These constraints are worked out dynamically so that there is absolutely no conflict with any other related event and that is how Si is determined. Then is Si is not empty, it assigns any solution slot from Si to the current event Ei. Once an assignment is made, not a single constraint is violated, and on top of this, any event that could not be solved is left unsolved, and the solution assigned from Si is removed from the entire search space. So when the next event Ei+1 is being solved, it will establish Si+1 from the Search Space that will no longer containt the assigned slot from Si, typically that can be called Si1, while dynamically establishing the new constraint set to avoid any conflict whatsoever for the next event.

This is the problem, that while any assignment made is PERFECT, it can leave several slots unsolved. I have not added a backtracking, or other approach, as I do not want the algorithm to be affected exponentially in time.

How can I improve this alogorithm with a decent touch so that unsolved events may now become solved, while bearing in mind, a solved event must not fail a single constraint?

The improvement will mean that if the choice for particular Ei could have been different, there could have been a better solution, with possibly more events solved. Remember, any event solved is optimal (100/100) for its constraint set.

Please help if you can.