Jobshop problem with two operations per job unit processing times total completion time
We have m machines and n jobs. Each job is made of 2 operations with unit processing time. An operation is assigned to a fixed machine. For the makespan critria the problem is known to be solvable in polynomial time. It's open for total completion time (when m is fixed there is an obvious dynamic program).