Lot-sizing and scheduling in flat-panel display manufacturing process

In this paper, we consider a lot-sizing and scheduling problem arising in the real-world flat-panel display industry. This problem is formulated as a variant of the discrete lot-sizing and scheduling problem with a sequence-dependent setup. After describing the characteristics of the problem and analyzing its computational complexity, we propose an extended formulation based on a network structure. Even though the problem is NP-hard in general, we show that there exist special cases solvable in polynomial time. For the general cases, we demonstrate the tightness of the extended formulation by means of both polyhedral analysis and computational experiments with artificially generated data and real-world industry data. We also propose a relax-and-fix heuristic algorithm based on the extended formulation, which has been deployed in practice, with the corresponding computational results.     

Two-level network design with intermediate facilities: An application to electrical distribution systems

We consider the two-level network design problem with intermediate facilities. This problem consists of designing a minimum cost network respecting some requirements, usually described in terms of the network topology or in terms of a desired flow of commodities between source and destination vertices. Each selected link must receive one of two types of edge facilities and the connection of different edge facilities requires a costly and capacitated vertex facility. We propose a hybrid decomposition approach which heuristically obtains tentative solutions for the vertex facilities number and location and use these solutions to limit the computational burden of a branch-and-cut algorithm. We test our method on instances of the power system secondary distribution network design problem. The results show that the method is efficient both in terms of solution quality and computational times.     

Approaches to real world two-dimensional cutting problems

We consider a real world generalization of the 2-Dimensional Guillotine Cutting Stock Problem arising in the wooden board cutting industry. A set of rectangular items has to be cut from rectangular stock boards, available in multiple formats. In addition to the classical objective of trim loss minimization, the problem also asks for the maximization of the cutting equipment productivity, which can be obtained by cutting identical boards in parallel. We present several heuristic algorithms for the problem, explicitly considering the optimization of both objectives. The proposed methods, including fast heuristic algorithms, Integer Linear Programming models and a truncated Branch and Price algorithm, have increasing complexity and require increasing computational effort. Extensive computational experiments on a set of realistic instances from the industry show that high productivity of the cutting equipment can be obtained with a minimal increase in the total area of used boards. The experiments also show that the proposed algorithms perform extremely well when compared with four commercial software tools available for the solution of the problem.     

A complexity dichotomy and a new boundary class for the dominating set problem

We study the computational complexity of the dominating set problem for hereditary graph classes, i.e., classes of simple unlabeled graphs closed under deletion of vertices. Every hereditary class can be defined by a set of its forbidden induced subgraphs. There are numerous open cases for the complexity of the problem even for hereditary classes with small forbidden structures. We completely determine the complexity of the problem for classes defined by forbidding a five-vertex path and any set of fragments with at most five vertices. Additionally, we also prove polynomial-time solvability of the problem for some two classes of a similar type. The notion of a boundary class is a helpful tool for analyzing the computational complexity of graph problems in the family of hereditary classes. Three boundary classes were known for the dominating set problem prior to this paper. We present a new boundary class for it.     

The supplier selection problem with quantity discounts and truckload shipping

To minimize procurement expenditures both purchasing and transportation costs need to be considered. We study a procurement setting in which a company needs to purchase a number of products from a set of suppliers to satisfy customer demand. The suppliers offer total quantity discounts and transportation costs are based on truckload shipping rates. The goal is to select a set of suppliers so as to satisfy product demand at minimal total costs. The resulting optimization problem is strongly NP-hard. We develop integer programming based heuristics to solve the problem. Extensive computational experiments demonstrate the efficacy of the proposed heuristics and provide insight into the impact of instance characteristics on effective procurement strategies.     

A Greedy Randomized Adaptive Search Procedure for the Feedback Vertex Set Problem

A Greedy Randomized Adaptive Search Procedure (GRASP) is a randomized heuristic that has produced high quality solutions for a wide range of combinatorial optimization problems. The NP-complete Feedback Vertex Set (FVS) Problem is to find the minimum number of vertices that need to be removed from a directed graph so that the resulting graph has no directed cycle. The FVS problem has found applications in many fields, including VLSI design, program verification, and statistical inference. In this paper, we develop a GRASP for the FVS problem. We describe GRASP construction mechanisms and local search, as well as some efficient problem reduction techniques. We report computational experience on a set of test problems using three variants of GRASP.     

Coordinating pricing and production decisions for multiple products

We consider a dynamic problem of joint pricing and production decisions for a profit-maximizing firm that produces multiple products. We model the problem as a mixed integer nonlinear program, incorporating capacity constraints, setup costs, and dynamic demand. We assume demand functions to be convex, continuous, differentiable, and strictly decreasing in price. We present a solution approach which is more general than previous approaches that require the assumption of a specific demand function. Using real-world data from a manufacturer, we study problem instances for different demand scenarios and capacities and solve for optimal prices and production plans. We present analytical results that provide managerial insights on how the optimal prices change for different production plans and capacities. We extend some of the earlier works that consider single product problems to the case of multiple products and time variant production capacities. We also benchmark performance of proposed algorithm with a commercial solver and show that it outperforms the solver both in terms of solution quality and computational times.     

