This paper considers 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 aij>0 and aji>0 may be given where aij 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 the paper considers also arbitrary regular criteria. Even the special cases of the classical job shop problem j&z.urule;&z.urule;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, the paper gives 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.
