Dissertação (Mestrado em Engenharia Mecânica) - Centro Universitário da FEI, São Bernardo do Campo, 2014

The research work presented in this dissertation relates to lot streaming in two-stage flow shops and assembly shops. Lot streaming refers to the process of splitting a production lot into sublots, and then, processing the sublots on different machines simultaneously in an overlapping manner. Such a strategy allows finished material at each stage to be transferred downstream sooner than if production and transfer batches were restricted to be the same size. In the case when each sublot consists of just one item, a single-piece-flow is obtained. Such a continuous flow is a key element of the Toyota Production System. However, single-piece-flow increases the number of transfers and the total transportation cost (time). As a result, it may not be economically justifiable in many cases, and therefore, material may have to be transferred in batches (called transfer batches, or sublots). Lot streaming addresses the problems of determining optimal sublot sizes for use in various machine environments and optimizes different performance measures.Given this relationship between lot streaming and the Toyota Production System, lot streaming can be considered a generalization of lean principles. In this dissertation, we first provide a comprehensive review of the existing literature related to lot streaming. We show that two-stage flow shop problems have been studied more frequently than other machine environments. In particular, single-lot two-machine flow shops have been very well researched and efficient solution techniques have been discovered for a large variety of problems. While two-stage flow shop lot streaming problems have been studied extensively, we find that the existing literature assumes that production rates at each stage remain constant. Such an assumption is not valid when processing rates change, for example, due to learning. Learning here, refers to the improvements in processing rates achieved due to experience gained from processing units. We consider the case when the phenomenon of learning affects processing and setup times in a two-stage flow shop processing a single lot, and when, sublot-attached setup times exist. The decrease in unit-processing time, or sublot-attached setup time, is given by Wright's learning curve. We find closed-form expressions or simple search techniques to obtain optimal sublot sizes that minimize the makespan when the effect of learning reduces processing times, sublot-attached setup times, or, both. Then, we provide a general method to transform a large family of scheduling problems related to lot streaming in the presence of learning, to their equivalent counterparts that are not influenced by learning. This transformation is valid for all integrable learning functions (including the Wright's learning curve). As a result, a large variety of new problems involving learning can be solved using existing solution techniques. We then consider lot streaming in stochastic environments in the context of sourcing material. Such problems have been well studied in the literature related to lot streaming for cost-based objective functions when demand is continuous, and when processing times are deterministic, or, for material sourcing problems when the time required to procure a lot is stochastic but is independent of the lot size. We extend this study to the case when the time required to produce a given quantity of products is stochastic and dependent on the number of units produced. We consider the case when two sublots are used, and also compare the performance of lot streaming to the case when each sublot is sourced from an independent supplier. Next, we address a new problem related to lot streaming in a two-stage assembly shop, where we minimize a weighted sum of material handling costs and makespan. We consider the case when several suppliers provide material to a single manufacturer, who then assembles units from different suppliers into a single item. We assume deterministic, but not necessarily constant, lead times for each supplier, who may use lot streaming to provide material to the manufacturer. Lead times are defined as the length of the time interval between a supplier beginning to process material and the time when the first sublot is delivered to the manufacturer; Subsequent sublots must be transported early enough so that the manufacturer is not starved of material. The supplier may reduce this lead time by using lot streaming, but at an increased material handling cost. The decrease in lead time is also affected by other factors such as lot attached/detached setup times, transportation times etc. We allow these factors to be different for each supplier, and each lot processed by the same supplier. We refer to this problem as the Assembly Lot Streaming Problem (ALSP). We show that the ALSP can be solved using two steps. The first step consists of solution to several two-stage, single-lot, flow shop, makespan minimization problems. The solution to these problems generate prospective sublot sizes. Solution methods outlined in the existing literature can be used to complete this step. The second step obtains optimal number of sublots and production sequence. For a given production sequence, this step can be executed in polynomial-time; otherwise, the second step problem is NP-hard and integer programming formulations and decomposition-based methodologies are investigated for their solution. We make very limited assumptions regarding the handling cost and the relationship between the supplier lead time and number of sublots used. As a result, our solution methodology has a wide scope. / Ph. D.

