10

In searching around for an online presence for one of the classics in this field (Coffman, Denning: Operating Systems Theory, Prentice Hall, 1983) I came upon what looks like a comprehensive textbook with a Google books preview Pinedo: Scheduling: Theory, Algorithms, and Systems, Springer 2008. The author's homepage also has pages devoted to each of his ...


9

Given a 3CNF with clauses $\phi_1,\ldots,\phi_k$ on variables $x_1,\ldots,x_n$. Suppose both $x_i$ and $\overline{x_i}$ appear in the formula for at most $k_i$ times respectively. We design a colored DAG $G$ whose vertices consists of three parts: "Assignment" vertices $v_i(j)$ and $\bar{v}_i(j)$, $1\leq i\leq n$, $1\leq j\leq k_i$. Color $v_i(j)$ with the ...


8

The graph of overlapping jobs is an interval graph. Interval graphs are perfect graphs. So what you are trying to do is find a maximum weight independent set (i.e., no two overlap) in a perfect graph. This can be solved in polynomial time. The algorithm is given in "Polynomial Algorithms for Perfect Graphs", by M. Grötschel, L. Lovász, and A. Schrijver. ...


7

There are two categories of solutions to this sort of problem that I'm aware of: biased lotteries and filtered/generated random sequences. First, let's dispense with easy but wrong solutions that keep no state. Any lottery-style solution that maintains no state will have the number of wins in a binomial distribution, which fails the "as many times" ...


6

Greedy algorithm can't help in that case. And it couldn't be compared with both fractional or 0-1 knapsack problems. The first could be resolved by greedy algorithm in O(n) and the second is NP. The problem you have could be brute-forced in O(2^n). But you could optimize it using dynamic programming. 1) Sort intervals by start time. 2) Initialize int[] ...


5

The question is proven NP-hard in "Minimizing Makespan in a Two-Machine Flow Shop with Delays and Unit-Time Operations is NP-Hard" by W. Yu, H. Hoogeveen, and J.K. Lenstra (2004). This is proven in section 9 of the paper: Theorem 24. The problem of minimizing the makespan on a single machine with two unit time operations per job with arbitrary ...


5

This looks like the so called master-slave scheduling model introduced by Sahni. In particular, your problem falls under the Single-Master Master-Slave Systems. You can distinguish several cases: 1) If you do not add any additional constraint on the order of job execution (as in your case), the problem is called unconstrained minimum finish time problem (...


5

One could implement this in O(nlogn) Steps: Sort the intervals based on end time define p(i) for each interval, giving the biggest end point which is smaller than the start point of i-th interval. Use binary search to obtain nlogn define d[i] = max(w(i) + d[p(i)], d[i-1]). initialize d[0] = 0 The result will be in d[n] n- the number of intervals. ...


5

This seems to be exercise 9 from Kleinberg's Algorithm Design, chapter six. I'll report how i tried to solve it. Let's define $OPT(i)$ as the maximum amount of work from day $1$ to day $i$, with $i \leq n$ For every $i$, there can be a reboot in any previous day $1\leq j < i$. If it was on day $j$, than you processed $\sum_{k=j+1}^i \min\left\{s_{k-j}, ...


4

Let $\{P_1,...,P_n\}$ be the set of croissant's byers. Let ${v_i}^k-1$ be the amount spent by $P_i$ on croissant up to the day $k$ (it can be the number of times he buy croissant if they always spend the same money whatever the number of peoples present, which don't look clever enough for our croissants lover); the $-1$ is for initialisation and to avoid ...


4

For the Round-Robin Scheduler the quantum time is to ensure that each process has a share to the CPU and we don't have starvation problems. It's known for being fair, such that each process shares the CPU equality. Quantum time is it's the amount of time spent on each process in the CPU until we context switch to the next process in the ready queue. For ...


4

This sounds very much like a Hamilton path problem. If you set the edge weights all to $1$ and the deadline of the vertices all to $|V| - 1$, then each vertex can only be visited once, since there is not enough time to visit one twice before the deadline runs out. Finding a Hamilton path on the other hand is NP-hard. Thus, your problem is NP-hard as well.


4

When you compute the topological ordering, you usually select one node with no predecessor and remove it from the graph. Instead you can scan the whole list of vertices and select all source vertices and remove them at once, only then you update the degree of the remaining vertices. The groups of vertices you remove together represent tasks that can be ...


3

This has always troubled me too. The problem is with the origins of the English word and the difference between ordinal numbers ("first", "second", "third", ...) and cardinal numbers (the numbers you use to count things). In schedulers we use the word priority in the sense of: the right to take precedence or to proceed before others[1] It came into ...


3

The shortest-task-first heuristic is a 1/2-approximation algorithm. For a tight example, image that a compatible set $\{T_i\mid 1\leq i\leq m\}$ sorted by their finish time and the other shorter tasks $Y_i$, $1\leq i\leq m/2$, such that $Y_i$ overlaps with $T_{2i-1}$ and $T_{2i}$ for each $i$. The shortest-first heuristic finds $m/2$ tasks while the optimal ...


