# Is scheduling a set of tasks on single machine in P or in NP?

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?

• Ain't this question exactly the Traveling Salesman Problem?
– R B
Commented Sep 17, 2014 at 13:33

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.

• Thank you Marzio!
– Umar
Commented Jan 29, 2021 at 10:34