# Tag Info

## Hot answers tagged scheduling

8

Mainly, there exist 3 benchmarks to test shop scheduling problems. Namely they are Taillard, Structured and ORLib benchmarks. These benchmarks have different goals. The Taillard benchmark is the most used benchmark in the literature. The benchmark targets permutation flowshop, flowshop, open shop and job shop scheduling problems. For details and download of ...

7

The problem is NP-hard for $L = A^*$ where $A$ is the finite language containing the following words: $x111$, $x000$, $y100$, $y010$, $y001$, $00c11$, $01c10$, $10c01$, and $11c00$ The reduction is from the problem Graph Orientation, which is known to be NP-hard (see https://link.springer.com/article/10.1007/s00454-017-9884-9). In this problem, we are ...

6

After a failed polynomial-time quick attempt, here it is an idea to prove that it is NP-complete using a reduction from 3SAT. Given a 3SAT formula with $x_1,...,x_n$ variables and $C_1,...,C_m$ clauses, first build a variable assignment gadget like in the figure below (thanks to @Jukka for the clarifications, the graph drawing style, and the hint for the ...

6

It could be useful to look at the list of participants of recent Dagstuhl seminars on scheduling http://www.dagstuhl.de/program/calendar/partlist/?semnr=13111 http://www.dagstuhl.de/program/calendar/partlist/?semnr=11091 http://www.dagstuhl.de/program/calendar/partlist/?semnr=10071 and then to look at the publications of each participant on DBLP. This ...

5

Kirk Pruhs, Cliff Stein, Kamesh Munagala, Nikhil Bansal, Sungjin Im, Ben Moseley.

5

This is the Vector Scheduling (VS) problem. Unless P = NP, VS admits no constant factor approximation algorithm when $d$ is part of the input: Chekuri, C., Khanna, S.: On multidimensional packing problems. SIAM J. Comput., 33(4):837-851, 2004. The same paper gives a polynomial-time approximation scheme when $d$ is not part of the input, and a polynomial ...

4

This is an instance of the standard network flow problem called "Project Selection", and hence can be solved efficiently (even in practice). See (what's currently) Section 24.6 of Jeff Erickson's lecture notes for a nice explanation. It's covered in most introductions to network flow in good undergraduate algorithms courses, so if you don't like Jeff E's ...

4

This is a possible reduction from 3-partition which is strongly NP-complete. Given a set $A = \{a_1,a_2,...,a_{3m}\}$ of $3m$ positibe integers, and a target sum $B$. The basic idea is simple: if we found a read sequence like $Rx1\; Rx2\; Rx1$, even if the last write of $x$ before the sequence was a $Wx2$, the first $Rx1$ forces to "use" another $Wx2$ to ...

3

This is a non-answer, but it might help to understand the question (assuming that I understood it correctly). Here is a simple but slightly non-trivial example: Here: input = black graph output = on which blue line we place each node = when to schedule each job costs = orange numbers = number of predecessors with different labels Left = simple greedy ...

2

Here's a paper that considers a more general variant of the problem (multiple machines, job dependent demands etc.): Rohit Khandekar, Baruch Schieber, Hadas Shachnai, Tami Tamir. Real-time scheduling to minimize machine busy times. Journal of Scheduling 18(6), 561-573, 2015. doi:10.1007/s10951-014-0411-z In particular, their results give a polynomial time ...

2

The precoloring extension problem is the following: Input: a number $k$ and a graph $G$ some of whose edges are labeled with labels in $\{1, 2, \ldots, k\}$. Decision: is it possible to color the edges of $G$ with colors $1, 2, \ldots, k$ such that no adjacent edges share a color and such that each initially labeled edge is colored with the color it is ...

2

@MikhailRudoy was the first to show NP-hardness, but Louis and I had a different idea, which I thought I could outline here since it works somewhat differently. We reduce directly from CNF-SAT, the Boolean satisfiability problem for CNFs. In exchange for this, the regular language $L$ that we use is more complicated. The key to show hardness is to design a ...

1

Here is an elaboration of my comment. From what I can understand, the OPs problem can be cast as the solution of a large implicit linear program. Given the $n$ numbers $d_1,d_2,\ldots,d_n$ let $\mathcal{S}$ denote the set of subsets of $[n]$ such that $S \in \mathcal{S}$ iff $\sum_{i \in S} d_i \le s$. These are the feasible customer sets at any given time. ...

1

Not my field of expertise, but I think this is a relaxation in comparison with real-life scenarios. In actual systems, once a connection has been established and a "packet" has been sent (what packet here means depends on the context of the problem being solved), it is possible that an unscheduled interrupt occurs that pauses this communication and allows a ...

1

I found a reduction from the Partition Problem to a modified version of the proposed problem. Partition Problem (Optimization) input: set of integers S output: partition of S into S1 and S1 such that the difference of the sums of S1 and S2 is minimized: $$\lvert\sum_{s\in S1}s - \sum_{s\in S2}s\lvert.$$ This problem is NP-hard. Level Assignment Problem (...

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