Chen, Jiayi. / Thesis (M.Phil.)--Chinese University of Hong Kong, 2009. / Includes bibliographical references (p. 86-94). / Abstract also in Chinese. / Abstract --- p.i / Acknowledgement --- p.iv / Introduction --- p.1 / Chapter 1.1 --- Introduction to the Capacitated Lot Sizing (CLS )problem --- p.1 / Chapter 1.2 --- Our contributions --- p.2 / Chapter 1.3 --- Organization of the thesis --- p.4 / Literature Review --- p.5 / Chapter 2.1 --- Research in CLS problem --- p.5 / Chapter 2.1.1 --- Reviews in CLS problems --- p.8 / Chapter 2.1.2 --- Approaches and methods to solve the traditional CLS problems --- p.9 / Chapter 2.1.3 --- Research on Fixed-Charge-Transportation-typed models for CLS problems --- p.13 / Chapter 2.2 --- Research in Genetic Algorithm (GA) --- p.15 / Chapter 2.3 --- Conclusion --- p.17 / Problem Description and Formulation --- p.18 / Chapter 3.1 --- The formulation --- p.18 / Chapter 3.2 --- Comparison with the traditional formulation --- p.24 / Chapter 3.3 --- Conclusion --- p.28 / Description of the Heuristic --- p.29 / Chapter 4.1 --- Initialization --- p.32 / Chapter 4.1.1 --- Setup string generation --- p.32 / Chapter 4.1.2 --- Transportation problem --- p.35 / Chapter 4.1.3 --- Consistency test --- p.47 / Chapter 4.2 --- Selection --- p.50 / Chapter 4.3 --- Crossover --- p.50 / Chapter 4.4 --- Mutation --- p.52 / Chapter 4.5 --- Evaluation --- p.53 / Chapter 4.6 --- Termination --- p.54 / Chapter 4.7 --- Conclusion --- p.54 / Design of Experiments and Computational Results --- p.56 / Chapter 5.1 --- Design of experiments --- p.57 / Chapter 5.2 --- Discussion of lower bound procedures --- p.63 / Chapter 5.3 --- Computational results --- p.65 / Chapter 5.3.1 --- CLS problems with setup times --- p.65 / Chapter 5.3.2 --- CLS problems without setup times --- p.77 / Chapter 5.4 --- Conclusion --- p.82 / Conclusion --- p.83 / Bibliography --- p.86

The integration of production and distribution decisions presents a challenging problem for manufacturers trying to optimize their supply chain. At the planning level, the immediate goal is to coordinate production, inventory, and delivery to meet customer demand so that the corresponding costs are minimized. Achieving this goal provides the foundations for streamlining the logistics network and for integrating other operational and financial components of the system. In this paper, a model is presented that includes a single production facility, a set of customers with time varying demand, a finite planning horizon, and a fleet of vehicles for making the deliveries. Demand can be satisfied from either inventory held at the customer sites or from daily product distribution. A procedure centering on a reactive tabu search is developed for solving the full problem. After a solution is found, path relinking is applied to improve the results. A novel feature of the methodology is the use of an allocation model in the form of a mixed integer program to find good feasible solutions that serve as starting points for the tabu search. Lower bounds on the optimum are obtained by solving a modified version of the allocation model. Computational testing on a set of 90 benchmark instances with up to 200 customers and 20 time periods demonstrates the effectiveness of the approach. In all cases, improvements ranging from 10 - 20% were realized when compared to those obtained from an existing greedy randomized adaptive search procedure (GRASP). This often came at a three- to five-fold increase in runtime, however. A hybrid scheme that combines the features of reactive tabu search algorithm and branch-and-price algorithm is also developed. The combined approach takes advantage of the efficiency of the tabu search heuristic and the precision of the branch-and-price algorithm. Branching strategy that is suitable for the problem is proposed. Several advance techniques such as column generation heuristic and rounding heuristic are also implemented to improve the efficiency of the algorithm. Computational testing on standard data sets shows that a hybrid algorithm can practically solve instances with up to 50 customers and 8 time periods which is not possible by standard branch-and-price algorithm alone. / text

published_or_final_version / Mathematics / Master / Master of Philosophy

No description available.

No description available.

No description available.

This dissertation is composed of three major parts, each studying a problem related to semiconductor manufacturing. The first part of the dissertation proposes a high-level scheduling model that serves as an intermediate stage between planning and detailed scheduling in the usual planning hierarchy. The high-level scheduling model explicitly controls the WIP over time in the system and provides a more specific guide to detailed scheduling. WIP control is used to balance the WIP (Work In Process) level and to keep the bottleneck station busy to maintain a high throughput rate. A mini-fab simulation model is used to evaluate the benefits of different approaches to implementing such a high-level scheduling model, and to compare different WIP control policies. Extensive numerical studies show that the proposed approaches can achieve much shorter cycle times than the traditional planning-scheduling approach, with only a small increase in inventory and backorder costs. With increasing worldwide competition, high technology product manufacturing companies have to pay great attention to lower their production costs and guarantee high quality at the same time. Advanced process control (APC) is widely used in semiconductor manufacturing to adjust machine parameters so as to achieve satisfactory product quality. The interaction between scheduling and APC motivates the second part of this dissertation. First, a single-machine makespan problem with APC constraints is proved to be NPcomplete. For some special cases, an optimal solution is obtained analytically. In more general cases, the structure of optimal solutions is explored. An efficient heuristic algorithm based on these structural results is proposed and compared to an integer programming approach. Another important issue in manufacturing system is maintenance, which affects cycle time and yield management. Although there is extensive literature regarding maintenance policies, the analysis in most papers is restricted to conventional preventive maintenance (PM) policies, i.e., calendar-based or jobbased PM policies. With the rapid development of new technology, predictive maintenance has become more feasible, and has attracted more and more attention from semiconductor manufacturing companies in recent years. Thus, the third problem considered in this dissertation is predictive maintenance in an M/G/1 queueing environment. One-recipe and two-recipe problems are studied through semi-Markov decision processes (SMDP), and structural properties are obtained. Discounted SMDP problems are solved by linear programming and expected machine availabilities are calculated to evaluate different PM policies. The optimal policy can maintain a high machine availability with low long-run cost. The structures of the optimal PM policies show that it is necessary to consider multiple recipes explicitly in predictive maintenance models. / text