# Distribute a number of tasks into multiple days (scheduling)

This is about scheduling. I have N tasks of different length and I have to schedule them into M days. Indeed, each day has a max capacity (usually they are the same). Parameters are tight in the sense, that the sum of taks' length is exactly the same as the sum of day's capacity, e.g. tasks of total length 150 must be scheduled into days of total capacity 150.

Resource sharing is not involved, but the ordering of task is important. Idealy, for every j > i, task Tj must be processed in the same day or later than task Ti. But then, the solution does not exist for the most cases. Thus, as few as possible tasks are allowed to be processed at most one day before a task with smaller index. If there is still no solution, as few as possible tasks are allowed to be processed at most two days before a task with smaller index, and so on.

This seems to me as an NP-hard problem. I have created an algorithm based on Binary Decision Diagrams, which performs an exhaustive search over all schedules but, of course, is quite limited by the size of the problem. I need a comparison with other solutions. Can you, please, suggest me some state-of-the-art approach to solve the given problem.

EDIT: I want to minimize how much the solution violates the natural ordering over how many times it violates the natural ordering.

• From your description it is not clear if you want to prioritize how many times you violate the natural ordering, or how much each earlier each task $j$ is scheduled before a task $i < j$. – Vincenzo Dec 7 '18 at 8:54

Even worse, even if we totally disregard the ordering constraint, there could still be no solution. Consider two days of capacity 7 and four tasks of length 2, 3, 3, 6, respectively. The total length is 14 = 2 $$\times$$ 7, yet there is no way to separate the tasks into two days of capacity 7. This problem (in which the precedences are not taken into account) is called the Partition problem, so that is one keyword you might want to search for. Unfortunately, checking if a solution to the Partition problem exists is a strongly NP-complete problem whenever you have 3 days or more.