Practically solving factorial-complexity problems ( scheduler )

Question

Given i have this O(n!) scheduler-problem:

• There are 10 Tasks with different durations, that I want to schedule during a workweek of 5 days
• Each day has 8 work hours, separated into 15 min. slots (1 day = 8 hrs = 32 slots)
• The tasks have different requirements in terms of "allowed days and time ranges" (e.g., a task may only be allowed on thursdays between 8am and 9am, another one only on mondays, tuesdays and wednesdays between 10am - 11am)

Requested result: There should be as many "consecutive free slots" available to later assign more/other tasks

Current solution: I tried to combine all possible slots via a BFS/DFS solution and then afterwards finding the best combination without overlapping tasks and the "biggest chunks of free slots". This solution kills me in performance and/or memorywise because of the O(n!) complexity.

Question: What is the most "reasonable" approach computer science has to offer (or maybe you solved a problem like this before) to solve this problem in a limited amount of time.

Answer 1

Here are a couple of things that could be added relatively easily to a depth first search approach that explored the most promising children first:

1) Limited Discrepancy Search - basically you score partially expanded solutions by accumulating x penalty points when you explore a child that is the xth best child of its node, and you discard partial solutions that have accumulated more than some threshold of total penalty points. Searching on the phrase Limited Discrepancy Search should give you lots of hits. This should at least stop your search running for n! seconds.

2) Given a possibly illegal putative solution, use it as the start of a hillclimbing process to improve it or at least try to make it legal. You need to do this anyway to eliminate the possibility that your program produces solutions in which users can find trivial improvements.

Answer 2

You can probably solve this using OptaPlanner, which is open source.

Another option is to quickly find a solution using a greedy algorithm, scheduling the most constrained tasks first and the least constrained tasks last. Next, use a local search to a. make the greedy solution valid and b. improve the greedy solution. For example, the greedy solution may leave you with an unscheduled task, so the local search unschedules a conflicting task and schedules the unscheduled task in its place, then re-schedules the newly unscheduled task.

Answer 3

I would use (recursive) backtracking, because of the restrictions on the tasks (allowed days and time ranges).

From Wikipedia (http://en.wikipedia.org/wiki/Backtracking):

Backtracking is a general algorithm for finding all (or some) solutions to some computational problem, that incrementally builds candidates to the solutions, and abandons each partial candidate c ("backtracks") as soon as it determines that c cannot possibly be completed to a valid solution.

For your problem. I would say, let's assign to every task the possible days to schedule. Here is a general solution.

M[level] means the set of the possible solution for the sub problem (R[level])

Backtracking(level = 0, result={0})
i = 0
Do
    i = i + 1 
    //With i - iterate over the possible solutions to result[level] (iterate over M[level])
    If(R[i] is a good result candidate) 
        k = 1
        While(k<level AND (R[k],R[i] are good solutions together)) k++
        If(k == level) //R[i] is a good result, it's in harmony with the results found before
            result[level] = R[i]
            If(level == N)
                bestResult = Max/Min(bestResult,result)
            Else
                Backtracking(level+1,result) //Backtracks
While(i<M[level])

Answer 4

Might want to consider simple AI such as https://en.wikipedia.org/wiki/Support_vector_machine

There are some libraries available for you to take a stab at:

Support Vector Machine library for C#

Also, Boli has a good solution (recursive backtracking). See the comment for an example video.

Answer 5

Your numbers are so small this immediately looks like a candidate for a brute force approach across all possible solutions mapped to a degree of success (utility) function.

Answer 6

I always prefer to create custom solutions for a problem rather than to rely on generic methodologies. In this specific case, the problem is quite well defined and I think that there is a quick and reliable iterative proceeding which can be defined relatively easily: basing the analysis on a sequential assignation of tasks by following the idea of "filling days" until being completed.

The algorithm would be iterating through the available (5) days, adding up the time associated with each task being assigned and comparing the resulting addition against the remaining available time for the given day. It would consist in two main parts:

---

1. Top priority assignation. Right at the start, the algorithm would be calculating the "flexibility" of the given day: it would add up all the time-slots of the tasks which have to be done on the given day. If they consume all the available time, the assignation of all these tasks would be done right away and would skip directly to the next day. In case of having available time, the algorithm would only assign the tasks with a detailed (time/day) definition; example: task to be performed on Mondays including the given slot (e.g., 9 to 9:15). After completing the assignation of all the defined-in-detail tasks, it would add up the whole time required by the remaining tasks to be done on the given day; this value is what I refer below as "remanent for the day"; the tasks belonging to this group (i.e., unassigned ones to be done on the given day) would be flagged such that the next point can deal with them properly.

2. Default preference rules. In case of not having assigned all the available time for the given day in the point above, a new iteration through all the tasks (not belonging to the aforementioned ones flagged for the given day) would be started by applying a system of generic preference rules (as described in the example below). Before assigning any new task, the algorithm would check whether there is still enough time to account for all the "remanent for the day". If the new-to-be-assigned task depletes the available time (i.e., avoids the "remanent for the day" to be assigned), the algorithm would keep iterating through the "preferred tasks" (the ones not belonging to the "remanent of the day") until finding one whose assignation would not deplete the available time. In case of not finding such a task, all the tasks belonging to the "remanent of the day" would be assigned right away and the algorithm would skip to the next day.

EXAMPLE OF PREFERENCE RULES FOR POINT 2: for the 9 to 9:15 slot on Monday; inspect firstly tasks allocated to the specific time independently upon the day (it wouldn't be Monday because these cases are already managed by point 1); then the biggest tasks (higher number of slots) which might be done on Mondays. It would also be possible to create a ranking for tasks in case of being in this last situation (e.g., in case of starting the last ordering by size, task X would have the maximum priority for Mondays).

---

The algorithm described above (or any other on these lines) represents the quickest option I can come up with for the problem you have. It focuses mainly on speed and reliability and thus the "many consecutive free slots" constraint is not fully optimised; although there is a tendency towards creating those (mainly during the last days of the week). Nonetheless, this last issue might be improved further by increasing the level of detail for the rules in point 2 (mainly the ones for tasks assigned by their time size). In summary, I do consider that an approach on these lines would deliver the best solution for the problem you propose.