An integrated approach for modeling and solving the general multiprocessor job-shop scheduling problem using tabu search
An integrated approach for modeling and solving the general multiprocessor job-shop scheduling problem using tabu search
复制标题
DOI：
10.1023/a:1018930406487
复制
发表时间：
1997-04
影响因子：
4.8
通讯作者：
S. Dauzére-Pérés;J. Paulli
中科院分区：
文献类型：
--
作者：
S. Dauzére-Pérés;J. Paulli
本文所考虑的问题是经典作业车间调度问题的一个重要扩展，其中相同的操作可以在多台机器上执行。问题是将每个操作分配给一台机器，并对机器上的操作进行排序，从而使一组作业的完工时间最小化。我们引入了析取图模型的扩展版本，该模型能够考虑到操作必须被分配给机器的事实。这使我们能够提出一种综合的方法，通过定义问题的邻域结构，其中没有重新分配或重新排序操作的区别。这个社区被证明是有联系的。提出了禁忌搜索算法，并给出了计算结果。
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.