(1) Warwick Business School, The University of Warwick, Coventry, CV4 7AL, UK;(2) DeGroote School of Business, McMaster University, Hamilton, Ontario, L8S 4M4, Canada
Abstract:
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.