Robotic-cell scheduling: Special polynomially solvable cases of the traveling salesman problem on permuted Monge matrices
UNSPECIFIED. (2005) Robotic-cell scheduling: Special polynomially solvable cases of the traveling salesman problem on permuted Monge matrices. JOURNAL OF COMBINATORIAL OPTIMIZATION, 9 (4). pp. 381-399. ISSN 1382-6905Full text not available from this repository.
In this paper, we introduce the 1 - K robotic-cell scheduling problem, whose solution can be reduced to solving a TSP on specially structured permuted Monge matrices, we call b-decomposable matrices. We also review a number of other scheduling problems which all reduce to solving TSP-s on permuted Monge matrices. We present the important insight that the TSP on b-decomposable matrices can be solved in polynomial time by a special adaptation of the well-known subtour-patching technique. We discuss efficient implementations of this algorithm on newly defined subclasses of permuted Monge matrices.
|Item Type:||Journal Article|
|Subjects:||Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software
Q Science > QA Mathematics
|Journal or Publication Title:||JOURNAL OF COMBINATORIAL OPTIMIZATION|
|Number of Pages:||19|
|Page Range:||pp. 381-399|
Actions (login required)