The problem of two processors in series and n parts is considered, when processing times depend on some state variable. It is first shown that the minimum problem is NP-Hard in the strong sense. Then, four heuristic algorithms are described and compared in the linear dependance case.