A tabu search heuristic for solving the CLSP with backlogging and set-up carry-over

In this paper, the multi-item, single-level, capacitated, dynamic lot sizing problem with set-up carry-over and backlogging, abbreviated to CLSP⁺, is considered. The problem is formulated as a mixed integer programming problem. A heuristic method consisting of four elements: (1) a demand shifting rule, (2) lot size determination rules, (3) checking feasibility conditions and (4) set-up carry-over determination, provides us with an initial feasible solution. The resulting feasible solution is improved by adopting the corresponding set-up and set-up carry-over schedule and re-optimizing it by solving a minimum-cost network flow problem. Then the improved solution is used as a starting solution for a tabu search procedure, with the value of moves assessed using the same minimum-cost network problem. Computational results on randomly generated problems show that the algorithm, which is coded in C++, is able to provide optimal solutions or solutions extremely close to optimal. The computational efficiency makes it possible to solve reasonably large problem instances routinely on a personal computer.     

Two methods for semi-automated quantification of changes in ventricular volume and their use in schizophrenia

Two semi-automated methods for quantification of ventricular volume change from baseline and follow-up magnetic resonance imaging scans have been developed. Technique 1 employs direct segmentation of the ventricles from both the scans using thresholding and contour extraction. Technique 2 operates on difference images produced by voxel based intensity subtraction of the baseline from the registered follow-up images. Here, all voxels with intensities above a noise threshold and in a restricted area are monitored to compute volumetric changes. In phantom measurements the first technique was accurate to 0.0046%, the second to 0.167% of the phantom volume. Results from normal volunteers was that the average ventricular volume changed by 1.52% and 1.54% for images acquired within 9 months using techniques 1 and 2, respectively. With schizophrenic patients mean change of 10.78% and 9.43% were found employing the first and second procedures, respectively. All measurements agreed with a radiologist’s visual grading of the changes. Robust, objective, fast, easy-to-use, and fairly accurate procedures have been developed and validated to quantify volumetric changes.     

Stable in situ sorting and minimum data movement

In this paper, we describe an algorithm to stably sort an array ofn elements using only a linear number of data movements and constant extra space, albeit in quadratic time. It was not known previously whether such an algorithm existed. When the input contains only a constant number of distinct values, we present a sequence ofin situ stable sorting algorithms makingO(n lg^(k+1) n+kn) comparisons (lg^(K) means lg iteratedk times and lg* the number of times the logarithm must be taken to give a result 0) andO(kn) data movements for any fixed valuek, culminating in one that makesO(n lg*n) comparisons and data movements. Stable versions of quicksort follow from these algorithms.Research supported by Natural Sciences and Engineering Research Council of Canada grant No.A-8237 and the Information Technology Research Centre of Ontario.Supported in part by a Research Initiation Grant from the Virginia Engineering Foundation.