Spelling suggestions: "subject:"heuristic.""
231 |
Improved formulations, heuristics and metaheuristics for the dynamic demand coordinated lot-sizing problemNarayanan, Arunachalam 02 June 2009 (has links)
Coordinated lot sizing problems, which assume a joint setup is shared by a product
family, are commonly encountered in supply chain contexts. Total system costs include a
joint set-up charge each time period any item in the product family is replenished, an item
set-up cost for each item replenished in each time period, and inventory holding costs. Silver
(1979) and subsequent researchers note the occurrence of coordinated replenishment
problems within manufacturing, procurement, and transportation contexts. Due to their
mathematical complexity and importance in industry, coordinated lot-size problems are
frequently studied in the operations management literature.
In this research, we address both uncapacitated and capacitated variants of the
problem. For each variant we propose new problem formulations, one or more construction
heuristics, and a simulated annealing metaheuristic (SAM).
We first propose new tight mathematical formulations for the uncapacitated problem
and document their improved computational efficiency over earlier models. We then
develop two forward-pass heuristics, a two-phase heuristic, and SAM to solve the
uncapacitated version of the problem. The two-phase and SAM find solutions with an
average optimality gap of 0.56% and 0.2% respectively. The corresponding average
computational requirements are less than 0.05 and 0.18 CPU seconds.
Next, we propose tight mathematical formulations for the capacitated problem and
evaluate their performance against existing approaches. We then extend the two-phase
heuristic to solve this more general capacitated version. We further embed the six-phase
heuristic in a SAM framework, which improves heuristic performance at minimal additional
computational expense. The metaheuristic finds solutions with an average optimality gap of 0.43% and within an average time of 0.25 CPU seconds. This represents an improvement
over those reported in the literature.
Overall the heuristics provide a general approach to the dynamic demand lot-size
problem that is capable of being applied as a stand-alone solver, an algorithm embedded
with supply chain planning software, or as an upper-bounding procedure within an
optimization based algorithm.
Finally, this research investigates the performance of alternative coordinated lotsizing
procedures when implemented in a rolling schedule environment. We find the
perturbation metaheuristic to be the most suitable heuristic for implementation in rolling
schedules.
|
232 |
Decomposition Based Solution Approaches for Multi-product Closed-Loop Supply Chain Network Design ModelsEaswaran, Gopalakrishnan 16 January 2010 (has links)
Closed-loop supply chain (CLSC) management provides opportunity for cost
savings through the integration of product recovery activities into traditional supply
chains. Product recovery activities, such as remanufacturing, reclaim a portion of the
previously added value in addition to the physical material.
Our problem setting is motivated by the practice of an Original Equipment Manufacturer
(OEM) in the automotive service parts industry, who operates a well established
forward network. The OEM faces customer demand due to warranty and
beyond warranty vehicle repairs. The warranty based demand induces part returns.
We consider a case where the OEM has not yet established a product recovery network,
but has a strategic commitment to implement remanufacturing strategy. In
accomplishing this commitment, complications arise in the network design due to activities
and material movement in both the forward and reverse networks, which are
attributed to remanufacturing. Consequently, in implementing the remanufacturing
strategy, the OEM should simultaneously consider both the forward and reverse flows
for an optimal network design, instead of an independent and sequential modeling approach.
In keeping with these motivations, and with the goal of implementing the
remanufacturing strategy and transforming independent forward and reverse supply
chains to CLSCs, we propose to investigate the following research questions: 1. How do the following transformation strategies leverage the CLSC?s overall cost
performance?
? Extending the already existing forward channel to incorporate reverse
channel activities.
? Designing an entire CLSC network.
2. How do the following network flow integration strategies influence the CLSC?s
overall cost performance?
? Using distinct forward and reverse channel facilities to manage the corresponding
flows.
? Using hybrid facilities to coordinate the flows.
In researching the above questions, we address significant practical concerns in
CLSC network design and provide cost measures for the above mentioned strategies.
We also contribute to the current literature by investigating the optimal CLSC network
design. More specifically, we propose three models and develop mathematical
formulations and novel solution approaches that are based on decomposition techniques,
heuristics, and meta-heuristic approaches to seek a solution that characterizes
the configuration of the CLSC network, along with the coordinated forward and
reverse flows.
|
233 |
Optimization in Geometric Graphs: Complexity and ApproximationKahruman-Anderoglu, Sera 2009 December 1900 (has links)
We consider several related problems arising in geometric graphs. In particular,
we investigate the computational complexity and approximability properties of several optimization problems in unit ball graphs and develop algorithms to find exact
and approximate solutions. In addition, we establish complexity-based theoretical
justifications for several greedy heuristics.
Unit ball graphs, which are defined in the three dimensional Euclidian space, have
several application areas such as computational geometry, facility location and, particularly, wireless communication networks. Efficient operation of wireless networks
involves several decision problems that can be reduced to well known optimization
problems in graph theory. For instance, the notion of a \virtual backbone" in a wire-
less network is strongly related to a minimum connected dominating set in its graph
theoretic representation.
Motivated by the vastness of application areas, we study several problems including maximum independent set, minimum vertex coloring, minimum clique partition,
max-cut and min-bisection. Although these problems have been widely studied in
the context of unit disk graphs, which are the two dimensional version of unit ball
graphs, there is no established result on the complexity and approximation status
for some of them in unit ball graphs. Furthermore, unit ball graphs can provide a
better representation of real networks since the nodes are deployed in the three dimensional space. We prove complexity results and propose solution procedures for
several problems using geometrical properties of these graphs.
We outline a matching-based branch and bound solution procedure for the maximum k-clique problem in unit disk graphs and demonstrate its effectiveness through
computational tests. We propose using minimum bottleneck connected dominating
set problem in order to determine the optimal transmission range of a wireless network that will ensure a certain size of "virtual backbone". We prove that this problem
is NP-hard in general graphs but solvable in polynomial time in unit disk and unit
ball graphs.
We also demonstrate work on theoretical foundations for simple greedy heuristics.
Particularly, similar to the notion of "best" approximation algorithms with respect to
their approximation ratios, we prove that several simple greedy heuristics are "best"
in the sense that it is NP-hard to recognize the gap between the greedy solution
and the optimal solution. We show results for several well known problems such as
maximum clique, maximum independent set, minimum vertex coloring and discuss
extensions of these results to a more general class of problems.
In addition, we propose a "worst-out" heuristic based on edge contractions for
the max-cut problem and provide analytical and experimental comparisons with a
well known "best-in" approach and its modified versions.
|
234 |
Modeling And Analysis Of The Facility Layout ProblemKirkizoglu, Zeynep 01 July 2006 (has links) (PDF)
The facilities layout problem, which is an integral part of facilities design, aims to
spatially locate the production units within a facility subject to some design criteria
and area limitations, with one or multiple objectives. In this study, the layout
problem is reviewed in detail, with an emphasis on the dynamic environment it
operates in. Despite the fact that layouts within the context of changing
manufacturing requirements represent the problem better, the single period block
layout problem is observed to have remained worth analyzing.
In this thesis, a hybrid model that combines the strong aspects of the available
models in the literature is constructed for the single period block layout problem.
The LP relaxation of this model and the effect of adding valid inequalities to the
model are studied. A rounding heuristic based on the LP relaxation of the problem is
proposed and computational experimentation is made. Also, an evolutionary
algorithm scheme that uses the sequence pair representation is proposed. Three
mutation operators are developed to be used in this scheme. Preliminary test are
made for implementations of these operators and results are given.
|
235 |
A Case Study: Improvement Of Component Placement Sequence Of A Turret Style Smt MachineCengel, Savas Mehmet 01 January 2007 (has links) (PDF)
This study aims to improve component placement sequencing of a number of PCBs produced on a turret style SMT machine. After modeling the problem and having found that an optimal solution to the real PCB problem is hard to be achieved because of the concurrent behavior of the machine and the PCB design parameters, two heuristics are developed by oversimplifying the problem down to TSP. Performance of
the heuristics and the lower bounds is evaluated by comparing the results with the optimal solution for two sets of randomly generated PCBs. The heuristic solutions are also compared with the lower bounds and the current implementation for the real PCBs. It is found out that the heuristics improve the current efficiency figures of the company.
|
236 |
A Genetic Algorithm For Tsp With Backhauls Based On Conventional HeuristicsOnder, Ilter 01 September 2007 (has links) (PDF)
A genetic algorithm using conventional heuristics as operators is considered in this study for the traveling salesman problem with backhauls (TSPB). Properties of a crossover operator (Nearest Neighbor Crossover, NNX) based on the nearest neighbor heuristic and the idea of using more than two parents are investigated in a series of experiments. Different parent selection and replacement strategies and generation of multiple children are tried as well. Conventional improvement heuristics are also used as mutation operators. It has been observed that 2-edge exchange and node insertion heuristics work well with NNX using only two parents. The best settings among different alternatives experimented are applied on traveling salesman problem with backhauls (TSPB). TSPB is a problem in which there are two groups of customers. The aim is to minimize the distance traveled visiting all the cities, where the second group can be visited only after all cities in the first group are already visited. The approach we propose shows very good performance on randomly generated TSPB instances.
|
237 |
A Three-level Hierarchical Location-allocation Model For Regional Organization Of Perinatal CareKarakaya, Sakir 01 February 2008 (has links) (PDF)
While the concept of regional organization (regionalization) of perinatal care aimed at reducing perinatal mortality has remained at the agenda of developed countries since 1970&rsquo / s, Turkey is one of the countries that does not have such a system yet. In this study, a three-level hierarchical location-allocation model is developed for the regionalization of perinatal care in an attempt to have a better distribution of maternal and perinatal health care services in Turkey. Since the mathematical model developed is difficult to solve in a reasonable time, we propose three heuristic approaches: top-down, modified top-down and Lagrangean relaxation based heuristics. These heuristics are computationally tested on a set of problem instances for networks ranging from 10 to 737 vertices. A significant result is that Lagrangean relaxation based heuristic outperforms the other two heuristics in terms of solution quality. In most of the test problems, the modified top-down heuristic outperforms the top-down heuristic in terms of solution quality. Using the proposed approaches, we solve a real life problem corresponding to the Eastern and South Eastern Anatolian Regions (the East Region) of Turkey.
|
238 |
The Order-picking Problem In Parallel-aisle WarehousesCelik, Melih 01 June 2009 (has links) (PDF)
Order-picking operations constitute the costliest activities in a warehouse. The order-picking problem (OPP) aims to determine the route of the picker(s) in such a way that the total order-picking time, hence the order-picking costs are minimized. In this study, a warehouse that consists of parallel pick aisles is assumed, and various versions of the OPP are considered. Although the single-picker version of the problem has been well studied in the literature, the multiple-picker version has not received much attention in terms of algorithmic approaches. The literature also does not take into account the time taken by the number of turns during the picking route. In this thesis, a detailed discussion is made regarding the computational complexity of the OPP with a single picker. A heuristic procedure, which makes use of the exact algorithm for the OPP with no middle aisles, is proposed for the single-picker OPP with middle aisles, and computational results on randomly generated problems are given. Additionally, an evolutionary algorithm that makes use of the cluster-first, route-second and route-first, cluster-second heuristics for the VRP is provided. The parameters of the algorithm are determined based on preliminary runs and the algorithm is also tested on randomly generated problems, with different weights given to the cluster-first, route-second and route-first, cluster-second approaches. Lastly, a polynomial time algorithm is proposed for the problem of minimizing the number of turns in a parallel-aisle warehouse.
|
239 |
A Rescheduling Problem With Controllable Processing Times:trade-off Between Number Of Disrupted Jobs And ReschedulingcostsCincioglu, Derya 01 December 2011 (has links) (PDF)
In this thesis, we consider a rescheduling problem on non-identical parallel machines with controllable processing times. A period of unavailability occurs on one of the machines due
to a machine failure, material shortage or broken tool. These disruptions may cause the original schedule to become inecient and sometimes infeasible. In order to generate a new and
feasible schedule, we are dealing with two conflicting measures called the eciency and stability measures simultaneously. The eciency measure evaluates the satisfaction of a desired objective function value and the stability measure evaluates the amount of change between
the schedule before and after the disruption. In this study, we measure stability by the number of disrupted jobs. In this thesis, the job is referred as a disrupted job if it completes processing after its planned completion time in the original schedule. The eciency is measured by the additional manufacturing cost of jobs. Decreasing number of disrupted jobs requires compressing the processing time of a job which cause an increase in its additional manufacturing cost. For that reason we cannot minimize these objectives at the same time. In order to handle this, we developed a mixed integer programming model for the considered problem by applying the epsilon-constraint approach. This approach makes focusing on the single objective possible to get efficient solutions. Therefore, we studied the problem of minimizing additional
manufacturing cost subject to a limit on the number of disrupted jobs. We also considered a convex compression cost function for each job and solved a cost minimization problem by applying conic quadratic reformulation for the model. The convexity of cost functions is a major source of diculty in finding optimal integer solutions in this problem, but applying
strengthened conic reformulation has eliminated this diculty. In addition, we prepare an improvement search algorithm in order to find good solution in reasonable CPU times. We use our heuristic procedure on optimality properties we showed for a single machine subproblem. We made computational experiments on small and medium scale test problems. Afterwards, we compare the performance of the improvement search algorithm and mathematical model for their solution quality and durations.
|
240 |
Integer programming based searchHewitt, Michael R. 21 August 2009 (has links)
When integer programming (IP) models are used in operational situations there is a need to consider the tradeoff between the conflicting goals of solution quality and solution time, since for many problems solving realistic-size instances to a tight tolerance is still beyond the capability of state-of-the-art solvers. However, by appropriately defining small instances, good primal solutions frequently can be found quickly. We explore this approach in this thesis by studying the design of algorithms that produce solutions to an integer program by solving restrictions of the problem via integer programming technology. We refer to this type of algorithm as IP-based search and present algorithms for network design problems of both real-world and academic interest. Along with algorithms that exploit the structure of the problem studied we also present a general integer programming algorithm that uses column generation to choose the restrictions to solve.
|
Page generated in 0.0683 seconds