I'm writing a "Chores Scheduler" in Python. It has to be implemented using dynamic programming and has to take in two types of chores, as below:
- Regular chores with a start time and end time (a real-life example of this may be taking classes at the same time from Monday to Friday). I need 5 of these in my implementation with dependencies (see under inputs).
- A list of jobs that may be executed at variable times (for example, I may go on a spontaneous dinner within a given timeframe OR I need to go to the post office a given day, which is only open between 9AM and 3PM). I need 3 of these, with dependencies (see under inputs).
Inputs: A list of all chores and constraints on each chore.
- To remember: Some chores are regular, others are variable (see above). Additionally:
- Chores have a weight (profit) which has to be optimized for. For example, going to lectures has a high importance/profit, while watching YoutTube videos may have a low profit/importance, even if I do both every day.
- Chores also have dependencies, i.e. one task depends on the completion of another. Real life example: To finish a paper, I must have done research prior (these being two separate jobs).
Output: Optimal schedule to follow in order. The output has to be "Optimal weight/profit is: x by doing these following jobs 'Job2', 'Job5', 'Job3'.
My question is: I've looked up a myriad of possible solutions, from Open Shop to Job Shop to Regular Weighted Job Scheduling (link to GeeksforGeeks). None of the problem classifications match what I need or how I might implement this. Is there some kind of a classification of these problems? Any similar problems? I'm having a difficult time structuring the problem and how it can potentially be solved (other than through dynamic programming, which is mandatory for this task).