Automated storage and Retrieval (AS/R) systems have had a significant impact on storage and retrieval of finished goods, work-in-process, and raw materials and supplies. A microcomputer-based simulation model was developed to evaluate different unit load AS/R systems serving multiple input sources and output destinations. The simulation results were statistically analyzed on different performance measures including throughput, mean waiting times maximum waiting times and rejects. The results showed that for single-dock, square-in-time layouts, the class based arrangement produced significantly higher throughput for all scheduling policies. Among the scheduling policies, the relief nearest neighbor produced consistently higher throughput. Comparing square-in-time versus non-square-in-time layouts, the square-in-time layout performance was better; the performance deteriorated as deviations from square-in-time increased. For the two dual-dock layouts, at lower arrival rates the dedicated layout produced higher throughput; there was no significant difference between the two layouts at higher arrival rates. / Graduation date: 1992

Many systematic methods exist for mapping algorithms to processor arrays. The algorithm is usually specified as a set of recurrence equations, and the processor arrays are synthesized by finding timing and allocation functions which transform index points in the recurrences into points in a space-time domain. The problem of scheduling (i.e. finding the timing function) of recurrence equations has been studied by a number of researchers. Of particular interest here are Systems of Affine Recurrence Equations (SAREs). The existing methods are limited to affine (or linear) schedules over the entire domain of computation. For some algorithms, there are points in the computation domain where the dependencies point in opposite directions, and an affine schedule does not exist, although a valid Piecewise Affine Schedule (PAS) can exist. The objective of this thesis is to examine these schedules and obtain a systematic method for deriving such schedules for SAREs. PAS can be found by first partitioning the computation domain and then obtaining a new SARE by renaming the variables. By partitioning the computation domain, we can obtain additional parallelism from the dependency graph, and find faster schedules over subspaces of the domain. In this paper, we describe a procedure for partitioning the domain and to generate a new SARE by renaming the variables. Some heuristics are introduced for partitioning the domain based on the properties of dependence vectors. After the partitioning and renaming, an existing method (due to Mauras et al.) is applied to find the schedules. Examples of Toeplitz System and Algebraic Path Problem are used to illustrate the results. / Graduation date: 1992

The objective of this research project was to identify the limitations associated with schedule-based Material Requirements Planning (SBMRP) and to present a knowledge-based expert system (KBES) approach to solve these problems. In SBMRP, the basic strategy is to use backward or forward scheduling based on an arbitrary dispatching rule, such as First-In First-Out. One of the SBMRP weak points is that it does not use such job information as slack times, due dates, and processing times, information which otherwise is important to good scheduling decisions. In addition, the backward scheduling method produces a better schedule than the forward scheduling method in terms of holding and late costs. Dependent upon job characteristics, this may or may not be true and should be tested. This study focused on the means to overcome these two weak points by the use of a KBES. Heuristic rules were developed through an experiment-based knowledge acquisition process to generate better schedules, rather than relying solely upon forward or backward scheduling. Scheduling performance was measured, based on the minimization of the sums of holding and late costs. Due to complexities of the problem, heuristic methods were used rather than analytic methods. In particular, five loading rules were selected, based upon their close relationship to selected job characteristics, including processing times and due dates. Combined loading methods (CLMs) were developed to obtain better performance, derived by combining the two existing SBMRP scheduling strategies with five loading heuristic rules. This resulted in the generation of 10 CLMs for further evaluation. Since this study proposed a new approach, an expert human scheduler was not available. To overcome this problem, knowledge acqusition through computer experimentation (KACE) was utilized, based upon an architecture of five components: job generator, scheduler, evaluator, rule generator (an extended version of ID3), and the KBES. The first three components were used to generate a large number of examples required by the rule generator to derive knowledge. This derived knowledge was incorporated into the KBES. Experimental results indicated that the KBES outperformed the two existing SBMRP methods. Based on sensitivity analysis, the KBES exhibited robust performance with regard to every job parameter except number of parts. As the number of parts was increased, KBES performance was subject to degradation since the possibility of interactions or conflicts between parts tended to increase, resulting in shifting the threshold ratio of total available time to total processing time. Thus, it is strongly recommended that a new KBES capable of accommodating 30 parts or more should be developed using the KACE method. / Graduation date: 1991

