AbstractWe consider a scheduling problem where a set ofnjobs has to be processed on a set ofmmachines and arbitrary precedence constraints between operations are given. Moreover, for any two operationsiandjvaluesaij>0 andaji>0 may be given whereaijis the minimal difference between the starting times of operationsiandjwhen operationiis 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 problemJ//Cmaxbelong 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.