Scheduling Parts in a Combined Production-transportation Work Cell

This paper is concerned with a combined production-transportation scheduling problem. The problem comprises a simple, two-machine, automated manufacturing cell, which either stands alone or is a subunit of a complete flexible manufacturing system. The cell consists of two machines in series with a dedicated part-handling device such as a crane or robotic arm for transferring parts from the first machine to the second. The loading of a new piece on the first machine and the ejection of a finished piece from the second machine are performed by dedicated automated mechanisms. The introduction of parts into the system is done n at a time, whereby the parts are reshuffled into a sequence that minimizes completion time. All processing and transfer times are considered deterministic—a reasonable assumption for a cell comprising a robotic transfer device and two CNC machining units. What complicates the problem is the assumption of a non-negligible time for the transfer device to return (empty) from the second machine to the first. The operation is a generalization of a two-machine flowshop problem, and is formulated as a specially structured, asymmetric travelling salesman problem. An approximate polynomial time 0(n log n) algorithm is proffered. The procedure incorporates a lower bound using the Gilmore–Gomory algorithm for the no-wait, two-machine flowshop problem.     

Complex homogeneous splines on the torus

We construct functions M_α which are piecewise homogeneous polynomials on the (d+1)-dimensional torus U^d+1. These functions possess complete symmetry with respect to the independent variables. The symmetry and homogeneous relations for these functions are exploited to obtain a recurrence relation and explicit representations. Furthermore, we show that , where ω=e^12x/k, 0≤j_t≤k−1, are linearly independent. By restricting M_α to U^d, we obtain the complex analogue of polynomial box splines on a (d+1)-direction mesh on U^d, which is a multivariate analogue of B-splines on the circle studied by I.J. Schoenberg^[8].