A classical two-job shop problem deals with the determination of an optimal schedule of two jobs on m machines. Each job has a linear sequence 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 follow 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.
展开▼