Distribute a number of tasks into multiple days (scheduling)

Question

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.

Answer 1

Suppose that you have 200 tasks to be scheduled in 100 days. The capacity of each day is 4. Task 1 has capacity 1, task 200 has capacity 3, and tasks 2 to 199 have capacity 2.

In any solution, task 1 and task 200 have to be assigned to the same day. That means that there is a big violation of the ordering of the tasks. So even if you could solve your problem effectively, the best solution (which is indeed hard to compute) might still be very bad.

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.