9 votes
Accepted

Selling blocks of time slots

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 ...
user avatar
  • 1,163
5 votes
Accepted

Using dynamic programming to maximize work done

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 \...
user avatar
  • 302
4 votes
Accepted

Round-Robin Scheduler - What exactly is the quantum time used for?

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 ...
user avatar
4 votes
Accepted

Why does lower integer represent higher priority in scheduling literature?

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 ...
user avatar
4 votes
Accepted

NP-hardness of a scheduling problem

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 ...
user avatar
4 votes
Accepted

Correctness proof for greedy algorithm based on ratio

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 ...
user avatar
  • 34.7k
4 votes

Scheduling task optimization

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 ...
user avatar
  • 176
3 votes

Designing a scheduling algorithm

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 ...
user avatar
3 votes

Does a greedy task selection algorithm find a c-approximate solution?

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 ...
user avatar
  • 458
3 votes
Accepted

Is there a difference between the name scheduler and scheduling?

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 ...
user avatar
3 votes

Are there any papers published proving how University Time Table Scheduling Problem is NP-Complete?

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 ...
user avatar
  • 809
3 votes
Accepted

How and which component of an Operating System is responsible for the transition of a process from the blocked state to the ready queue?

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 ...
user avatar
3 votes

Interval Scheduling Problem with Three Resources

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 ...
user avatar
3 votes
Accepted

A specific version of a job scheduling problem

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 ...
user avatar
3 votes

Selling blocks of time slots

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. ...
user avatar
3 votes
Accepted

Disk scheduling algorithm - SCAN and C-SCAN

Here are the examples of various disk scheduling algorithms. Yes you are correct in both the case. The author here has made mistake. For SCAN: The answer should be 236. For C-SCAN: The answer should ...
user avatar
3 votes
Accepted

Does an algorithm exist for scheduling jobs on two processors?

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 ...
user avatar
  • 2,682
3 votes
Accepted

How does the problem of "Scheduling to Minimize Lateness" exhibit optimal substructure?

Let us refine the "definition" of the optimal substructure property given in CLRS into two definitions. A problem exhibits strongly optimal substructure if every optimal solution to the ...
user avatar
  • 34.7k
3 votes
Accepted

Response time of scheduling a DAG where each vertex is a task

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) ...
user avatar
  • 4,371
3 votes

DP for Weighted Interval Scheduling: why is sorting by finish time necessary?

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 ...
user avatar
3 votes
Accepted

Algorithm to enumerate all complete schedulings of finals tests?

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 ...
user avatar
  • 143k
3 votes
Accepted

Hardness of a scheduling/assignment problem

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. ...
user avatar
  • 12.4k
3 votes
Accepted

Order List of Sets so Adjacent Sets are Disjoint

You are asking two questions. I will only answer the first. What you are looking for is a Hamiltonian path in the Kneser graph $K(n,2)$. When $n = 5$, this is the Petersen graph, which contains a ...
user avatar
3 votes

Topological sort of minimum costs to finish interdependent tasks

This problem is basically to find the longest path in a directed acyclic graph (DAG). Let $cost[t]$ be the number of days it takes to do task $t$. Let $m[t]$ be the minimum number of days to finish ...
user avatar
  • 34.7k
3 votes
Accepted

Topological sort of minimum costs to finish interdependent tasks

I am assuming here that you are allowed to start tasks in parallel if there is no dependency between them, otherwise I think that no matter what order you do, the total time needed to finish the ...
user avatar
  • 1,475
2 votes

Arranging tasks with specific constraints (scheduling)

This is actually a bin packing problem, rather than a scheduling problem. If I remember correctly (it's been a long time) bin packing is the dual of scheduling. In the most basic kind of bin packing ...
user avatar
2 votes

Algorithm to solve job assignment problem

Instead of putting x, put some very high cost values in those cells. Then the Hungarian algorithm avoids selecting those cells automatically (if that's possible).
user avatar
  • 121
2 votes

What is the average turnaround time?

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 ...
user avatar
2 votes
Accepted

Can Shortest Job First Scheduling be subject to convoy effect?

I think you're not using the same terminology as the books and articles you're reading. Non-preemptive schedulers suffer from priority inversion, not convoy effects. Most scheduling disciplines (...
user avatar
2 votes
Accepted

How profiling is done in trace scheduling?

Yes, profiling is normally done by running the program. Yes, running the program and then gathering information about execution frequencies is how this is normally done. As Paul A. Clayton suggests, ...
user avatar
  • 143k

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