<p>I don't know if there is a canonical description (scheduling notation: $1|?|?$) for it; but it seems that there is a quick reduction from Hamiltonian s-t path problem on a directed graph.</p>

<p>Given a digraph $G= (V,E), |V| = n$ and the two vertices $s,t$; build a scheduling task with $n+2$ tasks $T_A,T_1,...,T_n,T_B$ in which $T_1,...,T_n$ correspond to the nodes of $V$ (two of them: $T_s, T_t$ correspond to $s,t$); set $d = n+2$ and set execution times:</p>

<ul>
<li>$e(T_A,T_{s})$ = 1</li>
<li>$e(T_{t},T_B)$ = 1</li>
<li>$e(T_{i},T_j)$ = 1 if the directed edge $(u_i,u_j) \in E$</li>
</ul>

<p>For all the other pairs, set $e(T_i, T_j) = d+1$</p>

<p>The $n+2$ tasks can be scheduled before deadline $d$ if and only if the original graph has an Hamiltonian path from $s$ to $t$</p>

<p>So your problem is NP-complete.</p>

CC BY-SA 4.0
2021-01-29T10:34:15.023Z
Thank you Marzio!
Umar
CC BY-SA 3.0
2014-09-17T13:32:57.240Z
2014-09-17T13:32:57.240Z
Marzio De Biasi
<p>Given a set of tasks $T=\{t_1,\dots,t_n\}$ and execution times between the tasks $e(t_i,t_j)$ can we find a schedule $s$ for $T$ on a single machine with makespan $m_s &lt; d$? Assume that the execution times, $d$ and $m_s$ are arbitrary non-negative integers. The execution time of a task $t_j$ depends on the task the that was executed immediately before i.e. $t_i$ . Thus execution times play crucial role in determining the shortest schedule. </p>

<p>Do you any similar problem which is in P or NP?</p>

CC BY-SA 3.0
2014-09-17T13:33:57.240Z
Ain't this question exactly the Traveling Salesman Problem?
R B
<cc.complexity-theory>
Is scheduling a set of tasks on single machine in P or in NP?
Umar
# Is scheduling a set of tasks on single machine in P or in NP?

(Asked by: username_0 on 2014-09-17)

Given a set of tasks $T=\{t\_1,\dots,t\_n\}$ and execution times between the tasks $e(t\_i,t\_j)$ can we find a schedule $s$ for $T$ on a single machine with makespan $m\_s < d$? Assume that the execution times, $d$ and $m\_s$ are arbitrary non-negative integers. The execution time of a task $t\_j$ depends on the task the that was executed immediately before i.e. $t\_i$ . Thus execution times play crucial role in determining the shortest schedule.

Do you any similar problem which is in P or NP?

**Tags:** cc.complexity-theory

> **Comments:**
> **username_1**: Ain't this question exactly the Traveling Salesman Problem?  

---

## 1 answers

### Answer by username_2 on 2014-09-17. Score: 1 | Accepted answer

I don't know if there is a canonical description (scheduling notation: $1|?|?$) for it; but it seems that there is a quick reduction from Hamiltonian s-t path problem on a directed graph.

Given a digraph $G= (V,E), |V| = n$ and the two vertices $s,t$; build a scheduling task with $n+2$ tasks $T\_A,T\_1,...,T\_n,T\_B$ in which $T\_1,...,T\_n$ correspond to the nodes of $V$ (two of them: $T\_s, T\_t$ correspond to $s,t$); set $d = n+2$ and set execution times:

* $e(T\_A,T\_{s})$ = 1
* $e(T\_{t},T\_B)$ = 1
* $e(T\_{i},T\_j)$ = 1 if the directed edge $(u\_i,u\_j) \in E$

For all the other pairs, set $e(T\_i, T\_j) = d+1$

The $n+2$ tasks can be scheduled before deadline $d$ if and only if the original graph has an Hamiltonian path from $s$ to $t$

So your problem is NP-complete.

> **Comments:**
> **username_0**: Thank you Marzio!  

---

