Mixed-Integer Optimization Problems with Applications to Manufacturing Scheduling and Distributed Energy System Operation

Over the past decades, mixed-integer optimization problems have attracted a lot attentions. Two popular topics are the scheduling problems of semiconductor manufacturing, and operation problems of distributed energy systems. On the one hand, the increasing pressure to meet demand is forcing semiconductor manufacturers to seek efficient scheduling methods. On the other hand, with world’s increasing energy demand and growing environmental concerns, efficient utilization of energy is essential. Lithography, with a limited number of expensive resources, is a major bottleneck in memory chip manufacturing. Because of its complex characteristics and large sizes of practical problems, developing effective scheduling approaches is challenging. In this thesis, a mixed-integer linear formulation is established for high-volume and low-variety manufacturing through novel resource-based modeling instead of traditional lot-based. To solve this problem efficiently by branch-and-cut, a two-phase approach is established based on convex hull analysis. The solution methodology for litho machine scheduling can also be used for other mixed-integer linear problems such as distributed energy system (DES) operation. Energy demands and energy supplied by different devices are characterized by different levels of quality, which is measured by exergy in thermodynamics. Exergy is destroyed in various processes, with limited amount of exergy in fossil fuels, it is therefore important to match demand and supply in quantity and quality to avoid exergy waste. Flexible DESs provide a desirable infrastructure. An exergy-based optimization approach is therefore developed for DES operation to reduce energy costs and the exergy losses by considering the whole energy supply chain from energy resources to user demands. To capture the complicated interactions among energy devices and capture the exergy loss of each energy device, exergy networks are established with detailed device and water network models. The mixed-integer problem is efficiently solved by our latest surrogate Lagrangian relaxation with branch-and-cut. With renewables, a similar DES operation problem is considered to minimize energy and emission costs. To overcome the difficulty caused by the intermittent nature of renewables, PV uncertainties are modeled by a Markovian process. For effective coordination, other devices are modeled as Markov processes with states depending on PV states. The entire problem is stochastic and Markovian, and solved by branch-and-cut. To take capital and maintenance costs into account in the long run, the design problem is also considered to decide device sizes with given types. To evaluate the lifetime cost including the reliability cost under different types of grid connection, a linear model is established. By selecting a limited number of possible device size combinations, exhaustive search is used to find the optimized design.