ABSTRACT PERFORMANCE MEASUREMENT IN MULTI OBJECTIVE COMBINATORIAL OPTIMIZATION Bozkurt, Bilge M.Sc., Department of Industrial Engineering Supervisor: Prof. Dr. Murat K&ouml / ksalan September 2007, 96 pages In this study we address the problem of measuring the quality of different sets of nondominated solutions obtained by different approaches in multi objective combinatorial optimization (MOCO). We propose a new measure that quantitatively compares the sets of nondominated solutions, without needing an efficient frontier. We develop the measure for bi-criteria and more than two criteria cases separately. Rather than considering only the supported solutions in the evaluation, the measure captures both supported and unsupported solutions through utilizing weighted Tchebycheff function characteristics. We also adapt this method for determining the neighborhood relations on the weight space for both bi-criteria and more than two criteria cases. We check the consistency of the neighborhood assumption on the objective space with the neighborhood relations on the weight space by this measure and obtain highly good results. Keywords: Multi objective combinatorial optimization, performance measurement

In this study, value of quality information and the eects of centralization are investigated for a reverse supply chain consisting of a remanufacturer and a collector. Used products are collected and inspected to classify them into quality groups, then they are remanufactured to meet the demand of remanufactured products. The supply of collected products and demand of remanufactured products are both price-sensitive. The uncertain quality of the collected products is revealed by an inspection process. Two quality classes are considered, and the cost of remanufacturing depends on the quality class. The main decisions are on acquisition fee for the returns, the selling price for remanufactured products, and the transfer prices of inspected products between the collector and the remanufacturer. For this environment, centralized and decentralized settings are considered and dierent models that dier in availability of quality information when the pricing decisions are made are built. We explore the value of advance quality information and eects of centralization on the optimal prices and profits via a computational study.

This study deals with chocolate production line scheduling. The particular production line allows producing multiple items at the same time. Another distinguishing property affecting the planning methodology is that an item can have different production capacities when produced in different product combinations which are called production patterns in this study. Planning is done on a 12 weeks rolling horizon. There are 21 products and 103 production patterns covering all the production possibilities. The subject of the study is to construct an algorithm that gives 12 weeks&rsquo / production values of each product and to construct the shift based scheduling of the first week of the planning horizon. The first part is Master Production Scheduling (MPS) and the objective is minimizing the shortage and overage costs. A mathematical modeling approach is used to solve the MPS problem. The second part is the scheduling part which aims to arrange the production patterns obtained from the MPS module within the shifts for the first week of the planning horizon considering the setup times. The MPS module is a large integer programming model. The challenge is finding a reasonable lower bound whenever possible. If it is not possible, finding a reasonable upper bound and seeking solutions better than that is the main approach. The scheduling part, after solving MPS, becomes a TSP and the setup times are sequence independent. In this part, the challenge is solving TSP with an appropriate objective function.

In project scheduling, the activity durations can often be reduced by dedicating additional resources. Time/Cost Trade-off Problem considers the compromise between the total cost and project duration. The discrete version of the problem assumes a number of time/cost pairs, so called modes, and selects a mode for each activity. In this thesis we consider the Discrete Time/Cost Trade-off Problem. We first study the Deadline Problem, i.e., the problem of minimizing total cost subject to a deadline on project duration. To solve the Deadline Problem, we propose several optimization and approximation algorithms that are based on optimal Linear Programming Relaxation solutions. We then analyze the problem of generating all efficient solutions, and propose an approach that uses the successive solutions of the Deadline Problem. Our computational results on large-sized problem instances have revealed the satisfactory behavior of our algorithms.

In this thesis, attitude control of small satellites with dissimilar actuator is studied and the effects of control allocation methods on maneuvering are examined in detail. Magnetorquers and reaction wheels are considered as the actuators of a modeled remote sensing -nadir pointing- small satellite. Matlab&reg / Simulink simulation models are developed to model the satellite dynamics and the actuators on the satellite. The simulations are based on conceptual RASAT satellite, and, for verification, orbit data is taken from BILSAT satellite that is operated by TUBITAK Space Research Institute. Basic satellite control modes are developed and tested to obtain nominal control. Actuator failures are analyzed for different possible cases. A control allocation method called Blended Inverse that was originally proposed for steering CMGs is applied to select the actuators to avoid actuator saturation and singularity transition. The performance of traditional pseudo inverse method is compared with the blended inverse method and simulation results are given and discussed. The superiority of blended inverse over pseudo inverse is demonstrated.

