An integrated approach for modeling and solving the general multiprocessor job-shop scheduling problem using tabu search

The problem considered in this paper is an important extension of the classical job-shop scheduling problem, where the same operation can be performed on more than one machine. The problem is to assign each operation to a machine and to sequence the operations on the machines, such that the makespan of a set of jobs is minimized. We introduce an extended version of the disjunctive graph model, that is able to take into account the fact that operations have to be assigned to machines. This allows us to present an integrated approach, by defining a neighborhood structure for the problem where there is no distinction between reassigning or resequencing an operation. This neighborhood is proved to be connected. A tabu search procedure is proposed and computational results are provided.