Stay organized with collections
Save and categorize content based on your preferences.
C++ Reference: class TimeTableEdgeFinding
Note: This documentation is automatically generated.
TimeTableEdgeFinding implements the timetable edge finding filtering rule
presented in Vilim Petr, "Timetable edge finding filtering algorithm for
discrete cumulative resources", CPAIOR 2011,
http://vilim.eu/petr/cpaior2011.pdf.
This propagator runs in O(n^2) where n is the number of tasks. It increases
both the start times and decreases the ending times of the tasks.
Note that this propagator does not ensure that the cumulative constraint
holds. It should thus always be used with at least a timetable propagator.
ALOGRITHM:
The algorithm relies on free tasks. A free task is basically a task without
its mandatory part. For instance:
s_min s_max e_min e_max
v v v v
task: =============================
^ ^ ^
| free part | Mandatory part |
Obviously, the free part of a task that has no mandatory part is equal to the
task itself. Also, a free part cannot have a mandatory part by definition. A
fixed task thus have no free part.
The idea of the algorithm is to use free and mandatory parts separately to
have a better estimation of the energy contained in a task interval.
If the sum of the energy of all the free parts and mandatory subparts
contained in a task interval exceeds the amount of energy available, then the
problem is unfeasible. A task thus cannot be scheduled at its minimum start
time if this would cause an overload in one of the task intervals.
[[["Easy to understand","easyToUnderstand","thumb-up"],["Solved my problem","solvedMyProblem","thumb-up"],["Other","otherUp","thumb-up"]],[["Missing the information I need","missingTheInformationINeed","thumb-down"],["Too complicated / too many steps","tooComplicatedTooManySteps","thumb-down"],["Out of date","outOfDate","thumb-down"],["Samples / code issue","samplesCodeIssue","thumb-down"],["Other","otherDown","thumb-down"]],["Last updated 2024-08-06 UTC."],[[["\u003cp\u003eTimeTableEdgeFinding is a filtering algorithm for scheduling problems, improving start and end times based on resource capacity.\u003c/p\u003e\n"],["\u003cp\u003eIt works by analyzing free and mandatory parts of tasks to estimate resource usage and prevent overload.\u003c/p\u003e\n"],["\u003cp\u003eThe algorithm has a time complexity of O(n^2), where 'n' represents the number of tasks.\u003c/p\u003e\n"],["\u003cp\u003eThis propagator doesn't guarantee constraint satisfaction on its own; it should be paired with a timetable propagator for complete functionality.\u003c/p\u003e\n"],["\u003cp\u003eThe core concept involves identifying potential resource overloads within task intervals and adjusting task timings to avoid them.\u003c/p\u003e\n"]]],["The `TimeTableEdgeFinding` class implements a filtering algorithm for cumulative resources, operating in O(n²) time, where n is the number of tasks. It refines task start and end times by analyzing \"free\" and \"mandatory\" task parts to estimate energy usage within intervals. The core algorithm checks for overloads by comparing the energy of all free and mandatory parts within a task interval against the available energy. `Propagate` checks for feasibility. `RegisterWith` attaches to the watcher. `TimeTableEdgeFinding` is the constructor. It must be used with another propagator.\n"],null,["# TimeTableEdgeFinding\n\nC++ Reference: class TimeTableEdgeFinding\n=========================================\n\n\nNote: This documentation is automatically generated.\nTimeTableEdgeFinding implements the timetable edge finding filtering rule presented in Vilim Petr, \"Timetable edge finding filtering algorithm for discrete cumulative resources\", CPAIOR 2011, \u003chttp://vilim.eu/petr/cpaior2011.pdf\u003e. \n\nThis propagator runs in O(n\\^2) where n is the number of tasks. It increases both the start times and decreases the ending times of the tasks. \n\nNote that this propagator does not ensure that the cumulative constraint holds. It should thus always be used with at least a timetable propagator. \n\nALOGRITHM: \n\nThe algorithm relies on free tasks. A free task is basically a task without its mandatory part. For instance: \n\ns_min s_max e_min e_max v v v v task: ============================= \\^ \\^ \\^ \\| free part \\| Mandatory part \\| \n\nObviously, the free part of a task that has no mandatory part is equal to the task itself. Also, a free part cannot have a mandatory part by definition. A fixed task thus have no free part. \n\nThe idea of the algorithm is to use free and mandatory parts separately to have a better estimation of the energy contained in a task interval. \n\nIf the sum of the energy of all the free parts and mandatory subparts contained in a task interval exceeds the amount of energy available, then the problem is unfeasible. A task thus cannot be scheduled at its minimum start time if this would cause an overload in one of the task intervals.\n\n| Method ||\n|----------------------------------------------------------------------------------------------------------------|-----------------------------------------------------------------------------------------------------------------------------------------|\n| [`Propagate`](https://github.com/google/or-tools/blob/v9.4/ortools/sat/timetable_edgefinding.h#L67) | Return type: `bool ` \u003cbr /\u003e |\n| [`RegisterWith`](https://github.com/google/or-tools/blob/v9.4/ortools/sat/timetable_edgefinding.h#L69) | Return type: `void ` Arguments: `GenericLiteralWatcher* watcher` \u003cbr /\u003e |\n| [`TimeTableEdgeFinding`](https://github.com/google/or-tools/blob/v9.4/ortools/sat/timetable_edgefinding.h#L63) | \u003cbr /\u003e Arguments: `AffineExpression capacity, SchedulingConstraintHelper* helper, SchedulingDemandHelper* demands, Model* model` \u003cbr /\u003e |"]]
