Algorithm: How to plan / allocate hours to / from the weekly quota?

If I have, say, 5days * (8hourWorkday-2hoursForUnexpectedWork) = 30 hours per week to use, how can I programmatically schedule tasks to fill those 30 hours?

For example, I have 5 tasks, each of which I estimate will take the following amount of time:

#1:  2h
#2:  4h
#3:  6h
#4:  8h
#5: 10h

      

How would I sort this by saying:

M: #1 @ 2h + #2 @ 4h
T: #3 @ 6h
W: #4 @ 6h
H: #4 @ 2h + #5 @ 4h
F: #5 @ 6h

      

In other words, how do you account for "overflow"?

Ultimately, I also need to account for tasks that overwhelm the week, for example, if in the previous example I had a task #6: 40h

(itself for 10 hours more than a week, and bringing the weekly amount to 40h is additional that will need to be shed in the previous two weeks).

EDIT:

A second, more complex example, again with 5 tasks, this time with (optional) requirements for the day of the week:

#1:  2h, W[0][M]
#2:  4h, W[0][T]
#3:  6h, W[0][M]
#4:  8h, W[0][F]
#5: 40h, W[0][F]

      

How can I sort this, say

W[-1][M]: #5 @ 6h
W[-1][T]: #5 @ 6h
W[-1][W]: #5 @ 6h
W[-1][H]: #5 @ 6h
W[-1][F]: #3 @ 2h + #5 @ 4h
W[ 0][M]: #1 @ 2h + #3 @ 4h
W[ 0][T]: #2 @ 4h + #5 @ 2h
W[ 0][W]: #5 @ 6h
W[ 0][H]: #4 @ 2h + #5 @ 4h
W[ 0][F]: #4 @ 6h

      

Illustration # 1

The best scenario would actually be # 3 pushing # 1 back in the day, as shown here: Illustration # 2

Further clarification:

  • For each specified day of the week (MTWHF), complete up to 6 hours.
  • If overflow occurs, spill the previous day.
  • Ideally, this spill would be Knapsack-or-like-optimized so that 6 hours would be filled as much as possible with whole / unidentified tasks.
  • Likewise, during the days that spill, they have to correct their leak in order to be a solid task — unrecoverable as well.
+3


source to share


2 answers


If I am missing something, it looks like a problem. If tasks are dynamically assigned (as appears to be in a real environment) with the earliest deadline at the start , scheduling can meet all deadlines if utlization remains manageable. Since jobs are unloaded only when new jobs are available, this should result in low context switching costs and pretty good adjoining jobs. This is a simple heuristic that has received some attention in the literature, so a lot of guesswork has come out of the teaching.

EDIT: example.

#1:  2h, W[0][M]
#2:  4h, W[0][T]
#3:  6h, W[0][M]
#4:  8h, W[0][F]
#5: 40h, W[0][F]

EDF order: #1, #3, #2, #4, #5.

Schedule: 113333332222444444445555555555555555555555555555555555555555

In days: 113333 332222 444444 445555 555555 555555 555555 555555 555555 555555

      



Note that we could have done better in terms of adjacency by taking this prior schedule and post-processing the EDF scheduling results. Assuming we have the context overhead when the day starts and whenever the number changes, this schedule gives 13 context switches, of which only 10 are required. With graph # 3, # 1, # 2, # 4, # 5, we get 12 context switches. I know there was originally a question that required minimizing context switches. However, the optimal scheduling algorithm in this regard would be better than EDF, hiding the genuine context switches in the mandatory context switches (which happen early in the day). The advantage of EDF is that you always meet your deadlines if you can meet deadlines.It's a compromise, but I think the nod goes to EDF.

Also consider the speed of monotonous scheduling (assuming your deadline period), which may be more appropriate for statically defined schedules, especially if there is any regularity in assigned tasks.

+2


source


Looks like a backpack problem . The wiki provides some solutions to this problem, but it is mostly solved with dynamic programming.



+1


source







All Articles