16

I assume that an edge $(u,v)$ means that $u$ has to be executed before $v$. If this is not the case, turn around all edges. I furthermore assume that you are less interested in paths (those are already given by the DAG) than in a good execution strategy given the dependencies. You can easily adapt the topological sort procedure: instead of appending, merge ...


9

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

You need to determine at what time each job is completed. With a first-come-first-served scheduler, this is simple to calculate: each job starts as soon as the processor becomes free, and takes exactly its burst time to complete. You've already calculated the start and end times to calculate the wait times, so use that to obtain the turnaround time. For ...


8

As $m = k \times n$, we can look at this in terms of $k$ and $n$ instead of $n$ and $m$. Let's say $T_i$ is the time it takes the $i$-th processor to finish its work. As $n$ grows, the probability that $T_i$ = $5k$ (the processor was assigned only $T=5$ tasks) for some $i$ approaches $1$, so makespan being defined as $\mathrm{max}(T_i)$, $E[M]$ approaches $...


7

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

Update: For the new version where you try to minimize the makespan, your static schedule still has the optimal expected value. Let $M$ be the random variable for the makespan. Let $F_i$ be the time slave $i$ is finished. We then have that $M = \max_i(X_i)$. Let $c_i$ be the number of jobs allocated to slave $i$. Then we have that $X_i = \sum_{i=1}^{c_i} X =...


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

I am slightly confused. If $k$ is a constant, then you can try all $O(n^k)$ possible tours. Hence the problem is in ${\sf P}$. However, if $k$ is part of the input, the decision problem is ${\sf NP}$-complete. This can be shown by reducing $\text{HAM-CIRCUIT}$ to the problem, by the following reduction. Assume that we want to determine if a $n$-vertex ...


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

The problem minimizing maximal lateness is discussed in the algorithm book by Kleinberg and Tardos under greedy algorithms. The solution is like yours, ordering the tasks by their deadline. Indeed the length of the tasks is not relevant. The main ingredient of the proof is that any optimal solution $O$ can be transformed into this greedy one $G$ by swapping ...


4

Hint: Let $\sigma$ be the optimal schedule. Suppose that jobs $k$ and $k+1$ are switched. How is the cost affected? What does the optimality of $\sigma$ tell us about $w_k,w_{k+1},t_k,t_{k+1}$?


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

Use a dynamic programming algorithm to compute an $n \times n$ table $T$, where the entry $T(j,k)$ answers the question: suppose you wish to schedule $j$ out of the first $k$ jobs. What is the earliest time you can complete processing these? How do we compute $T(j,k+1)$? Either the job $k+1$ is included in the best set of $j$ out of $k+1$ jobs, so $$T(j,k+...


3

Here's a naive algorithm. It relies ultimately on brute force, but may perform okay sometimes. Each constraint $(\sigma_{m_i}, \sigma_{m_j}, \sigma_{m_k}) \in S \implies i < k \wedge \neg(i < j < k)$ consists of two conjuncts; let's call them type-$A$, $i < k$, and type-$B$, $\neg(i < j < k)$. Each type-$B$ constraint can be equivalently ...


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

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 ...


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