The research work presented in this dissertation relates to lot sizing and its applications in the areas of operational planning and shop floor scheduling and control. Lot sizing enables a proper loading of requisite number of jobs on the machines in order to optimize the performance of an underlying production system. We address lot sizing problems that are encountered at the order entry level as well as those that are faced at the time of distributing the jobs from one machine to another and those that arise before shipping the jobs (orders) to customers. There are different issues and performance measures involved during each of these scenarios, which make the lot sizing problems encountered in these scenarios different from one another. We present algorithms and relevant theoretical analyses for each of the lot sizing problems considered, and also, present results of numerical experimentation to depict their effectiveness
We first study the lot sizing problem encountered while transferring jobs from one machine to another. A lot of the jobs is to be split into smaller lots (called sublots) such that the lot is processed on multiple machines in an overlapping manner, a process which is known in the literature as lot streaming. Two lot streaming problems, FL2/n/C and FLm/1/C, are investigated in Chapter 2.
FL2/n/C involves a two-machine flow shop in which multiple lots are to be processed. The objective is to minimize the combined cost of makespan and material handling (the latter is proportional to the number of sublots). A dynamic programming-based methodology is developed to determine the optimal sublot sizes and the number of sublots for each lot while assuming a known sequence in which to process the lots. We designate this problem as LSP-DP. This methodology is, then, extended to determine an optimal sequence in which to process the lots in conjunction with the number of sublots and sublot sizes for each lot. We designate this problem as LSSP-DP. Three multidimensional heuristic search procedures (denoted as LSSP-Greedy, LSSP-Cyclic and LSSP-ZP) are proposed for this problem in order to obtain good-quality solutions in a reasonable amount of computational time. Our experimentation reveals that both lot streaming and lot sequencing generate significant benefits, if used alone. However, for the objective of minimizing total handling and makespan cost, lot streaming is more beneficial than lot sequencing. The combined use of lot streaming and sequencing, expectedly, results in the largest improvement over an initial random solution. LSP-DP is found to be very efficient, and so are the three LSSP heuristics, all of which are able to generate near-optimal solutions. On the average, LSSP-Greedy generates the best solutions among the three, and LSSP-Cyclic requires the least time.
FLm/1/C deals with the streaming of a single lot over multiple machines in a flow shop. The objective is a unified cost function that comprises of contributions due to makespan, mean flow time, work-in-process, transfer time and setup time. The distinctive features of our problem pertain to the inclusion of sublot-attached setup time and the fact that idling among the sublots of a lot is permitted. A solution procedure that relies on an approximation equation to determine sublot size is developed for this problem for equal-size sublots. The approximation avoids the need for numerical computations, and enables the procedure to run in polynomial time. Our experimentation shows that this solution procedure performs quite well and frequently generates the optimal solution. Since the objective function involves multiple criteria, we further study the marginal cost ratios of various pairs of the criteria, and propose cost sensitivity indices to help in estimating the impact of marginal cost values on the number of sublots obtained.
The lot sizing problem addressed in Chapter 3 is motivated by a real-life setting associated with semiconductor manufacturing. We first investigate the integration of lot sizing (at the operational planning level) and dispatching (at the scheduling and control level) in this environment. Such an integration is achieved by forming a closed-loop control system between lot sizing and dispatching. It works as follows: lot sizing module determines lot sizes (loading quota) for each processing buffer based on the current buffer status via a detailed linear programming model. The loading quotas are then used by the dispatching module as a general guideline for dispatching lots on the shop floor. A dispatching rule called "largest-remaining-quota-first" (LRQ) is designed to drive the buffer status to its desired level as prescribed by the lot sizing module. Once the buffer status is changed or a certain amount of time has passed, loading quotas are updated by the lot sizing module. Our experimentation, using the simulation of a real-life wafer fab, reveals that the proposed approach outperforms the existing practice (which is based on "first-in-first-out" (FIFO) model and an ad-hoc lot sizing method). Significant improvements are obtained in both mean values and standard deviations of the performance metrics, which include finished-goods inventory, backlog, throughput and work-in-process.
The integration of lot sizing and dispatching focuses on the design of an overall production system architecture. Another lot sizing problem that we present in Chapter 3 deals with input control (or workload control) that complements this architecture. Input control policies are responsible for feeding the production system with the right amount of work and at the right time, and are usually divided into "push" or "pull" categories. We develop a two-phase input control methodology to improve system throughput and the average cycle time of the lots. In phase 1, appropriate operational lot sizes are determined with regard to weekly demand, so as to keep the lot start rate at the desired level. In phase 2, a "pull" policy, termed CONLOAD, is applied to keep the bottleneck's workload at a target level by releasing new lots into the system whenever the workload level is below the desired level. Since the operators are found to be the bottleneck of the system in our preliminary investigation, the "operator workload" is used as system workload in this study. Using throughput and cycle time as the performance metrics, it is shown that this two-phase CONLOAD methodology achieves significant improvement over the existing CONWIP-like policy. Furthermore, a reference table for the target operator workload is established with varying weekly demand and lot start rate.
The last lot sizing problem that we address has to do with the integration of production and shipping operations of a make-to-order manufacturer. The objective is to minimize the total cost of shipping and inventory (from manufacturer's perspective) as well as the cost of earliness and tardiness of an order (from customer's perspective). An integer programming (IP) model is developed that captures the key features of this problem, including production and delivery lead times, multiple distinct capacitated machines and arbitrary processing route, among others. By utilizing the generalized upper bound (GUB) structure of this IP model, we are able to generate a simplified first-level RLT (Reformulation Linearization Technique) relaxation that guarantees the integrity of one set of GUB variables when it is solved as a linear programming (LP) problem. This allows us to obtain a tighter lower bound at a node of a branch-and-bound procedure. The GUB-based RLT relaxation is complemented by a GUB identification procedure to identify the set of GUB variables that, once restricted to integer values, would result in the largest increment in the objective value. The tightening procedure described above leads to the development of a RLT-based branch-and-bound algorithm. Our experimentation shows that this algorithm is able to search the branch-and-bound tree more efficiently, and hence, generates better solutions in a given amount of time. / Ph. D.
| Identifer | oai:union.ndltd.org:VTETD/oai:vtechworks.lib.vt.edu:10919/29435 |
| Date | 07 December 2007 |
| Creators | Chen, Ming |
| Contributors | Industrial and Systems Engineering, Sarin, Subhash C., Merzifonluoglu, Yaesmin, Ellis, Kimberly P., Lu, Guo-Quan |
| Publisher | Virginia Tech |
| Source Sets | Virginia Tech Theses and Dissertation |
| Detected Language | English |
| Type | Dissertation |
| Format | application/pdf |
| Rights | In Copyright, http://rightsstatements.org/vocab/InC/1.0/ |
| Relation | Ming_Chen_Dissertation_12_06_07.pdf |
Page generated in 0.003 seconds