search

tpaviot / ProcessScheduler

A Python package for automatic and optimized resource scheduling
https://processscheduler.github.io/
GNU General Public License v3.0
58 stars 17 forks source link

Breakable tasks #125

Closed tpaviot closed 10 months ago

tpaviot commented 1 year ago

This PR is a work in progress related to issues #117 and #124. A new class BreakableFixedDurationTask is created that can represent a task where time slots are not necessarily contiguous. The task with duration=n is split into n unitary tasks (unitary means duration is 1). For example:

from processscheduler import *

problem = SchedulingProblem("ShiftBreaks", horizon=10)

worker = Worker("Worker")

task = BreakableFixedDurationTask("Task", 5)
task.add_required_resource(worker)

# Lunch break
lunch = FixedDurationTask("Lunch", duration=1)
lunch.add_required_resource(worker)
TaskStartAt(lunch, 4)

solver = SchedulingSolver(problem)
solution = solver.solve()

solution.render_gantt_matplotlib()

results in the following Gant diagram breakable_task

@itopaloglu83 and @asoral any feedback? would it fit your needs?

itopaloglu83 commented 1 year ago

@tpaviot thank you for taking a go at this, it looks great.

From what I can surmise from the code (processscheduler/task.py), you're diving the task into unitary subtasks (each with a duration of 1 unit) and also adding a precedence constraint as well.

Do you think there is a way to ensure that the task will not be interrupted by another task? Somehow we need to say that no other task can be scheduled between the start and the end of breakable task although the lunch is also defined as a task.

In a similar attempt with Google OR Tools, I didn't break the task but instead used connecting variables and calculated the total task duration as the sum of task duration itself plus any resource breaks that fall between the task start and stop times. It is rather convoluted and not well documented at the moment.

https://github.com/google/or-tools/blob/stable/ortools/sat/docs/scheduling.md#detecting-if-two-intervals-overlap

tpaviot commented 1 year ago

I think there's an issue with the semantics of the "breakable task". You cannot represent a task that can be achieved in several time slots and, simultaneously, force the "breakable task" not to be "broken". There's something weird. Maybe it's because I don't have the use case. Another way would be to add a parameter that forces the BreakableTask to be broken over close time slots, for example, a task with a duration of 10 cannot exceed 15 between the start and the end.

itopaloglu83 commented 1 year ago

Yes, it is a unique use case. It only come into use if the task being scheduled might be longer than the maximum shift duration. e.g. resources are available for 8 hours a day and we need to schedule a task that is 12 hours. Or a previous task ends at a time that cannot accommodate the next task and results in an unused capacity.

Thank you for implementing the breakable tasks. I think that one would be useful as well.

codecov-commenter commented 1 year ago

Codecov Report

Patch coverage: 86.07% and project coverage change: -0.12 :warning:

Comparison is base (2572cd3) 95.29% compared to head (4af8658) 95.17%.

:exclamation: Your organization is not using the GitHub App Integration. As a result you may experience degraded service beginning May 15th. Please install the Github App Integration for your organization. Read more.

