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.

  • 1
    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 at 8:54

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.

  • Sure! But, giving the priority to the offset from the ideal solution, if the algorithm returns such bad solution this would at least suggest the user that he stated very bad limitations. Many thanks for your comment, I am not expecting the details of the algorithm here (otherwise I would go to SO), I am just curious if this can be seen as a variant of a Knapsack problem and if Greedy algorithm is good or there is something else. – meolic Dec 7 at 14:07

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.