Dynamic Programming and Hill-Climbing Techniques for Constrained Two-Dimensional Cutting Stock Problems

In this paper we propose an algorithm for the constrained two-dimensional cutting stock problem (TDC) in which a single stock sheet has to be cut into a set of small pieces, while maximizing the value of the pieces cut. The TDC problem is NP-hard in the strong sense and finds many practical applications in the cutting and packing area. The proposed algorithm is a hybrid approach in which a depth-first search using hill-climbing strategies and dynamic programming techniques are combined. The algorithm starts with an initial (feasible) lower bound computed by solving a series of single bounded knapsack problems. In order to enhance the first-level lower bound, we introduce an incremental procedure which is used within a top-down branch-and-bound procedure. We also propose some hill-climbing strategies in order to produce a good trade-off between the computational time and the solution quality. Extensive computational testing on problem instances from the literature shows the effectiveness of the proposed approach. The obtained results are compared to the results published by Alvarez-Valdés et al. (2002).     

A Framework for Facilitating Sourcing and Allocation Decisions for Make‐to‐Order Items

This paper provides a fundamental building block to facilitate sourcing and allocation decisions for make‐to‐order items. We specifically address the buyer's vendor selection problem for make‐to‐order items where the goal is to minimize sourcing and purchasing costs in the presence of fixed costs, shared capacity constraints, and volume‐based discounts for bundles of items. The potential suppliers for make‐to‐order items provide quotes in the form of single sealed bids or participate in a dynamic auction involving open bids. A solution to our problem can be used to determine winning bids amongst the single sealed bids or winners at each stage of a dynamic auction. Due to the computational complexity of this problem, we develop a heuristic procedure based on Lagrangian relaxation technique to solve the problem. The computational results show that the procedure is effective under a variety of scenarios. The average gap across 2,250 problem instances is 4.65%.     

Vendor Selection with Bundling*

Product bundling has become increasingly prevalent not only in consumer goods but also in the industrial sector. We study a purchasing problem in which a buyer must obtain necessary numbers of various stock items from a variety of vendors who charge different prices, have limited capacities and different levels of quality, and offer bundled products at discounted prices. We examine relationships among different bundling scenarios and show that the most general scenario is one in which free items are given to the buyer when sufficient quantities are purchased. We develop a mixed integer linear program that finds the purchasing strategy for the buyer that minimizes the total purchase cost. We present computational results which indicate that the problem is very tractable to solve optimally on a personal computer with standard optimization software. Finally, three extensions of the model are discussed.     

Data aggregation for <Emphasis Type="Italic">p</Emphasis>-median problems

In this paper, we use a pseudo-Boolean formulation of the p-median problem and using data aggregation, provide a compact representation of p-median problem instances. We provide computational results to demonstrate this compactification in benchmark instances. We then use our representation to explain why some p-median problem instances are more difficult to solve to optimality than other instances of the same size. We also derive a preprocessing rule based on our formulation, and describe equivalent p-median problem instances, which are identical sized instances which are guaranteed to have identical optimal solutions.     

The two-level lot-sizing problem with outbound shipment

We consider the two-level lot-sizing problem for the integrated replenishment and dispatch plan of a third-party logistics company and distribution center. Each outbound shipment for a dispatch involves cargos that incur a stepwise transportation cost. To increase the effect of shipment consolidation, the distribution center allows backlogging. This problem has the characteristics of capacitated and uncapacitated lot-sizing. A forward dynamic program is applied to exploit the beneficial characteristic of the uncapacitated problem. The forward dynamic program is implemented using Zangwill partitions to decrease the number of computational parameters with legitimacy checks to guarantee optimality. Employing these techniques, we provide an O(T⁴) algorithm, which serves as an improvement on the O(T⁶) algorithm of previous research. Moreover, computational results from actual implementations show that our algorithm is significantly faster than that of prior research.     

Multi-agent scheduling on a single machine with a fixed number of competing agents to minimize the weighted sum of number of tardy jobs and makespans

We study the multi-agent scheduling on a single machine with a fixed number of competing agents, in which, the objective function of each agent is either the number of tardy jobs or the makespan, and the goal of the problem is to minimize the weighted sum of agents’ objective functions. In the literature, the computational complexity of this problem was posed as open. By using enumerating, dynamic programming, and schedule-configuration, we show in this paper that the problem is solvable in polynomial time.     

Modeling the problem of locating collection areas for urban waste management. An application to the metropolitan area of Barcelona

Reverse logistics problems arising in municipal waste management are both wide-ranging and varied. The usual collection system in UE countries is composed of two phases. First, citizens leave their refuse at special collection areas where different types of waste (glass, paper, plastic, organic material) are stored in special refuse bins. Subsequently, each type of waste is collected separately and moved to its final destination (a recycling plant or refuse dump). The present study focuses on the problem of locating these collection areas. We establish the relationship between the problem, the set covering problem and the MAX-SAT problem and then go on to develop a genetic algorithm and a GRASP heuristic to, respectively, solve each formulation. Finally, the quality of the algorithms is tested in a computational experience with real instances from the metropolitan area of Barcelona, as well as a reduced set of set covering instances from the literature.     

