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 ...
- 1,173
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 \...
- 302
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 ...
- 618
4
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 ...
- 38.6k
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 ...
- 38.6k
4
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) ...
- 4,431
4
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 ...
- 642
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 ...
- 176
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.
...
- 5,459
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 ...
- 146
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 ...
- 17.7k
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 ...
- 76
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 ...
- 829
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 ...
- 751
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 ...
- 13.2k
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 ...
- 2,732
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 ...
D.W.♦
- 156k
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. ...
- 12.7k
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 ...
- 275k
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 ...
- 38.6k
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 ...
- 2,610
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).
- 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 ...
- 21
2
votes
Schedule tasks from a weighted list with time frame constraints
I'd be inclined to punt the problem to an integer linear programming problem solver. (Note that many solvers will take a timeout argument that'll return the best solution they've found so far if/when ...
- 1,404
2
votes
Accepted
Distributed parallel computing algorithms for content dependent data
You have a static number of tasks to be executed, and each task is independent (i.e., no communication among tasks is required). However, the chunks assigned to different machines might take a ...
- 4,132
2
votes
Accepted
Who was the first to define Flow Shop / Job Shop problem?
Coffman and Demming's famous Operating Systems Theory, 1973, section on Job Shop and Flow Shop problems (pp. 123-128) cites Conway, Maxwell, and Miller, 1967 as "a comprehensive treatment" ...
- 17.7k
2
votes
Scheduling N variable-time interdependent tasks across M workers
This can been seen as a variation of the job shop problem where you want to find the policy that yields the minimum makespan (time taken for all machines to process all jobs); as well as a variation ...
- 829
2
votes
How to choose waiting process in a preemptive priority-based scheduler
“Preemptive priority” is a property of a scheduler, it is not a complete specification. Under preemptive priority scheduling, you choose the waiting process that has the highest priority. If there are ...
2
votes
Accepted
How to understand the mathematical constraint of potentials?
I suspect there's some misunderstanding about the definition/meaning of $a_{ij}$. The time to complete task $i$ depends only on $i$ (not on $j$), so it wouldn't make sense to use notation like $a_{ij}...
D.W.♦
- 156k
2
votes
Accepted
Lower bound on competitive ratio of $m$-machine scheduling
Consider first the sequence $m \times 1$. If the algorithm schedules all the 1's in different machines, then its competitive ratio is 1. Otherwise, its competitive ratio is at least 2 (since the ...
- 275k
Only top scored, non community-wiki answers of a minimum length are eligible