Dynamic Programming - Break Scheduling Problem With Decreasing Work Capacity

Question

Assume you are given t1, t2, t3, ..., tn amount of tasks to finish every day. And once you start working, you can only finish c1, c2, c3, ..., cn tasks until spending 1 day resting. You can spend multiple days resting too. But you can only do the tasks which are given you that day. For example;

T[] = {10, 1, 4, 8} given tasks;
C[] = {8, 4, 2, 1} is the capacity of doing tasks for each day.

For this example, optimal solution is giving a break on the 3rd day. That way you can complete 17 tasks in 4 days:

1st day 8 (maximum 10 tasks, but c1=8)
2nd day 1 (maximum 1 task, c2=4)
3rd day 0 (rest to reset to c1)
4th day 8 (maximum 8 tasks, c1=8)

Any other schedule would result with fewer tasks getting done.

I'm trying to find the recurrence relation for this dynamic programming problem. Can anyone help me? I find this question but mine is different because of the decreasing work capacity and there are different number of jobs each day. Reference

I find the problem statement confusing, can you elaborate with several examples what you are trying to solve for? The example you gave, solving for 17 tasks in 4 days does not seem to solve your problem (which has 10+1+4+8=23 tasks in total.) Please spend some time explaining your problem and what you want to compute more clearly. — ldog
Hi @ldog, We can't complete all 23 tasks because we can only complete 8 task the first day of work, 4 tasks 2nd day, 2 tasks 3rd day and 1 task 4th day. Because we get tired. After taking a 1 day break, our capasity to complete tasks is 8 again, then next day it is 4 and so on. Question is, what is the maximum number of tasks that can be completed. We can only take the tasks which are given to us that day and complete as many of them as we are capable of that day. Tasks we couldn't complete the day they are given is discarded and can not be completed next day. — ogzhnozclk

DuDa DuDa · Accepted Answer · 2021-01-21T23:23:11

If I got you right you have an amount of tasks to do, t(i) for every day i. Also you have some kind of a given internal restriction sequence c(j) for a current treak day j where j can be reseted to 0 if no task was done that day. Goal is to maximizie the solved tasks.

Naive approach is to store for each day i a list for every state j how many tasks were done. Fill the data for the first day. Then for every following day fill the values for the "no break" case - which is value(i-1,j-1)+min(t(i),c(j)). Choose the maximum from the previous day to fill the "break" entry. Repeat until last day. Choose the highest value and trace back the path.

Example for above

Memory consumtption is pretty easy: O(number of days * number of states).
If you are only interested in the value and not the schedule the memory consumption would be the O(number of states).

Time consumption is a bit more complex, so lets write some pseudo code:

For each day i
    For each possible state j
        add and write values
    choose maximum from previous day for break state
choose maximum
For each day
    trace back path

The choose maximum-function would have a complexity of O(number of states).

This pseudo code results in time consumption O(number of days * number of states) as well.

Dynamic Programming - Break Scheduling Problem With Decreasing Work Capacity

1 Answers