Feasible job insertions in the multi-processor-task job shop

The Multi-Processor-Task Job Shop is an extension of the Job Shop problem where an operation of a job requires a set of machines instead of a single machine. Job insertion is the following: given a feasible schedule of n − 1 jobs, find a feasible insertion of job n into the schedule such that makespan is minimized. The problem is known to be NP-hard already for the Job Shop case. In this note, a polyhedral description of all feasible insertions is derived, settling an open problem recently proposed by Kis and Hertz. Constrained feasible insertions, satisfying additional constraints, are introduced and a feasibility theorem is established. A lower bound on the job insertion problem is derived and computed by repeatedly invoking the feasibility theorem. Numerical results show high quality of the bounds and short computation times.