In this dissertation, we investigate the use of lot streaming in a two-stage assembly system and a two-stage hybrid flow shop in order to improve system performance. Lot streaming accelerates the flow of a production lot through a production process by splitting it into sublots, and then, processing these sublots in an overlapping fashion over the machines, thereby reducing work-in-process and cycle-time. Traditionally, lot streaming has been applied to problems in various flow shop machine configurations. It has also been applied to machine environments of job shop, open shop, and parallel machines. Its application to assembly system is relatively new. The two-stage assembly system that we consider consists of multiple suppliers at Stage 1 with each supplier producing one type of a subassembly (or a component), and one or more assembly locations at Stage 2, where the subassemblies are then put together. Lot-attached and sublot-attached setup time and cost are encountered on the machines at both the stages, and sublot-attached time and cost are encountered for the transfer of sublots from Stage 1 to Stage 2. Mass customization is an example of such a system in which the final assembly of a product is postponed to capture specific customer demands. Dell Computer constitutes a real-life example of this system. A customer picks his/her computer processor, memory, storage, and other equipment, on Dell's web site. Dell's supply chain is configured to obtain subassemblies from suppliers (stage 1), and then, to assemble the requisite systems in different market areas (stage 2). This enables a reduction in operating cost while improving responsiveness to customers. The problem that we address is as follows: Given a maximum number of sublots of each lot, determine the number of sublots to use (assuming equal sublot sizes), and also, the sequence in which to process the lots, in order to minimize two criteria, namely, makespan, total cost. We propose two column generation-based methods that rely on different decomposition schemes. The results of our computational investigation conducted by using randomly generated data sets reveal that the proposed column generation methods obtain solutions in a few seconds of CPU time while the direct solution by CPLEX of a mixed integer programming model of the problem requires much larger CPU times. For the hybrid flow shop lot streaming problem, the machine configuration that we consider consists of one machine at Stage 1 and two machines at Stage 2 (designated as 1+2 system). A single lot is to be processed in the system, and the objective is to minimize the makespan. A removal time is associated with each sublot at Stage 1. We present a mixed integer programming model for this problem to determine optimal number of sublots and sublot sizes. First, we consider the case of a given number of sublots for which we develop closed-form expressions to obtain optimal, continuous sublot sizes. Then, we consider determination of optimal number of sublots in addition to their sizes. We develop an upper bound on optimal number of sublots, and use a simple search procedure in conjunction with the closed-form expressions for sublot sizes to obtain an optimal solution. We also consider the problem of determining integer sublot sizes, and propose a heuristic method that directly solves the mixed integer programming model after having fixed values of appropriate variables. The results of our numerical experimentation reveal the efficacy of the proposed method to obtain optimal, continuous sublot sizes, and also, that of the proposed heuristic method to obtain integer sublot sizes, which are within 0.2% of optimal solutions for the testbed of data used, each obtained within a few seconds of CPU time. The last problem that we address is an extension of the single-lot lot streaming problem for a $1+2$ hybrid flow shop considered above to the case of multiple lots, where each lot contains items of a unique product type. We consider two objectives: minimize makespan, and minimize the sum of the completion times for all the lots. The consideration of multiple lots introduces a complicating issue of sequencing the lots. We use the results derived for the single-lot problem and develop effective heuristic methods for this problem. The results of our computational investigation on the use of different heuristic methods reveal their efficacy in solving this problem. / Ph. D.

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.

