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).

  • 1
    $\begingroup$ cs.stackexchange.com/tags/dynamic-programming/info $\endgroup$ – D.W. Apr 1 '19 at 6:08
  • 1
    $\begingroup$ I think you've misled yourself looking for different kinds of scheduling classifications (open shop vs job shop vs ...) . Instead you should be trying to figure out how to break down the stated problem into one with optimal substructure. You have two different sets here that can be broken into subsets: the list of tasks, and the remaining times of the week. You may (or may not) need to frame your problem in terms of subsets on either or both of those in order to implement a dynamic programming solution. $\endgroup$ – Wandering Logic Apr 1 '19 at 14:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.