ISSN:
1572-9338
Keywords:
Analysis of algorithms
;
suboptimal algorithms: tabu search
;
production/scheduling
;
sequencing
;
deterministic
;
multiple machine
;
multiprocessor
;
job-shop scheduling
;
disjunctive graph model
Source:
Springer Online Journal Archives 1860-2000
Topics:
Mathematics
,
Economics
Notes:
Abstract 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.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1023/A:1018930406487
Permalink
