As the technology scales, there is a need to develop design and optimization algorithms under various scenarios of uncertainties. These uncertainties are introduced by process variation and impact both delay and leakage. For future technologies at the end of CMOS scaling, not only process variation but the device defect density is projected to be very high. Thus realizing error tolerant implementation of Boolean functions with minimal redundancy overhead remains a challenging task. The dissertation is concerned with the challenges of low-power and area digital circuit design under high parametric variability and high defect density. The technology mapping provides an ideal starting point for leakage reduction because of higher structural freedom in the choices of implementations. We first describe an algorithm for technology mapping for yield enhancement that explicitly takes parameter variability into account. We then show how leakage can be reduced by accounting for its dependence on the signal state, and develop a fast gain-based technology mapping algorithm. In some scenarios the state probabilities can not be precise point values but are modeled as an interval. We extended the notion of mean leakage to the worst case mean leakage which is defined as the sum of maximal mean leakage of circuit gates over the feasible probability realizations. The gain-based algorithm has been generalized to optimize this proxy leakage metric by casting the problem within the framework of robust dynamic programming. The testing is performed by selecting various instance probabilities for the primary inputs that are deviations from the point probabilities with respect to which a point probability based gain based mapper has been run. We obtain leakage improvement for certain test probabilities with the interval probability based over the point probability based mapper. Next, we present techniques based on coding theory for implementing Boolean functions in highly defective fabrics that allow us to tolerate errors to a certain degree. The novelty of this work is that the structure of Boolean functions is exploited to minimize the redundancy overhead. Finally we have proposed an efficient analysis approach for statistical timing, which can correctly propagate the slope in the path-based statistical timing analysis. The proposed algorithm can be scaled up to one million paths.

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