StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

POImplementing a dynamic multiple timeline queue
text
Body
copied!<h2>Introduction</h2> <p>I would like to implement a <em>dynamic multiple timeline queue</em>. The context here is <strong>scheduling</strong> in general.</p> <h2>What is a <em>timeline queue</em>?</h2> <p>This is still simple: It is a timeline of tasks, where each event has its start and end time. Tasks are grouped as jobs. This group of tasks need to preserve its order, but can be moved around in time as a whole. For example it could be represented as:</p> <pre><code> --t1-- ---t2.1-----------t2.2------- ' ' ' ' ' 20 30 40 70 120 </code></pre> <p>I would implement this as a <a href="http://docs.python.org/library/heapq.html" rel="nofollow noreferrer">heap queue</a> with some additional constraints. The Python <a href="http://docs.python.org/library/sched.html" rel="nofollow noreferrer"><code>sched</code></a> module has some basic approaches in this direction.</p> <h2>Definition <em>multiple timeline queue</em></h2> <p>One queue stands for a resource and a resource is needed by a task. Graphical example:</p> <pre><code>R1 --t1.1----- --t2.2----- -----t1.3-- / \ / R2 --t2.1-- ------t1.2----- </code></pre> <p><br/> </p> <h2>Explaining "<em>dynamic</em>"</h2> <p>It becomes interesting when a task can use one of multiple resources. An additional constraint is that consecutive tasks, which can run on the same resource, must use the same resource.</p> <p>Example: If (from above) task <code>t1.3</code> can run on <code>R1</code> or <code>R2</code>, the queue should look like:</p> <pre><code>R1 --t1.1----- --t2.2----- / \ R2 --t2.1-- ------t1.2----------t1.3-- </code></pre> <p><br/></p> <h2>Functionality (in priority order)</h2> <ul> <li><strong>FirstFreeSlot(duration, start)</strong>: Find the first free time slot beginning from <code>start</code> where there is free time for <code>duration</code> (see detailed explanation at the end).</li> <li><strong>Enqueue</strong> a job as earliest as possible on the multiple resources by regarding the constraints (mainly: correct order of tasks, consecutive tasks on same resource) and using <code>FirstFreeSlot</code>.</li> <li><strong>Put</strong> a job at a specific time and move the tail backwards</li> <li><strong>Delete</strong> a job</li> <li><strong>Recalculate</strong>: After delete, test if some tasks can be executed earlier.</li> </ul> <p><br/></p> <h2>Key Question</h2> <p>The point is: How can I <strong>represent</strong> this information to provide the functionality <strong>efficiently</strong>? Implementation is up to me ;-) </p> <p><strong>Update</strong>: A further point to consider: The typical interval structures have the focus on "What is at point X?" But in this case the <code>enqueue</code> and therefore the question "Where is the first empty slot for duration D?" is much more important. So a segment/interval tree or something else in this direction is probably not the right choice.</p> <p>To elaborate the point with the free slots further: Due to the fact that we have multiple resources and the constraint of grouped tasks there can be free time slots on some resources. Simple example: <code>t1.1</code> run on R1 for 40 and then <code>t1.2</code> run on R2. So there is an empty interval of <code>[0, 40]</code> on R2 which can be filled by the next job.</p> <hr> <p><strong>Update 2</strong>: There is an <a href="https://stackoverflow.com/a/1983402/851737">interesting proposal in another SO question</a>. If someone can port it to my problem and show that it is working for this case (especially elaborated to multiple resources), this would be probably a valid answer.</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

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