Spelling suggestions: "subject:"managemement sciences"" "subject:"managementment sciences""
1 |
A Lagrangean Relaxation and A Heuristic for the Pooling ProblemAlmutairi, Hossa January 2008 (has links)
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.
|
2 |
Technology and Strategic Management Decision-Making as a Constrained Shortest Path ProblemFormaneck, Steven David January 2008 (has links)
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.
|
3 |
Response Time Reduction and Service Level Differentiation in Supply Chain Design: Models and Solution ApproachesVidyarthi, Navneet 20 May 2009 (has links)
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.
|
4 |
Collective Intelligence in Collaborative Tagging SystemYang, Xiaoyin January 2009 (has links)
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.
|
5 |
A Lagrangean Relaxation and A Heuristic for the Pooling ProblemAlmutairi, Hossa January 2008 (has links)
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.
|
6 |
Technology and Strategic Management Decision-Making as a Constrained Shortest Path ProblemFormaneck, Steven David January 2008 (has links)
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.
|
7 |
Response Time Reduction and Service Level Differentiation in Supply Chain Design: Models and Solution ApproachesVidyarthi, Navneet 20 May 2009 (has links)
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.
|
8 |
Collective Intelligence in Collaborative Tagging SystemYang, Xiaoyin January 2009 (has links)
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.
|
9 |
Facility location with economies of scale and congestionLu, Da January 2010 (has links)
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.
|
10 |
A Lagrangian Relaxation Approach to a Two-Stage Stochastic Facility Location Problem with Second-Stage Activation CostGhodsi, Ghazal January 2012 (has links)
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.
|
Page generated in 0.0904 seconds