# Tag Info

17

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

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

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 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 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 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 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$Sto the positive integers, giving the number of time units required by each job, and (4) a ... 3 Simple answer No, we cannot sort start time in ascending order to get a reasonable dynamic programming algorithm. A counterexample As illustrated above, we are given four jobs aligned in order of ascending start time, each labeled with its wight. Though some computation, we havep_4=3$and$OPT(4)=1+OPT(3)$. By definition,$OPT(3)\$ equals to the optimal ...

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