The pooling problem is one of the fundamental optimization problems encountered in the petroleum industry. In the pooling problem, final products are produced using two stages of blending operations. In the first stage, raw materials are mixed together to produce intermediate products. In the second stage, intermediate products and some of the raw materials are blended together according to product demand and quality requirements. Generally, the pooling problem is a nonlinear problem because the output stream qualities, which are unknown, depend on the volume, which is also unknown, and on the quality of the input streams. Specifically, nonlinearity and nonconvexity are due to the use of bilinear terms either in the quality constraints or in the objective function. Nonlinearity and nonconvexity result in several local optima, making the process of solving large-scale pooling problems to global optimality very challenging. Therefore, developing efficient heuristics for large-scale pooling problems is very desirable. Moreover, devising tight bounds on the global solutions is essential to assess the quality of the proposed heuristics. In this thesis, we use a Lagrangean relaxation approach where feasible solutions and lower bounds are generated for the pooling problem. The procedure targets all nonlinear constraints and penalizes their violation in the objective function. The resulting Lagrangean subproblem has a nonlinear objective function and linear constraints. The Lagrangean subproblem is reformulated as a mixed integer programming problem where the nonlinearities in the objective function are eliminated at the expense of using binary variables. The obtained Lagrangean lower bounds are strengthened using valid cuts that are based on the relaxed bilinear terms. In addition, at every iteration of the Lagrangean algorithm, the subproblem solutions are used to generate feasible solutions to the pooling problem. The procedure is applied to fifteen pooling problems collected from the literature. Some of these problems have a single quality and others have multiple qualities. Numerical results show that for eight solved cases, the obtained Lagrangean lower bounds are equal to the global optima, whereas for seven cases the obtained Lagrangean lower bound is on average 8.2% from the global optimum. Numerical results indicate the efficiency of the heuristic. For nine cases, the heuristic gives the global solution, and for the other cases the heuristic solutions are within 1.8% of the global optimum.

A constrained shortest path algorithm is developed and implemented in Matlab to optimize the management decision-making process, which is a potential tool for managers. An empirical analysis is performed using Statistics Canada’s Workplace and Employee Survey (WES), which consists of variables relating to employers and their employees, conducted from years 1999 through 2004, inclusively. Specifically, the research explores the relationships among variables such as innovation, technology use, training and human resource management and its effect on the success of the firm in terms of profit and labor productivity. The results are compared to the current literature in technology and organizational management. In general, it is discovered that optimal management strategies are highly dependent upon the performance in which the firm operates. Additionally, the constrained shortest path algorithm developed for the thesis is tested against other leading methods in the literature and is found to be quite competitive. The tests are run on randomly generated constrained shortest path problems of varying degrees of complexity with the algorithm performing well on all levels.