On greedy and strategic evaders in sequential interdiction settings with incomplete information

We consider a class of sequential network interdiction problem settings where the interdictor has incomplete initial information about the network while the evader has complete knowledge of the network including its structure and arc costs. In each decision epoch, the interdictor can block (for the duration of the epoch) at most k arcs known to him/her. By observing the evader’s actions, the interdictor learns about the network structure and costs and thus, can adjust his/her actions in subsequent decision epochs. It is known from the literature that if the evader is greedy (i.e., the shortest available path is used in each decision epochs), then under some assumptions the greedy interdiction policies that block k-most vital arcs in each epoch are efficient and have a finite regret. In this paper, we consider the evader’s perspective and explore deterministic “strategic” evasion policies under the assumption that the interdictor is greedy. We first study the theoretical computational complexity of the evader’s problem. Then we derive basic constructive properties of optimal evasion policies for two decision epochs when the interdictor has no initial information about the network structure. These properties are then exploited for the design of a heuristic algorithm for a strategic evader in a general setting with an arbitrary time horizon and any initial information available to the interdictor. Our computational experiments demonstrate that the proposed heuristic outperforms the greedy evasion policy on several classes of synthetic network instances under either perfect or noisy information feedback. Finally, some interesting insights from our theoretical and computational results conclude the paper.     

An hierarchal location—allocation problem

We consider a 2-hierarchal location-allocation problem when p₁ health centers and p₂ hospitals are to be located among n potential locations so as to minimize the total weighted travel distance. We consider the possibility of the referral of θ (0 ≤ θ ≤ 1) proportion of patients from a health center to a hospital. For a graph with certain properties, we extend the notion of a median of a graph to an hierarchal median set. We show how the 2-hierarchal location-allocation problem may be solved as a 2-hierarchal vertex median set problem. We formulate the problem as a mathematical programming problem, suggest five heuristic procedures to solve the problem and report some computational experience. Although we consider the hierarchal location-allocation problem with reference to a health care delivery system, the results of this paper have wide application.     

Optimal Selection Strategy for the Group Interview Problem

We propose a more generalized version of the secretary problem, called the group interview problem, in which each group contains several alternatives and each group of alternatives is presented and evaluated sequentially over time. Using the assumptions corresponding to the classical secretary problem, we derive an optimal selection strategy which maximizes the probability of winning or selecting the single best choice in a given sequence of groups. We further address the problem of choosing at the beginning of the evaluation process a sequence of groups to maximize the winning probability. Because of formidable computational requirements to obtain an optimal solution to this sequencing problem, we then develop a heuristic algorithm based on several properties inherent in an optimal selection strategy. The heuristic procedure is evaluated experimentally using Monte Carlo simulation and is shown to be effective in obtaining near-optimal (within 5 percent) solutions.     

Lot sizing with storage losses under demand uncertainty

We address a variant of the single item lot sizing problem affected by proportional storage (or inventory) losses and uncertainty in the product demand. The problem has applications in, among others, the energy sector, where storage losses (or storage deteriorations) are often unavoidable and, due to the need for planning ahead, the demands can be largely uncertain. We first propose a two-stage robust optimization approach with second-stage storage variables, showing how the arising robust problem can be solved as an instance of the deterministic one. We then consider a two-stage approach where not only the storage but also the production variables are determined in the second stage. After showing that, in the general case, solutions to this problem can suffer from acausality (or anticipativity), we introduce a flexible affine rule approach which, albeit restricting the solution set, allows for causal production plans. A hybrid robust-stochastic approach where the objective function is optimized in expectation, as opposed to in the worst-case, while retaining robust optimization guarantees of feasibility in the worst-case, is also discussed. We conclude with an application to heat production, in the context of which we compare the different approaches via computational experiments on real-world data.     

A Heuristic Algorithm for the Capacitated Multiple Supplier Inventory Grouping Problem

This paper presents and solves a model for the multiple supplier inventory grouping problem, which involves the minimization of logistics costs for a firm that has multiple suppliers with capacity limitations. The costs included in the model are purchasing, transportation, ordering, and inventory holding, while the firm's objective is to determine the optimal flows and groups of commodities from each supplier. We present an algorithm, which combines subgradient optimization and a primal heuristic, to quickly solve the multiple supplier inventory grouping problem. Our algorithm is tested extensively on problems of various sizes and structures, and its performance is compared to that of OSL, a state-of-the-art integer programming code. The computational results indicate that our approach is extremely efficient for solving the multiple supplier inventory grouping problem.     

Solution Procedures for the Lot-Streaming Problem

Lot streaming is the process of splitting a job into sublots so its operations can be overlapped and its progress accelerated. We present a computationally efficient procedure for solving the m-machine, two-sublot problem, and we discuss the bottleneck insights that emerge from the analysis. We also examine heuristic approaches for more than two sublots and discuss computational results for these procedures.