StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>This is actually more than a sorting problem. It's a single-machine scheduling problem with release dates. Depending on what you are trying to do, the problem might be NP-Hard. For example, if you are trying to mimimize the weighted-sum of the completion times (the weight being inversely proportional to the priority), the the problem is <a href="http://www.lix.polytechnique.fr/~durr/query/search.php?a1=1&a2=%3B&a4=%3B&a3=&b1=r_i&b3=&b7=&b4=&b5=&b6=&b8=&c=sum+w_iC_i&problem=1|r_i|sum+w_iC_i" rel="noreferrer">categorized</a> as</p> <pre><code>1|ri;pmtn|Σ wiCi </code></pre> <p>and is NP-hard. There are numerous <a href="http://www-math.mit.edu/~goemans/GoemansQSSW-2002-SingleMachineSchedulingWithReleaseDates.pdf" rel="noreferrer">papers</a> on this topic, but it might be more than what you need.</p> <p>In your case, you never want a solution with gaps, so what you might just need to do is a simple discrete-event simulation ( O(n log(n)) ) time. You need to store released_jobs as a priority queue.</p> <pre><code>unreleased_jobs = jobs // sorted list of jobs, by release date released_jobs = {} // priority queue of jobs, by priority scheduled_jobs = {} // simple list while (!unreleased_jobs.empty() || !released_jobs.empty()) { while (unreleased_jobs.top().earliestTime <= t) { released_jobs.push(unreleased_jobs.pop()) } if (!released_jobs.empty()) { next_job = released_jobs.pop(); scheduled_jobs.push_back(next_job) t = t + next_job.duration } else { // we have a gap t = unreleased_jobs.top().earliestTime } } </code></pre> <p>One problem is that you might have a low-priority job with a release time just before a short, high-priority job, but it will produce a schedule with the property that there are no gaps (if a schedule with no gaps is possible).</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