Make-to-order (MTO) and assemble-to-order (ATO) systems are emerging business strategies in managing responsive supply chains, characterized by high product variety, highly variable customer demand, and short product life cycle. Motivated by the strategic importance of response time in today’s global business environment, this thesis presents models and solution approaches for response time reduction and service-level differentiation in designing MTO and ATO supply chains. In the first part, we consider the problem of response time reduction in the design of MTO supply chains. More specifically, we consider an MTO supply chain design model that seeks to simultaneously determine the optimal location and the capacity of distribution centers (DCs) and allocate stochastic customer demand to DCs, so as to minimize the response time in addition to the fixed cost of opening DCs and equipping them with sufficient assembly capacity and the variable cost of serving customers. The DCs are modelled as M/G/1 queues and response times are computed using steady-state waiting time results from queueing theory. The problem is set up as a network of spatially distributed M/G/1 queues and modelled as a nonlinear mixed-integer program. We linearize the model using a simple transformation and a piece-wise linear and concave approximation. We present two solution procedures: an exact solution approach based on cutting plane method and a Lagrangean heuristic for solving large instances of the problem. While the cutting plane approach provides the optimal solution for moderate instances in few iterations, the Lagrangean heuristic succeeds in finding feasible solutions for large instances that are within 5% from the optimal solution in reasonable computation times. We show that the solution procedure can be extended to systems with multiple customer classes. Using a computational study, we also show that substantial reduction in response times can be achieved with minimal increase in total costs in the design of responsive supply chains. Furthermore, we find the supply chain configuration (DC location, capacity, and demand allocation) that considers congestion and its effect on response time can be very different from the traditional configuration that ignores congestion. The second part considers the problem of response time reduction in the design of a two-echelon ATO supply chain, where a set of plants and DCs are to be established to distribute a set of finished products with non-trivial bill-of-materials to a set of customers with stochastic demand. The model is formulated as a nonlinear mixed integer programming problem. Lagrangean relaxation exploits the echelon structure of the problem to decompose into two subproblems - one for the make-tostock echelon and the other for the MTO echelon. We use the cutting plane based approach proposed above to solve the MTO echelon subproblem. While Lagrangean relaxation provides a lower bound, we present a heuristic that uses the solution of the subproblems to construct an overall feasible solution. Computational results reveal that the heuristic solution is on average within 6% from its optimal. In the final part of the thesis, we consider the problem of demand allocation and capacity selection in the design of MTO supply chains for segmented markets with service-level differentiated customers. Demands from each customer class arrives according to an independent Poisson process and the customers are served from shared DCs with finite capacity and generally distributed service times. Service-levels of various customer classes are expressed as the fraction of their demand served within a specified response (sojourn) time. Our objective is to determine the optimal location and the capacity of DCs and the demand allocation so as to minimize the sum of the fixed cost of opening DCs and equipping them with sufficient capacity and the variable cost of serving customers subject to service-level constraints for multiple customer classes. The problem is set up as a network of spatially distributed M/M/1 priority queues and modelled as a nonlinear mixed integer program. Due to the lack of closed form solution for service-level constraints for multiple classes, we present an iterative simulation-based cutting plane approach that relies on discrete-event simulation for the estimation of the service-level function and its subgradients. The subgradients obtained from the simulation are used to generate cuts that are appended to the mixed integer programming model. We also present a near-exact matrix analytic procedure to validate the estimates of the service-level function and its subgradients from the simulation. Our computational study shows that the method is robust and provides an optimal solution in most of the cases in reasonable computation time. Furthermore, using computational study, we examine the impact of different parameters on the design of supply chains for segmented markets and provide some managerial insights.

Recently, a new form of organizing, sharing and finding information, named tagging, has gained importance because its results are the product of the combined efforts of the actual users’ opinions of the information. In this paper, we explore the conceptual model of the del.icio.us tagging system in order to investigate the degree to which the tagging system’s conceptual model reflects the human conceptual knowledge structure at both the population level and the individual level. We use datasets extracted from the del.icio.us system from 2003 to 2007 to obtain the strength of connection among tags, and compare that with data for the association of the same concepts by actual human beings. The results show that, overall, the conceptual model for the del.icio.us tagging system captures human’s notion of concept similarity. Several potential applications are mentioned.

