We consider a job‐shop scheduling problem with n jobs and the constraint that at most p
<n jobs can be processed simultaneously. This model arises in several manufacturing processes, where each operation has to be assisted by one human operator and there are p (versatile) operators. The problem is binary NP‐hard even with n=3 and p=2. When the number of jobs is fixed, we give a pseudopolynomial dynamic programming algorithm and a fully polynomial time approximation scheme (FPTAS). We also propose an enumeration scheme based on a generalized disjunctive graph, and a dynamic programming‐based heuristic algorithm. The results of an extensive computational study for the case with n=3 and p=2 are presented.
