FPTAS for the two identical parallel machine problem with a single operator under the free changing mode

We address in this paper the problem of scheduling a set of independent and non-preemptive jobs on two identical parallel machines with a single operator in order to minimize the makespan. The operator supervises the machines through a subset of a given set of modi operandi: the working modes. A working mode models the way the operator divides up his interventions between the machines. The processing times thus become variable as they now depend on the working mode being utilized. To build a schedule, we seek not only a partition of the jobs on the machines, but also a subset of working modes along with their duration. A pseudo-polynomial time algorithm is first exhibited, followed by a fully polynomial time approximation scheme (FPTAS) to generate an optimal solution within the free changing mode.