Skip to main content
Share Your Experience: Take the 2024 Developer Survey
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 ...
Wei Zhan's user avatar
  • 1,183
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 ...
John L.'s user avatar
  • 39k
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 ...
John L.'s user avatar
  • 39k
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) ...
ryan's user avatar
  • 4,511
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 ...
Mengfan Ma's user avatar
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 ...
Albjenow's user avatar
  • 176
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 ...
Parth Pandya's 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. ...
j_random_hacker's 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 ...
Wandering Logic's 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 ...
Amir Nasr's user avatar
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 ...
Tom van der Zanden's 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 ...
DCTLib's user avatar
  • 2,787
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.'s user avatar
  • 161k
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. ...
orlp's user avatar
  • 13.6k
3 votes

Maximum interval scheduling - Circular Variation

Yes. What we need to do is, basically, running the $O(n^2)$ algorithm provided in the question, but without unnecessary intervals and redundant steps. Here is the gist of an $O(n\log n)$ algorithm. ...
John L.'s user avatar
  • 39k
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 ...
Yuval Filmus's 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 ...
John L.'s user avatar
  • 39k
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 ...
Russel's user avatar
  • 2,745
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 ...
orangemonkey's user avatar
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 ...
Gilles 'SO- stop being evil''s user avatar
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" ...
Wandering Logic's user avatar
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 ...
GEL's user avatar
  • 829
2 votes

Minimum sum of distance from entrance gate

I will try to give a solution. Tell me if I am mistaking anywhere. First observation : When we have equal number of chairs and persons the solution is trivial.Ask all the people from 1st gate to fill ...
User Not Found's user avatar
2 votes
Accepted

What is the best Approximation algorithm to schedule a task graph?

You get a $2-\frac1m$-approximation (where $m$ is the number of machines), by greedily scheduling tasks as they become available, and this is essentially the best we can do at the moment. Improving ...
Thomas Bosman's user avatar
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 ...
Yuval Filmus's user avatar
2 votes

Work-stealing: where and how many to steal

I did some experiments about this myself a while back so I hope I can still give some insight. This approach is called "Idempotent Work Stealing" and was defined (to the best of my knowledge) here. It ...
gue's user avatar
  • 211
2 votes

What are some examples of problems whose deterministic versions are easy, but become hard when injecting some uncertainty?

Linear Quadratic Regulation is a standard control-theoretic problem that is easy when deterministic. The problem is to minimize a quadratic cost while steering a linear system: https://en.wikipedia....
tobwin's user avatar
  • 81
2 votes

Find a schedule with lowest total penalty

This problem is called "minimization of total weighted flow time". It is very hard, especially when jobs cannot be preempted by the processor. Even when jobs can be preempted, it is NP-hard, so you ...
Vincenzo's user avatar
  • 3,302
2 votes
Accepted

Existence of Real-Time Multiprocessor Schedule

Y. Cho and S. Sahni, Scheduling Independent tasks with due times on a uniform Processor System, Jr. of the ACM, 1980 Presents an algorithm to preemptively schedule n tasks(with due dates) on m ...
Nilesh Hirani's user avatar
2 votes

3-SAT reduction to jobs scheduling problem (np-completeness)

I see that you have posted this question before with no luck, and I think that this might be due to the amount of work needed to the answer such an open question. I looked at it also when you posted ...
AstridNeu's user avatar
  • 158

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