The pooling problem is one of the fundamental optimization problems encountered in the petroleum industry. In the pooling problem, final products are produced using two stages of blending operations. In the first stage, raw materials are mixed together to produce intermediate products. In the second stage, intermediate products and some of the raw materials are blended together according to product demand and quality requirements. Generally, the pooling problem is a nonlinear problem because the output stream qualities, which are unknown, depend on the volume, which is also unknown, and on the quality of the input streams. Specifically, nonlinearity and nonconvexity are due to the use of bilinear terms either in the quality constraints or in the objective function. Nonlinearity and nonconvexity result in several local optima, making the process of solving large-scale pooling problems to global optimality very challenging. Therefore, developing efficient heuristics for large-scale pooling problems is very desirable. Moreover, devising tight bounds on the global solutions is essential to assess the quality of the proposed heuristics. In this thesis, we use a Lagrangean relaxation approach where feasible solutions and lower bounds are generated for the pooling problem. The procedure targets all nonlinear constraints and penalizes their violation in the objective function. The resulting Lagrangean subproblem has a nonlinear objective function and linear constraints. The Lagrangean subproblem is reformulated as a mixed integer programming problem where the nonlinearities in the objective function are eliminated at the expense of using binary variables. The obtained Lagrangean lower bounds are strengthened using valid cuts that are based on the relaxed bilinear terms. In addition, at every iteration of the Lagrangean algorithm, the subproblem solutions are used to generate feasible solutions to the pooling problem. The procedure is applied to fifteen pooling problems collected from the literature. Some of these problems have a single quality and others have multiple qualities. Numerical results show that for eight solved cases, the obtained Lagrangean lower bounds are equal to the global optima, whereas for seven cases the obtained Lagrangean lower bound is on average 8.2% from the global optimum. Numerical results indicate the efficiency of the heuristic. For nine cases, the heuristic gives the global solution, and for the other cases the heuristic solutions are within 1.8% of the global optimum.

A constrained shortest path algorithm is developed and implemented in Matlab to optimize the management decision-making process, which is a potential tool for managers. An empirical analysis is performed using Statistics Canada’s Workplace and Employee Survey (WES), which consists of variables relating to employers and their employees, conducted from years 1999 through 2004, inclusively. Specifically, the research explores the relationships among variables such as innovation, technology use, training and human resource management and its effect on the success of the firm in terms of profit and labor productivity. The results are compared to the current literature in technology and organizational management. In general, it is discovered that optimal management strategies are highly dependent upon the performance in which the firm operates. Additionally, the constrained shortest path algorithm developed for the thesis is tested against other leading methods in the literature and is found to be quite competitive. The tests are run on randomly generated constrained shortest path problems of varying degrees of complexity with the algorithm performing well on all levels.

Make-to-order (MTO) and assemble-to-order (ATO) systems are emerging business strategies in managing responsive supply chains, characterized by high product variety, highly variable customer demand, and short product life cycle. Motivated by the strategic importance of response time in today’s global business environment, this thesis presents models and solution approaches for response time reduction and service-level differentiation in designing MTO and ATO supply chains. In the first part, we consider the problem of response time reduction in the design of MTO supply chains. More specifically, we consider an MTO supply chain design model that seeks to simultaneously determine the optimal location and the capacity of distribution centers (DCs) and allocate stochastic customer demand to DCs, so as to minimize the response time in addition to the fixed cost of opening DCs and equipping them with sufficient assembly capacity and the variable cost of serving customers. The DCs are modelled as M/G/1 queues and response times are computed using steady-state waiting time results from queueing theory. The problem is set up as a network of spatially distributed M/G/1 queues and modelled as a nonlinear mixed-integer program. We linearize the model using a simple transformation and a piece-wise linear and concave approximation. We present two solution procedures: an exact solution approach based on cutting plane method and a Lagrangean heuristic for solving large instances of the problem. While the cutting plane approach provides the optimal solution for moderate instances in few iterations, the Lagrangean heuristic succeeds in finding feasible solutions for large instances that are within 5% from the optimal solution in reasonable computation times. We show that the solution procedure can be extended to systems with multiple customer classes. Using a computational study, we also show that substantial reduction in response times can be achieved with minimal increase in total costs in the design of responsive supply chains. Furthermore, we find the supply chain configuration (DC location, capacity, and demand allocation) that considers congestion and its effect on response time can be very different from the traditional configuration that ignores congestion. The second part considers the problem of response time reduction in the design of a two-echelon ATO supply chain, where a set of plants and DCs are to be established to distribute a set of finished products with non-trivial bill-of-materials to a set of customers with stochastic demand. The model is formulated as a nonlinear mixed integer programming problem. Lagrangean relaxation exploits the echelon structure of the problem to decompose into two subproblems - one for the make-tostock echelon and the other for the MTO echelon. We use the cutting plane based approach proposed above to solve the MTO echelon subproblem. While Lagrangean relaxation provides a lower bound, we present a heuristic that uses the solution of the subproblems to construct an overall feasible solution. Computational results reveal that the heuristic solution is on average within 6% from its optimal. In the final part of the thesis, we consider the problem of demand allocation and capacity selection in the design of MTO supply chains for segmented markets with service-level differentiated customers. Demands from each customer class arrives according to an independent Poisson process and the customers are served from shared DCs with finite capacity and generally distributed service times. Service-levels of various customer classes are expressed as the fraction of their demand served within a specified response (sojourn) time. Our objective is to determine the optimal location and the capacity of DCs and the demand allocation so as to minimize the sum of the fixed cost of opening DCs and equipping them with sufficient capacity and the variable cost of serving customers subject to service-level constraints for multiple customer classes. The problem is set up as a network of spatially distributed M/M/1 priority queues and modelled as a nonlinear mixed integer program. Due to the lack of closed form solution for service-level constraints for multiple classes, we present an iterative simulation-based cutting plane approach that relies on discrete-event simulation for the estimation of the service-level function and its subgradients. The subgradients obtained from the simulation are used to generate cuts that are appended to the mixed integer programming model. We also present a near-exact matrix analytic procedure to validate the estimates of the service-level function and its subgradients from the simulation. Our computational study shows that the method is robust and provides an optimal solution in most of the cases in reasonable computation time. Furthermore, using computational study, we examine the impact of different parameters on the design of supply chains for segmented markets and provide some managerial insights.