Additional details and impacted files ```diff @@ Coverage Diff @@ ## master #125 +/- ## ========================================== - Coverage 95.29% 95.17% -0.12% ========================================== Files 42 43 +1 Lines 4441 4520 +79 ========================================== + Hits 4232 4302 +70 - Misses 209 218 +9 ``` | [Impacted Files](https://app.codecov.io/gh/tpaviot/ProcessScheduler/pull/125?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=Thomas+Paviot) | Coverage Δ | | |---|---|---| | [processscheduler/\_\_init\_\_.py](https://app.codecov.io/gh/tpaviot/ProcessScheduler/pull/125?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=Thomas+Paviot#diff-cHJvY2Vzc3NjaGVkdWxlci9fX2luaXRfXy5weQ==) | `88.88% <ø> (ø)` | | | [processscheduler/task.py](https://app.codecov.io/gh/tpaviot/ProcessScheduler/pull/125?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=Thomas+Paviot#diff-cHJvY2Vzc3NjaGVkdWxlci90YXNrLnB5) | `93.47% <72.00%> (-4.76%)` | :arrow_down: | | [test/test\_breakable\_task.py](https://app.codecov.io/gh/tpaviot/ProcessScheduler/pull/125?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=Thomas+Paviot#diff-dGVzdC90ZXN0X2JyZWFrYWJsZV90YXNrLnB5) | `92.59% <92.59%> (ø)` | | ... and [1 file with indirect coverage changes](https://app.codecov.io/gh/tpaviot/ProcessScheduler/pull/125/indirect-changes?src=pr&el=tree-more&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=Thomas+Paviot)

:umbrella: View full report in Codecov by Sentry.
:loudspeaker: Do you have feedback about the report comment? Let us know in this issue.

asoral commented 1 year ago

This PR is a work in progress related to issues #117 and #124. A new class BreakableFixedDurationTask is created that can represent a task where time slots are not necessarily contiguous. The task with duration=n is split into n unitary tasks (unitary means duration is 1). For example:

from processscheduler import *

problem = SchedulingProblem("ShiftBreaks", horizon=10)

worker = Worker("Worker")

task = BreakableFixedDurationTask("Task", 5)
task.add_required_resource(worker)

# Lunch break
lunch = FixedDurationTask("Lunch", duration=1)
lunch.add_required_resource(worker)
TaskStartAt(lunch, 4)

solver = SchedulingSolver(problem)
solution = solver.solve()

solution.render_gantt_matplotlib()

results in the following Gant diagram breakable_task

@itopaloglu83 and @asoral any feedback? would it fit your needs?

This makes a lot of sense now. I think this was the missing link. Splitting the task into unitary sub-tasks and arranging these subtasks on the horizon based on constraints was really what I wanted.

I will test this PR and update the status

asoral commented 1 year ago

@tpaviot thank you for taking a go at this, it looks great.

From what I can surmise from the code (processscheduler/task.py), you're diving the task into unitary subtasks (each with a duration of 1 unit) and also adding a precedence constraint as well.

Do you think there is a way to ensure that the task will not be interrupted by another task? Somehow we need to say that no other task can be scheduled between the start and the end of breakable task although the lunch is also defined as a task.

In a similar attempt with Google OR Tools, I didn't break the task but instead used connecting variables and calculated the total task duration as the sum of task duration itself plus any resource breaks that fall between the task start and stop times. It is rather convoluted and not well documented at the moment.

https://github.com/google/or-tools/blob/stable/ortools/sat/docs/scheduling.md#detecting-if-two-intervals-overlap

I have a scenario that I can think of, let me know if the below scenario is what you are referring to too-

itopaloglu83 commented 1 year ago

@asoral your example would work okay and Task A would complete over the course of 3 working days and then the Task B would start.

However, imagine there was no dependency between Task A and B. And also due to some other constraint, Task B can only start one day after Task A. In that instance, the source might work on Task A first for one day, switch to Task B and work it to completion, and switch back to Task A. Which might not be okay under certain cases like manufacturing because switching between tasks sometimes require setup times etc. Depending on the task type, this can be very useful though.

Another approach to solving the same problem of task spanning multiple shifts would be to extend the apparent duration of the task until the work time of the resource is equal to task duration. e.g. this task takes 24 hours to complete but due to recourse breaks, it will start on Monday at 8am and end at Wednesday 5pm, which means it needs to stay on the schedule for 57 hours even though the work itself is 24 hours.

asoral commented 1 year ago

I tried it with 100 tasks with an average duration of 6hrs and it fails to give the output. It gives the below error and the process terminates

100 changes in 300 seconds. Saving... 18:19:17 redis_queue.1 | 48760:M 29 Jun 2023 18:19:17.049 * Background saving started by pid 50060 18:19:17 redis_queue.1 | 50060:C 29 Jun 2023 18:19:17.080 * DB saved on disk 18:19:17 redis_queue.1 | 50060:C 29 Jun 2023 18:19:17.081 * Fork CoW for RDB: current 0 MB, peak 0 MB, average 0 MB 18:19:17 redis_queue.1 | 48760:M 29 Jun 2023 18:19:17.150 * Background saving terminated with success

tpaviot commented 1 year ago

@asoral I must be able to duplicate the issue in order to deeply study what is going on and provide a fix, your report does not contain enough information