# Tag Info

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

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

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

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

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