Branch-price-and-cut algorithms are among the most successful exact optimization approaches for solving many routing and scheduling problems. This is due, in part, to the availability of extremely efficient and effective dynamic programming algorithms for solving the pricing problem, and the availability of efficient and effective branching schemes and cutting planes that drive integrality. In terms of branch-price-and-cut, two obstacles we face today are (1) being able to solve harder and larger pricing problems, and (2) solving mixed-integer column generation formulations that suffer from relatively weak LP bounds compared to the more traditional 0-1 set partitioning type. As part of the work presented in this thesis, we encounter column generation formulations motivated by real life problems that require overcoming both types of challenges. The first part of this thesis is dedicated to solving the resource constrained shortest path problem (RCSPP) arising in column generation pricing problems for formulations involving extremely large networks and a huge number of local resource constraints. We present a relaxation-based dynamic programming algorithm that alternates between a forward and a backward search. Each search employs bounds derived in the previous search to prune the search, and between consecutive searches, the relaxation is tightened over a set of critical resources and arcs. The second part of this thesis focuses in the fixed charge shortest path problem (FCSPP) in which the amount of resource consumed is itself a continuous bounded variable. By exploiting the structure of optimal solutions to FCSPP, we design and implement a solution approach that relies on solving multiple RCSPPs, and therefore can again make use of extremely efficient and effective dynamic programming algorithms. In the third and final part of this thesis, we present a branch-price-and-cut algorithm for the inventory routing problem (IRP). We extend a class of cuts known for the vehicle routing problem, and develop a new class of cuts specifically for IRP to tighten the formulation. Both the branching schemes and cuts preserve the structure of the pricing problem making them efficiently implementable within a branch-price-and-cut algorithm.

Motivated by operational issues in real-world glass manufacturing, this thesis addresses a problem of laying out and sequencing the orders so as to minimize wasted glass, called scrap. This optimization problem combines aspects of traditional cutting problems and traditional scheduling and sequencing problems. In so far as we know, the combination of cutting and scheduling has not been modeled, or solved. We propose a two-phase approach: snap construction and constructing cutting and offload schedules. Regarding the second phase problem, we introduce FGSP (float glass scheduling problem), and provide its solution structure, called coveys. We analyze simple sub-models of FGSP considering the main elements: time, unit, and width. For each model, we provide either a polynomial time algorithm or a proof of NP-completeness. Since FGSP is NP-complete, we propose a heuristic algorithm, Longest Unit First (LUF), and analyze the worst case performance of the algorithm in terms of the quality of solutions; the worst case performance bound is {1+(m-1)/m}+{1/3-1/(3m)} where m is the number of machines. It is 5/3 when m=2. For the real-world problem, we propose two different methods for snap construction, and we apply two main approaches to solve cutting and offloading schedules: an MIP approach and a heuristic approach. Our solution approach produces manufacturing yields greater than 99%; current practice is about 95%. This is a significant improvement and these high-yield solutions can save millions of dollars.

Thesis (Ph. D.)--Mississippi State University. Department of Industrial Engineering. / Title from title screen. Includes bibliographical references.

Thesis (M.S.)--University of North Carolina at Wilmington, 2003. / Includes bibliographical references (leaf : [38]).

Thesis (M. Phil.)--Hong Kong University of Science and Technology, 2003. / Includes bibliographical references (leaves 40-42). Also available in electronic version. Access restricted to campus users.

Thesis PlanB (M.S.)--University of Wisconsin--Stout, 2009. / Includes bibliographical references.

published_or_final_version / Civil Engineering / Doctoral / Doctor of Philosophy