A Heuristic Decomposition Algorithm for Scheduling Problems on Mixed Graphs |
| |
Authors: | Karin Krüger Natalia V Shakhlevich Yuri N Sotskov Frank Werner |
| |
Institution: | 1.Otto-von-Guericke-Universit?t,Germany;2.Institute of Engineering Cybernetics of the Byelorussian Academy of Sciences,Belarus |
| |
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//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. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|