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?

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

1 Answer 1


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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.