operations_research::sat::TaskSet Class Reference

#include <disjunctive.h>

Classes
struct	Entry

Public Member Functions
	TaskSet (int num_tasks)
void	Clear ()
	Insertion and modification. These leave sorted_tasks_ sorted.
void	AddEntry (const Entry &e)
void	AddShiftedStartMinEntry (const SchedulingConstraintHelper &helper, int t)
void	NotifyEntryIsNowLastIfPresent (const Entry &e)
void	AddUnsortedEntry (const Entry &e)
void	Sort ()
IntegerValue	ComputeEndMin (int task_to_ignore, int *critical_index) const
IntegerValue	ComputeEndMin () const
int	GetCriticalIndex () const
absl::Span< const Entry >	SortedTasks () const

Detailed Description

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.

Definition at line 54 of file disjunctive.h.

Constructor & Destructor Documentation

TaskSet()

operations_research::sat::TaskSet::TaskSet ( int num_tasks )

inlineexplicit

Definition at line 56 of file disjunctive.h.

Member Function Documentation

AddEntry()

void operations_research::sat::TaskSet::AddEntry

(

const Entry &

e

)

If the task is added after optimized_restart_, we know that we don't need to scan the task before optimized_restart_ in the next ComputeEndMin().

Definition at line 165 of file disjunctive.cc.

AddShiftedStartMinEntry()

void operations_research::sat::TaskSet::AddShiftedStartMinEntry	(	const SchedulingConstraintHelper &	helper,
		int	t )

Same as AddEntry({t, helper->ShiftedStartMin(t), helper->SizeMin(t)}). This is a minor optimization to not call SizeMin(t) twice.

Definition at line 180 of file disjunctive.cc.

AddUnsortedEntry()

void operations_research::sat::TaskSet::AddUnsortedEntry ( const Entry & e )

inline

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.

Definition at line 86 of file disjunctive.h.

Clear()

void operations_research::sat::TaskSet::Clear ( )

inline

Insertion and modification. These leave sorted_tasks_ sorted.

Definition at line 68 of file disjunctive.h.

ComputeEndMin() [1/2]

IntegerValue operations_research::sat::TaskSet::ComputeEndMin

(

)

const

Definition at line 204 of file disjunctive.cc.

ComputeEndMin() [2/2]

IntegerValue operations_research::sat::TaskSet::ComputeEndMin	(	int	task_to_ignore,
		int *	critical_index ) const

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.

The order in which we process tasks with the same start-min doesn't matter.

If the ignored task is last and was the start of the critical block, then we need to reset optimized_restart_.

Definition at line 220 of file disjunctive.cc.

GetCriticalIndex()

int operations_research::sat::TaskSet::GetCriticalIndex ( ) const

inline

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.

Definition at line 114 of file disjunctive.h.

NotifyEntryIsNowLastIfPresent()

void operations_research::sat::TaskSet::NotifyEntryIsNowLastIfPresent

(

const Entry &

e

)

Advanced usage, if the entry is present, this assumes that its start_min is >= the end min without it, and update the datastructure accordingly.

Definition at line 186 of file disjunctive.cc.

Sort()

void operations_research::sat::TaskSet::Sort ( )

inline

Definition at line 87 of file disjunctive.h.

SortedTasks()

absl::Span< const Entry > operations_research::sat::TaskSet::SortedTasks ( ) const

inline

Definition at line 116 of file disjunctive.h.

---

The documentation for this class was generated from the following files:

• ortools/sat/disjunctive.h
• ortools/sat/disjunctive.cc