Stay organized with collections
Save and categorize content based on your preferences.
C++ Reference: class TaskSet
Note: This documentation is automatically generated.
Helper class to compute the end-min of a set of tasks given their start-min
and size-min. In Petr Vilim's PhD "Global Constraints in Scheduling",
this corresponds to his Theta-tree except that we use a O(n) implementation
for most of the function here, not a O(log(n)) one.
Advanced usage. Instead of calling many AddEntry(), it is more efficient to
call AddUnsortedEntry() instead, but then Sort() MUST be called just after
the insertions. Nothing is checked here, so it is up to the client to do
that properly.
Arguments: int task_to_ignore, int* critical_index
Returns the end-min for the task in the set. The time profile of the tasks
packed to the left will always be a set of contiguous tasks separated by
empty space:
[Bunch of tasks] ... [Bunch of tasks] ... [critical tasks].
We call "critical tasks" the last group. These tasks will be solely
responsible for the end-min of the whole set. The returned
critical_index will be the index of the first critical task in
SortedTasks().
A reason for the min end is:
- The size-min of all the critical tasks.
- The fact that all critical tasks have a start-min greater or equal to the
first of them, that is SortedTasks()[critical_index].start_min.
It is possible to behave like if one task was not in the set by setting
task_to_ignore to the id of this task. This returns 0 if the set is empty
in which case critical_index will be left unchanged.
Warning, this is only valid if ComputeEndMin() was just called. It is the
same index as if one called ComputeEndMin(-1, &critical_index), but saves
another unneeded loop.
[[["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\u003eThe \u003ccode\u003eTaskSet\u003c/code\u003e class in C++ is a helper class designed for computing the end-min of a task set based on their start times and durations.\u003c/p\u003e\n"],["\u003cp\u003eIt employs an efficient O(n) implementation for most functions, unlike the Theta-tree approach with O(log(n)) complexity.\u003c/p\u003e\n"],["\u003cp\u003eThe class provides methods to add, remove, and sort tasks, along with functionalities to calculate the end-min and identify critical tasks.\u003c/p\u003e\n"],["\u003cp\u003eThe \u003ccode\u003eTaskSet\u003c/code\u003e is particularly useful within scheduling constraints and optimization problems for determining the earliest possible completion time of a group of tasks.\u003c/p\u003e\n"]]],["The `TaskSet` class computes the end-min of a task set, using an O(n) implementation, unlike the O(log(n)) Theta-tree. Key actions include adding entries via `AddEntry` or `AddUnsortedEntry` (followed by `Sort`), adding an optimized `AddShiftedStartMinEntry` , removing entries via `RemoveEntryWithIndex`, clearing with `Clear`, and updating a datastructure via `NotifyEntryIsNowLastIfPresent`. `ComputeEndMin` calculates the end-min, identifying critical tasks; `GetCriticalIndex` retrieves the critical task index after `ComputeEndMin`. The `SortedTasks` method returns a sorted vector of entries.\n"],null,[]]