This research is concerned with the development of efficient solutions to various problems that arise in the flow-shop environments which utilize lot-streaming. Lot streaming is a commonly used process of splitting production lots into sublots and, then, of scheduling the sublots in an overlapping fashion on the machines, so as to expedite the progress of orders in production and to improve the overall performance of the production system. The different lot-streaming problems that arise in various flow-shop environments have been divided into two categories, single-lot problems and multiple-lot problems. Further classification of the multiple-lot problems into the lot streaming sequencing problem (LSSP) and the flow-shop lot-streaming (FSLS) problem is made in this work. This classification is motivated by the occurrence of these problems in the industry. Several variants of these problems are addressed in this research. In agreement with numerous practical applications, we assume sublots of equal sizes. It turns out that this restriction paves the way to the relaxation of several typical limitations of current lot-streaming models, such as assumption of negligible transfer and setup times or consideration of only the makespan criterion. For the single-lot problem, a goal programming (GP) approach is utilized to solve the problem for a unified cost objective function comprising of the makespan, the mean flow time, the average work-in-process (WIP), and the setup and handling related costs. A very fast optimal solution algorithm is proposed for finding the optimal number of sublots (and, consequently, the sublot size) for this unified cost objective function in a general m-machine flow shop. For the more complicated multiple-lot problem, a near-optimal heuristic for the solution of the LSSP is developed. This proposed heuristic procedure, referred to as the Bottleneck Minimal Idleness (BMI) heuristic, identifies and employs certain properties of the problem that are irregular in traditional flow-shop problems, particularly the fact that the sublot sizes eminating from the same lot type and their processing times (on the same machines) are identical. The BMI heuristic attempts to maximize the time buffer prior to the bottleneck machine, thereby minimizing potential bottleneck idleness, while also looking-ahead to sequence the lots with large remaining process time earlier in the schedule. A detailed experimental study is performed to show that the BMI heuristic outperforms the Fast Insertion Heuristic (the best known heuristic for flow-shop scheduling), when modified for Lot Streaming (FIHLS) and applied to the problem on hand. For the FSLS problem, several algorithms are developed. For the two-machine FSLS problem with an identical sublot-size for all the lots, an optimal pseudo-polynomial solution algorithm is proposed. For all practical purposes (i.e., even for very large lot sizes), this algorithm is very fast. For the case in which the sublot-sizes are lot-based, optimal and heuristic procedures are developed. The heuristic procedure is developed to reduce the complexity of the optimal solution algorithm. It consists of a construction phase and an improvement phase. In the construction phase, it attempts to find a near-optimal sequence for the lots and then, in the improvement phase, given the sequence, it attempts to optimize the lot-based sublot-sizes of each of the lots. Extensions of the solution procedures are proposed for the general m-machine FSLS problem. A comprehensive simulation study of a flow shop system under lot streaming is conducted to support the validity of the results and to demonstrate the effectiveness of the heuristic procedures. This study clearly indicates that, even in dynamic practical situations, the BMI rule, which is based on the proposed BMI heuristic, outperforms existing WIP rules, commonly used in industry, in scheduling a flow-shop that utilizes lot streaming. With respect to the primary performance measure - cycle time (or MFT) - the BMI rule demonstrates a clear improvement over other WIP rules. It is further shown that it also outperforms other WIP rules with respect to the output variability measure, another important measure in flow-shop systems. The effects of several other factors, namely system randomness, system loading, and bottleneck-related (location and number), in a flow-shop under lot streaming, are also reported. / Ph. D.

As the Army transitions to the Army Force Generation (ARFORGEN) deployment cycle, it must adjust its many operations in support of ARFORGEN. Specifically, the Initial Military Training (IMT) must be able to adjust the scheduling of its classes for newly enlisted service members to finish training such that they fulfill Brigade Combat Team (BCT) requirements within their common due windows. We formulate this problem as a lot streaming problem. Lot streaming splits a batch of jobs into sublots,which are then processed over the machines in an overlapping fashion. To schedule classes for the IMT, there are two stages that must be coordinated: Basic Training (BT) and Advanced Individual Training (AIT). For the Army Force Generation problem, the classes are considered as sublots that are streamed from one stage to the next. For this process, the model formulation must address determination of class sizes and scheduling of soldiers and classes at the two stages such that (1) the start times of the soldiers at Stage 2 are greater than their completion times at Stage 1, and (2) the assignment of requisite number of soldiers is made to each BCT, so as to minimize the total flow time. We propose a decomposition-based approach for the solution of this problem. In an effort to decompose the problem, the original lot streaming problem is reformulated such that the master problem selects an optimal combination of schedules for training classes and assigning soldiers to BCTs. A complete schedule selected in the master problem includes the assignments of soldiers to classes in BT, AIT, and their assignments to the BCTs, so as to minimize the total flow time as well as earliness and tardiness for regular Army units. Earliness and Tardiness are defined as the length of the time a soldier waits before and after the due date, respectively, of the BCT to which he or she is assigned. Our decomposition-based method enables solution of larger problem instances without running out of memory, and it affords CPU time reductions when compared with the CPU times required for these problem instances obtained via direct application of CPLEX 12.1. Our investigation into the structure of the problem has enabled further improvement of the proposed decomposition-based method. This improvement is achieved because of a result, which we show, that the first and second-stage scheduling problems need not be solved as one combined subproblem, but rather, they can be solved sequentially, the first stage problem followed by the second stage problem. The combination of Stage 1 and Stage 2 problems as one subproblem creates several additional enumerations of possible schedules the model must generate. By reducing this number of enumerations, the computational effort involved in solving the model reduces significantly, thereby allowing reductions in CPU time. In the Sequential approach, the completion times of soldiers determined at Stage 1 are passed to Stage 2 as bounds on their completion times at Stage 2. We prove that solving the combined subproblem sequentially as two subproblems is optimal when the first stage has no limit on the batch size and the ready times of the soldiers at Stage 1 are the same. For the Army Force Generation problem, we use unequal ready times, and therefore, solving the scheduling problems for the first two stages as sequential subproblems can lead to suboptimal solutions. Our experimental investigation shows efficacy of solving larger-sized problem instances with this method. We also recommend various potential additions to improve the Sequential approach for application to the overall Army problem. We have also demonstrated the use of our methodology to a real-life problem instance. Our methodology results in schedules for IMT with an estimated 28% reduction in mean flow time for soldiers over what is currently experienced in practice. We apply this Sequential approach to various extensions of the problem on hand that pertain to hybrid flow shop and agile manufacturing environments. Results of our computational investigation show the effectiveness of using the Sequential approach over direct solution by CPLEX from the viewpoint of both optimality gap and the CPU time required. In particular, we consider two different model configurations for a hybrid flow shop and three different model configurations for an agile manufacturing facility. / Ph. D.

