A polynomial algorithm for a two-job shop scheduling problem with routing flexibility

A classical two-job shop problem deals with the determination of an optimal schedule of operations fixed by the technological process. In this paper, we address a generalization of such a problem by introducing the routing flexibility on the realization of jobs. The sequence a job follows in order to be performed is not fixed but must be computed from several alternatives. A polynomial algorithm, based on the geometric approach for the two-job shop problem, is developed for solving a particular case with two jobs. The algorithm applies for the minimization of any regular objective function.