Recently, a new form of organizing, sharing and finding information, named tagging, has gained importance because its results are the product of the combined efforts of the actual users’ opinions of the information. In this paper, we explore the conceptual model of the del.icio.us tagging system in order to investigate the degree to which the tagging system’s conceptual model reflects the human conceptual knowledge structure at both the population level and the individual level. We use datasets extracted from the del.icio.us system from 2003 to 2007 to obtain the strength of connection among tags, and compare that with data for the association of the same concepts by actual human beings. The results show that, overall, the conceptual model for the del.icio.us tagging system captures human’s notion of concept similarity. Several potential applications are mentioned.

Most literature on facility location assumes a fixed set-up cost and a linear variable cost. However, as production volume increases, cost savings are achieved through economies of scale, and then when production exceeds a certain capacity level, congestion occurs and costs start to increase significantly. This leads to an S-shaped cost function that makes the location-allocation decisions challenging. This thesis presents a nonlinear mixed integer programming formulation for the facility location problem with economies of scale and congestion and proposes a Lagrangian solution approach. Testing on a variety of functions and cost settings reveals the efficiency of the proposed approach in finding solutions that are within an average gap of 3.79% from optimal.

We study a two-stage stochastic facility location problem in the context of disaster response network design. The uncertainty inherent in disaster occurrence and impact is captured by defining scenarios to reflect a large spectrum of possible occurrences. In the first stage (pre-event response), planners should decide on locating a set of facilities in strategic regions. In the second stage (post-event response), some of these facilities are to be activated to respond to demand in the disaster affected region. The second-stage decisions depend on disaster occurrence and impact which are highly uncertain. To model this uncertainty, a large number of scenarios are defined to reflect a large spectrum of possible occurrences. In this case, facility activation and demand allocation decisions are made under each scenario. The aim is to minimize the total cost of locating facilities in the first stage plus the expected cost of facility activation and demand allocation under all scenarios in the second stage while satisfying demand subject to facility and arc capacities. We propose a mixed integer programming model with binary facility location variables in the first stage and binary facility activation variables and fractional demand allocation variables in the second stage. We propose two Lagrangian relaxations and several valid cuts to improve the bounds. We experiment with aggregated, disaggregated and hybrid implementations in calculating the Lagrangian bound and develop several Lagrangian heuristics. We perform extensive numerical testing to investigate the effect of valid cuts and disaggregation and to compare the relaxations. The second relaxation proved to provide a tight bound as well as high quality feasible solutions.