In this work, we address a variety of problems with applications to `ethanol production from biomass', `agile manufacturing' and `mass customization' domains. Our motivation stems from the potential use of biomass as an alternative to non-renewable fuels, the prevalence of `flexible manufacturing systems', and the popularity of `mass customization' in today's highly competitive markets. Production scheduling and design and optimization of logistics network mark the underlying topics of our work. In particular, we address three problems, Biomass Logistics Problem, Hybrid Flow Shop Scheduling Problem, and Stochastic Demand Assembly Job Scheduling Problem. The Biomass Logistics Problem is a strategic cost analysis for setup and operation of a biomass supply chain network that is aimed at the production of ethanol from switchgrass. We discuss the structural components and operations for such a network. We incorporate real-life GIS data of a geographical region in a model that captures this problem. Consequently, we develop and demonstrate the effectiveness of a `Nested Benders' based algorithm for an efficient solution to this problem. The Hybrid Flow Shop Scheduling Problem concerns with production scheduling of a lot over a two-stage hybrid flow shop configuration of machines, and is often encountered in `flexible manufacturing systems'. We incorporate the use of `lot-streaming' in order to minimize the makespan value. Although a general case of this problem is NP-hard, we develop a pseudo-polynomial time algorithm for a special case of this problem when the sublot sizes are treated to be continuous. The case of discrete sublot sizes is also discussed for which we develop a branch-and-bound-based method and experimentally demonstrate its effectiveness in obtaining a near-optimal solution. The Stochastic Demand Assembly Job Scheduling Problem deals with the scheduling of a set of products in a production setting where manufacturers seek to fulfill multiple objectives such as `economy of scale' together with achieving the flexibility to produce a variety of products for their customers while minimizing delivery lead times. We design a novel methodology that is geared towards these objectives and propose a Lagrangian relaxation-based algorithm for efficient computation. / Doctor of Philosophy / In this work, we organize our research efforts in three broad areas - Biomass Supply Chain, Hybrid Flow Shop, and Assembly Job Shop, which are separate in terms of their application but connected by scheduling and logistics as the underlying functions. For each of them, we formulate the problem statement and identify the challenges and opportunities from the viewpoint of mathematical decision making. We use some of the well known results from the theory of optimization and linear algebra to design effective algorithms in solving these specific problems within a reasonable time limit. Even though the emphasis is on conducting an algorithmic analysis of the proposed solution methods and in solving the problems analytically, we strive to capture all the relevant and practical features of the problems during formulation of each of the problem statement, thereby maintaining their applicability. The Biomass Supply Chain pertains to the production of fuel grade ethanol from naturally occurring biomass in the form of switchgrass. Such a system requires establishment of a supply chain and logistics network that connects the production fields at its source, the intermediate points for temporary storage of the biomass, and bio-energy plant and refinery at its end for conversion of the cellulosic content in the biomass to crude oil and ethanol, respectively. We define the components and operations necessary for functioning of such a supply chain. The Biomass Logistics Problem that we address is a strategic cost analysis for setup and operation of such a biomass supply chain network. We focus our attention to a region in South Central Virginia and use the detailed geographic map data to obtain land use pattern in the region. We conduct survey of existing literature to obtain various transportation related cost factors and costs associated with the use of equipment. Our ultimate aim here is to understand the feasibility of running a biomass supply chain in the region of interest from an economic standpoint. As such, we represent the Biomass Logistics Problem with a cost-based optimization model and solve it in a series of smaller problems. A Hybrid Flow Shop (HFS) is a configuration of machines that is often encountered in the flexible manufacturing systems, wherein a particular station of machines can execute processing of jobs/tasks simultaneously. In our work, we approach a specific type of HFS, with a single machine at the first stage and multiple identical machines at the second stage. A batch or lot of jobs/items is considered for scheduling over such an HFS. Depending upon the area of application, such a batch is either allowed to be split into continuous sections or restricted to be split in discrete sizes only. The objective is to minimize the completion time of the last job on its assigned machine at the second stage. We call this problem, Hybrid Flow Shop Scheduling Problem, which is known to be a hard problem in literature. We aim to derive the results which will reduce the complexity of this problem, and develop both exact as well as heuristic methods in order to obtain near-optimal solution to this problem. An Assembly Job Shop is a variant of the classical Job Shop which considers scheduling a set of assembly operations over a set of assembly machines. Each operation can only be started once all the other operations in its precedence relationship are completed. Assembly Job Shop are at the core of some of the highly competitive manufacturing facilities that are principled on the philosophy of Mass Customization. Assuming an inherent nature of demand uncertainty, this philosophy aims to achieve ‘economy of scale’ together with flexibility to produce a variety of products for the customers while minimizing the delivery lead times simultaneously. We incorporate some of these challenges in a concise framework of production scheduling and call this problem as Stochastic Demand Assembly Job Scheduling Problem. We design a novel methodology that is geared towards achieving the set objectives and propose an effective algorithm for efficient computation.

No description available.

This dissertation is devoted to the modeling, analysis and development of solution approaches for some optimization-related problems encountered in industrial and manufacturing settings. We begin by introducing a special type of traveling salesman problem called "High Multiplicity Asymmetric Traveling Salesman Problem" (HMATSP). We propose a new formulation for this problem, which embraces a flow-based subtour elimination structure, and establish its validity for this problem. The model is, then, incorporated as a substructure in our formulation for a lot-sizing problem involving parallel machines and sequence-dependent setup costs, also known as the "Chesapeake Problem". Computational results are presented to demonstrate the efficacy of our modeling approach for both the generic HMATSP and its application within the context of the Chesapeake Problem. Next, we investigate an integrated lot-sizing and scheduling problem that is encountered in the primary manufacturing facility of pharmaceutical manufacturing. This problem entails determination of production lot sizes of multiple products and sequence in which to process the products on machines, which can process lots (batches) of a fixed size (due to limited capacity of containers) in the presence of sequence-dependent setup times/costs. We approach this problem via a two-stage optimization procedure. The lot-sizing decision is considered at stage 1 followed by the sequencing of production lots at stage 2. Our aim for the stage 1 problem is to allocate batches of products to time-periods in order to minimize the sum of the inventory and backordering costs subject to the available capacity in each period. The consideration of batches of final products, in addition to those for intermediate products, which comprise a final product, further complicates the lot-sizing problem. The objective for the stage 2 problem is to minimize sequence-dependent setup costs. We present a novel unifying model and a column generation-based optimization approach for this class of lot-sizing and sequencing problems. Computational experience is first provided by using randomly generated data sets to test the performances of several variants of our proposed approach. The efficacy of the best of these variants is further demonstrated by applying it to the real-life data collected with the collaboration of a pharmaceutical manufacturing company. Then, we address a single-lot, lot streaming problem for a two-stage assembly system. This assembly system is different from the traditional flow shop configuration. It consists of m parallel subassembly machines at stage 1, each of which is devoted to the production of a component. A single assembly machine at stage 2, then, assembles products after components (one each from the subassembly machines at the first stage) have been completed. Lot-detached setups are encountered on the machines at the first and second stages. Given a fixed number of transfer batches (or sublots) from each of the subassembly machines at stage 1 to the assembly machine at stage 2, our problem is to find sublot sizes so as to minimize the makespan. We develop optimality conditions to determine sublot sizes for the general problem, and present polynomial-time algorithms to determine optimal sublot sizes for the assembly system with two and three subassembly machines at stage 1. Finally, we extend the above single-lot, lot streaming problem for the two-stage assembly system to multiple lots, but still, for the objective of minimizing the makespan. Due to the presence of multiple lots, we need to address the issue of the sequencing of the lots along with lot-splitting, a fact which adds complexity to the problem. Some results derived for the single-lot version of this problem have successfully been generalized for this case. We develop a branch-and-bound-based methodology for this problem. It relies on effective lower bounds and dominance properties, which are also derived. Finally, we present results of computational experimentation to demonstrate the effectiveness of our branch-and-bound-based methodology. Because of the tightness of our upper and lower bounds, a vast majority of the problems can be solved to optimality at root node itself, while for others, the average gap between the upper and lower bounds computed at node zero is within 0.0001%. For a majority of these problems, our dominance properties, then, effectively truncate the branch-and-bound tree, and obtain optimal solution within 500 seconds. / Ph. D.