A Heuristic Decomposition Algorithm for Scheduling Problems on Mixed Graphs

Abstract

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//C_max 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.

Keywords:

• networks and graphs
• scheduling
• decomposition