10

Indeed, it can be solved in polynomial time. This is a result by Frank (1985).


7

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

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


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


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


5

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


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

Reduce Garey & Johnson problem [SS8], Multiprocessor Scheduling, to your problem. This is NP-complete, even if $m=2$. In this problem there are no overlaps, and a deadline is specified. Your problem is therefore NP-hard, even in the case of zero overlaps. If you require non-zero overlaps, then it is still possible to reduce Multiprocessor Scheduling ...


4

If I understand your problem correctly, it seems like you're looking to examine a furthest-point weighted Voronoi diagram under the Manhattan ($\ell_1$) distance. The transformation is as follows. For each point $p_i$ on the grid, define the distance function $$d_i(x) = \max(0, \|x - p_i\|_1 - (t_{n+1}-t_i))$$ Then $d_i(x)$ is the (truncated) distance of $...


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


3

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

Even without the additional constraints you have the unrelated machine scheduling problem with precedence constraints is not well understood. If I am not mistaken nothing better than a polynomial factor approximation is known. It is an important open problem in approximation algorithms for scheduling problems. Some positive results are known when the ...


2

Have you tried to look for what already existed in the field of Scheduling with Communication Cost? If you choose some of the communication cost to be $+\infty$, then it seems to me that it is exactly your problem. A communication cost is defined on an edge between two tasks $T$, $T'$ as: $$ \text{comm}(T,T')= \left \{ \begin{array}{ll} 0 &...


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


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


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