3

This is more a question of English than computer science. For almost any regular verb (and "schedule" is a perfect example), the [verb]er is the thing that does the [verb]ing. The scheduler is the software that schedules.


3

Since a customer must either be assigned all the requested hours or none at all, this problem is $NP$-complete. This can be seen by reduction from Exact Cover. A polynomial algorithm is unlikely to exist. Starting with biggest job first might be a reasonable heuristic for many cases, but there are no performance guarantees.


3

Simple Google search reveals a thesis from 2010 that defines and proves the complexity of scheduling university courses as NP-Complete. See Fig. 42 towards the end. Lovelace, April L. "On the complexity of scheduling university courses." (2010). There is also a technical report dating back to 1995 that does the same thing: Cooper, Tim B., and Jeffrey H. ...


3

When an I/O is started, it will typically have an I/O request structure associated with it that includes items like the process ID that the I/O belonged to. When the I/O completes the device driver will typically fork into an OS level I/O subsystem in the OS which will queue the IO request packet notification to the process and move the process to a ...


3

The greedy scheduling with a first fit resource selection is actually not correct. Consider the case where the intervals are: ${ (1, 3) , (2, 5) , (6, 7) , (4, 8) }$, for simplicity assume we only have 2 resources. The greedy algorithm will assign intervals 1, 2, 3 to resources 1, 2, 1 respectively and will fail to assign a resource for the last interval. ...


3

This scheduling problem is called non-preemptive job shop scheduling. The classic reference is Edward G Coffman, Jr, and Peter J Denning: Operating Systems Theory, Prentice-Hall, 1973. Job-shop scheduling is discussed in Section 3.7 and 3.8 (although they mainly focus on a restricted version of the problem called the flow shop problem where the $a_i$ ...


3

This solution has problems and will be deleted soon; see templatetypedef's comment. You can solve this in polynomial time using minimum-cost flow. In the following, all edges have unit capacity. Create a source vertex $s$, and a target vertex $t$. We will send $k$ units of flow from $s$ to $t$. Create $n+1$ vertices $v_0, \dots, v_n$ to represent the ...


3

The algorithms for $n$ processors will do the job just fine for the 2-processor case. In this context, $n$ does not refer to the number of tasks to be scheduled, which probably caused the confusion when you looked for algorithms. Then, there is a great website for searching for scheduling problems, which you can access at http://www-desir.lip6.fr/~durrc/...


3

The strategy to prove your ratio greedy algorithm is what I called "unimprovable solution by exchange of elements". Instead of proving that an algorithm produces the optimal solution, this strategy require you to show that every optimal solution that cannot be improved by an exchange of two or more elements must be or must be equivalent to the solution ...


3

Found it! This problem is NP-complete when the goal is to minimize total execution time. The scheduling problem (P1) is the following. We are given (1) a set $S = \{J_1 , \ldots , J_n\}$ of jobs, (2) a partial order $\prec$ on $S$, (3) a weighting function $W$ from $S$ to the positive integers, giving the number of time units required by each job, and (4) a ...


3

You're asking to enumerate all maximum matchings in a bipartite graph. Unfortunately that problem is #P-complete, so there is unlikely to be any efficient algorithm that works on arbitrary size graphs. There might be algorithms that work well enough for your situation, given the small numbers you're dealing with. For instance, a simple approach is to use ...


3

The problem is NP-hard, at least for a particular simplified configuration. Assume that each $m_l$ is effectively infinite - we can scan a particular libraries' books all on the day we get access. Let all $d_l = 1$ - each library takes one day to get access to, meaning we get access to exactly $n$ libraries. Now if $P_b = 1$ the thing that maximizes our ...


2

Well since no one else is giving an answer, here goes: Assume the jobs are represented as $J=\{x_1,\ldots,x_n\}$ Since $P_1$ must process only one job at a time, it doesn't matter which order the jobs are processed, the time taken by $P_1$ is always the same, $\sum_{i=1}^n t_{i,1}$, each job's 3 parts are represented as $(t_{i,1},t_{i,2},t_{i,3})$. So to ...


2

I find that heuristic arguments are often quite misleading when considering task scheduling (and closely related problems like bin packing). Things can happen that are counter-intuitive. For such a simple case, it is worthwhile actually doing the probability theory. Let $n = km$ with $k$ a positive integer. Suppose $T_{ij}$ is the time taken to complete ...


2

In textbooks, the solution given is 6+8+13+20+21= 68/5 = 13.6 This is because the textbooks (including Operating System Concepts 8e by Silberschatz,Gagne,Gelvin) define turnaround time as the time that elapses between the submission and the termination of the process, which is the sum of arrival time, waiting time, execution time and time spent in device ...


Only top voted, non community-wiki answers of a minimum length are eligible