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.

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.

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.

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.

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.

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.

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.

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.

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.

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.