995.
We consider a scheduling problem where a set of
n jobs has to be processed on a set of
m machines and arbitrary precedence constraints between operations are given. Moreover, for any two operations
i and
j values
a ij >0 and
a ji >0 may be given where
a ij is the minimal difference between the starting times of operations
i and
j when operation
i is processed first. Often, the objective is to minimize the makespan but we consider also arbitrary regular criteria. Even the special cases of the classical job shop problem
J//Cmax belong to the set of NP-hard problems. Therefore, approximation or heuristic algorithms are necessary to handle large-dimension problems. Based on the mixed graph model we give a heuristic decomposition algorithm for such a problem, i.e. the initial problem is partitioned into subproblems that can be solved exactly or approximately with a small error bound. These subproblems are obtained by a relaxation of a subset of the set of undirected edges of the mixed graph. The subproblems are successively solved and a proportion of the results obtained for one subproblem is kept for further subproblem definitions. Numerical results of the algorithm presented here are given.
相似文献