In Traveling Salesman Problem (TSP) with profits, a profit is associated with each city and the requirement to visit all cities is removed. The purpose is to simultaneously minimize cost (excluding as many cities as possible) and maximize profit (including as many cities as possible). Although the reduced single-objective case of the problem has been well-studied, the true biobjective problem has been studied only by a few researchers. In this paper we study the true biobjective problem using the Multiobjective Genetic Algorithm NSGA II and the Lin-Kernighan Heuristic. We propose several improvements for NSGA II in solving the problem. Based on these improvements, we provide computational results of the approximated Pareto-optimal front for a set of practically large size TSP instances. Finally, we provide a framework and its computational results for a post-optimality analysis to guide the decision maker, using the data mining software Clementine.

Increased product proliferation and global competition are forcing companies within the supply chain to adopt new strategies. Postponement is an effective strategy that allows companies to be agile and cost effective in dealing with the dynamics of global supply chains. Postponement centres around delaying activities in the supply chain until real information about the market is available, which reduces the complexity and uncertainty of dealing with a proliferation of products. A two-echelon divergent supply chain entailing a central production facility and N retailers facing stochastic demand is studied within the inventory-distribution system. A periodic review order-up-to strategy is incorporated at all echelons. Unique to the study, five different systems are created and the effectiveness of several postponement strategies (form and transshipment) under various operational settings are compared. The importance of postponement under an integrated supply chain context and its contribution to various sector implementations are also discussed. Simulation is used to analyze the performance of the systems especially with respect to cost, order lead time and the effectiveness of transshipment policies. The study is unique in determining factors that favour one system implementation over another and distinguishing sector requirements that support postponement. In the study, postponement is found to be an effective strategy in dealing with managing item variety, demand uncertainty and differences in review periods in the two echelon supply chain for different experimental settings.

Inventory management policies of two independent dealers in a service parts system with transshipment is studied in this thesis. Dealers can collaborate by pooling inventory or service. Revenue is shared in transshipment, can sometimes be contrary to profit maximization of one of the parties albeit sum of profits is increased. To assess the benefits of inventory pooling under equilibrium strategies, and the effect of competition on profits, a Markov Decision Process is formulated. A simpler variant of the optimal four-index threshold policy is used to characterize the production, service and transshipment related inventory decisions. A game theoretical approach as well as notions from policy iteration is taken to find the best response policy and equilibrium policies of the dealers. Numerical study is conducted to investigate the effect of cost, revenue and demand parameters, as well as dealer asymmetricities on benefit of pooling, service levels and transshipment flows. Analysis shows that commission schemes fairly allocating transshipment value to the players, high customer traffic intensities, and low transshipment costs are most suited environments for pooling. System centralization is beneficial when the inventory holding costs are high, transshipment costs are low, customer traffic intensities are high or the commission structure is distracting a party. Competition, within the experimental settings, dampens about 45% of the benefits of pooling.

In this thesis, we study the dynamic facility location problem with mobile customers considering the permanent facilities. Our general aim is to locate facilities considering the movements of customers in time. The problem is studied for three objectives: P-median, P-center and MINMAX P-median. We show that dynamic facility location problem is a large instance of a static facility location problem for P-median and P-center objectives. In the problem, we represent the movements of each customer in time with a time series. Using clustering approaches, we develop a heuristic approach for the problem with P-median objective. K-means algorithm is used as a clustering algorithm and dynamic time warping is used in order to define similarities between the customer time series. Solution method is tested on several experimental settings. We obtain results, which differ at most 2% from the optimal, in small computation times. Generally, in the literature, MINMAX P-median is solved with a heuristic depending on scenarios planning (see Serra and Marianov, 1998). The heuristic finds an initial solution according to scenarios, later the initial solution is tried to be improved. We provide a bounding procedure on the solution of the problem. The bounds can be used by decision maker to judge the solution quality before proceed. The bounding procedure is also analyzed in different experimental settings.

In this study, we present the implementation and experimental analysis of a modeling approach for analyzing tactical level land combat to generate information for weapon and ammunition planning. The discrete-time stochastic model (DSM), which can handle small and moderately large force levels, is based on single shot kill probabilities. Forces are assumed to be heterogeneous on both sides, and both directed and area fire types are modeled by means of combinatorial analysis. DSM considers overkills and can handle noncombat loss and engagement processes, discrete reinforcements, force combinations and divisions. In addition to experimenting with DSM, we estimate attrition rate coefficients used in Lanchester combat models, such that the two models will yield similar figures for force levels throughout the combat.