Databases
StackOverflow2013
Postsdbo
PO
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PO
    primarykey
    data
    text
    <p>After spend some time thinking through this. I think a <strong>segment tree</strong> might be more appropriate to model this timeline queue. The job concept is like a LIST data structure.</p> <p>I assume the Task can be modeled like this (PSEUDO CODE). The sequence of the tasks in the job can be assured by the start_time.</p> <pre><code>class Task: name='' _seg_starttime=-1; #this is the earliest time the Task can start in the segment tree, #a lot cases this can be set to -1, which indicates its start after its predecessor, #this is determined by its predecessor in the segment tree. #if this is not equal -1, then means this task is specified to start at that time #whenever the predecessor changed this info need to be taken care of _job_starttime=0; #this is the earliest time the Task can start in the job sequence, constrained by job definition _duration=0; #this is the time the Task cost to run def get_segstarttime(): if _seg_starttime == -1 : return PREDESSOR_NODE.get_segstarttime() + _duration return __seg_startime + _duration def get_jobstarttime(): return PREVIOUS_JOB.get_endtime() def get_starttime(): return max( get_segstarttime(), get_jobstarttime() ) </code></pre> <ul> <li><strong>Enqueue</strong> it is merely append a task node into the segment tree, notice the _seg_startime set to -1 to indicate it to be started right after it's predecessor</li> <li><strong>Put</strong> insert a segment into the tree, the segment is indicated by start_time and duration. </li> <li><strong>Delete</strong> remove the segment in the tree, update its successor if necessary( say if the deleted node do have a _seg_start_time present )</li> <li><strong>Recalculate</strong> calling the get_starttime() again will directly get its earliest start time. </li> </ul> <p>Examples( without considering the job constraint )</p> <pre><code> t1.1( _segst = 10, du = 10 ) \ t2.2( _segst = -1, du = 10 ) meaning the st=10+10=20 \ t1.3 (_segst = -1, du = 10 ) meaning the st = 20+10 = 30 </code></pre> <p>if we do a Put:</p> <pre><code> t1.1( _segst = 10, du = 10 ) \ t2.2( _segst = -1, du = 10 ) meaning the st=20+10=30 / \ t2.3(_segst = 20, du = 10) t1.3 (_segst = -1, du = 10 ) meaning the st = 30+10 = 30 </code></pre> <p>if we do a Delete t1.1 to original scenario</p> <pre><code> t2.2( _segst = 20, du = 10 ) \ t1.3 (_segst = -1, du = 10 ) meaning the st = 20+10 = 30 </code></pre> <p>Each resource could be represented using 1 instance of this interval tree egg.</p> <p>from the segment tree (timeline) perspective:</p> <pre><code>t1.1 t3.1 \ / \ t2.2 t2.1 t1.2 </code></pre> <p>from the job perspective:</p> <pre><code>t1.1 &lt;- t1.2 t2.1 &lt;- t2.2 t3.1 </code></pre> <p>t2.1 and t2.2 are connected using a linked list, as stated: t2.2 get its _sg_start_time from the segment tree, get its _job_start_time from the linked list, compare the two time then the actual earliest time it could run can be derived.</p>
    singulars
    1. This table or related slice is empty.
    1. POImplementing a dynamic multiple timeline queue
      singulars
      1. PTQuestion
    1. PTAnswer
    1. USMizipzor
    1. USzinking
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    1. CO+1 for the detailed explanation. But a segment tree is definitely not the right choice: " its content cannot be modified once the structure is built". And I don't think an interval tree is the optimal solution for this case either because I have no overlapping intervals on a single resource and the number of resources is small compared to the number of tasks. I think the right direction would be some binary structure per resource which are linked together.
      singulars
      1. PO
      1. USschlamar
    2. CO@ms4py I agree you said its content cannot be modified once structure built. but what really matters is merely the **start_time** of a task, that is why I construct start_time from various inner structures. which essentially makes us do not need to handle the **start_time**. maybe I am not making myself well understood, I was thinking this implementation could handle the functionalites you mentioned.
      singulars
      1. PO
      1. USzinking
    3. COI updated the question with an additional point to consider. And I don't see a representation of multiple resources in your model.
      singulars
      1. PO
      1. USschlamar
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload