An FPTAS for scheduling with resource constraints

We study a basic scheduling problem with resource constraints: A number of jobs need to be scheduled on two parallel identical machines with the objective of minimizing the makespan, subject to the constraint that jobs may require a unit of one of the given renewable resources during their execution. For this NP-hard problem, we develop a fully polynomial-time approximation scheme (FPTAS). Our FPTAS makes a novel use of existing algorithms for the subset-sum problem and the open shop scheduling problem.     

Utilizing the information theory of entropy to solve an off-line inspection problem

This study presents an off-line inspection problem for a batch produced from a process subject to random failures and exhibiting manufacturing variations. The objective of this paper is to develop an inspection policy in which units should be inspected in a particular order to find the transition unit in the batch under a required confidence level. This study develops an algorithm to compute the expected number of inspections. This approach uses the information theory of entropy to select an un-inspected unit to be inspected, and effectively minimizes the uncertainty of the transition unit in the production batch. A numerical example illustrates the proposed off-line inspection policy, and the effects of model parameters on the expected inspection number are investigated. The numerical example in this study indicates that full inspection is required when the required confidence level is one or the process has larger manufacturing variations.     

Product sequencing and pricing under cascade browse model

We study the assortment optimization problem under the newly proposed cascade browse model. We propose a constant approximate solution to this problem. As a byproduct, we propose the first fully polynomial-time approximation scheme (FPTAS) for the classic assortment optimization problem subject to one capacity constraint and one cardinality constraint. We also studied a joint pricing and sequencing problem under the above model and develop a constant approximate solution to this problem.     

Exploiting locality: approximating sorting buffers

The sorting buffers problem is motivated by many applications in manufacturing processes and computer science, among them car-painting and file servers architecture. The input is a sequence of items of various types. All the items must be processed, one by one, by a service station. We are given a random-access sorting buffer with a limited capacity. Whenever a new item arrives it may be moved directly to the service station or stored in the buffer. Also, at any time items can be removed from the buffer and assigned to the service station. Our goal is to give the service station a sequence of items with minimum type transitions. We generalize the problem to allow items with different sizes and type transitions with different costs. We give a polynomial-time 9-approximation algorithm for the maximization variant of this problem, which improves the best previously known 20-approximation algorithm.     

The constrained minimum weighted sum of job completion times problem

We consider the problem of minimizing the weighted sum of job completion times on a single machine (subject to certain job weights) with an additional side constraint on the weighted sum of job completion times (with respect to different job weights). This problem is NP-hard, and we provide a polynomial time approximation scheme for this problem. Our method is based on Lagrangian relaxation mixed with carefully guessing the positions of certain jobs in the schedule. An earlier version of this paper appeared in the Proceedings of the 10th International IPCO Conference.     

Improved analysis of an algorithm for the coupled task problem with UET jobs

The coupled task problem is to schedule n jobs, each one consisting of two subtasks with exact delay times between them, on a single machine. We derive a new lower bound for the problem variant with unit execution times and correct a previously published analysis.     

Scheduling three chains on two parallel machines

We consider the problem of scheduling n tasks subject to chain-precedence constraints on two identical machines with the objective of minimizing the makespan. The problem is known to be strongly NP-hard. Here, we prove that it is binary NP-hard even with three chains. Furthermore, we characterize the complexity of this case by presenting a pseudopolynomial time algorithm and a fully polynomial time approximation scheme.     

Strongly polynomial-time approximation for a class of bicriteria problems

Consider the following problem: given a ground set and two minimization objectives of the same type find a subset from a given subset-class that minimizes the first objective subject to a budget constraint on the second objective. Using Megiddo's parametric method we improve an earlier weakly polynomial time algorithm.     

Approximating Global Quadratic Optimization with Convex Quadratic Constraints

We consider the problem of approximating the global maximum of a quadratic program (QP) subject to convex non-homogeneous quadratic constraints. We prove an approximation quality bound that is related to a condition number of the convex feasible set; and it is the currently best for approximating certain problems, such as quadratic optimization over the assignment polytope, according to the best of our knowledge.     

Maximum thick paths in static and dynamic environments

We consider the problem of finding a large number of disjoint paths for unit disks moving amidst static or dynamic obstacles. The problem is motivated by the capacity estimation problem in air traffic management, in which one must determine how many aircraft can safely move through a domain while avoiding each other and avoiding “no-fly zones” and predicted weather hazards. For the static case we give efficient exact algorithms, based on adapting the “continuous uppermost path” paradigm. As a by-product, we establish a continuous analogue of Menger's Theorem.Next we study the dynamic problem in which the obstacles may move, appear and disappear, and otherwise change with time in a known manner; in addition, the disks are required to enter/exit the domain during prescribed time intervals. Deciding the existence of just one path, even for a 0-radius disk, moving with bounded speed is NP-hard, as shown by Canny and Reif [J. Canny, J.H. Reif, New lower bound techniques for robot motion planning problems, in: Proc. 28th Annu. IEEE Sympos. Found. Comput. Sci., 1987, pp. 49–60]. Moreover, we observe that determining the existence of a given number of paths is hard even if the obstacles are static, and only the entry/exit time intervals are specified for the disks. This motivates studying “dual” approximations, compromising on the radius of the disks and on the maximum speed of motion.Our main result is a pseudopolynomial-time dual-approximation algorithm. If K unit disks, each moving with speed at most 1, can be routed through an environment, our algorithm finds (at least) K paths for disks of radius somewhat smaller than 1 moving with speed somewhat larger than 1.     

A Lot-sizing Model for Just-in-time Manufacturing

We consider the problem of determining lot sizes of multiple items that are manufactured by a single capacitated facility. The manufacturing facility may represent a bottleneck processing activity on the shop floor or a storeroom that provides components to the shop floor. Items flow from the facility to a downstream facility, where they are assembled according to a specified mix. Just-in-time (JIT) manufacturing requires a balanced flow of items, in the proper mix, between successive facilities. Our model determines lot sizes of the various items based on available capacity and four attributes of each item: demand rate, holding cost, set-up time and processing time. Holding costs for each item accrue until the appropriate mix of items is available for shipment downstream. We develop a lot-sizing heuristic that minimizes total holding cost per time unit over all items, subject to capacity availability and the required mix of items.     

An approximation algorithm for the pickup and delivery vehicle routing problem on trees

This paper presents an approximation algorithm for a vehicle routing problem on a tree-shaped network with a single depot where there are two types of demands, pickup demand and delivery demand. Customers are located on nodes of the tree, and each customer has a positive demand of pickup and/or delivery.Demands of customers are served by a fleet of identical vehicles with unit capacity. Each vehicle can serve pickup and delivery demands. It is assumed that the demand of a customer is splittable, i.e., it can be served by more than one vehicle. The problem we are concerned with in this paper asks to find a set of tours of the vehicles with minimum total lengths. In each tour, a vehicle begins at the depot with certain amount of goods for delivery, visits a subset of the customers in order to deliver and pick up goods and returns to the depot. At any time during the tour, a vehicle must always satisfy the capacity constraint, i.e., at any time the sum of goods to be delivered and that of goods that have been picked up is not allowed to exceed the vehicle capacity. We propose a 2-approximation algorithm for the problem.     

Reoptimization of minimum and maximum traveling salesman's tours

In this paper, reoptimization versions of the traveling salesman problem (TSP) are addressed. Assume that an optimum solution of an instance is given and the goal is to determine if one can maintain a good solution when the instance is subject to minor modifications. We study the case where nodes are inserted in, or deleted from, the graph. When inserting a node, we show that the reoptimization problem for MinTSP is approximable within ratio 4/3 if the distance matrix is metric. We show that, dealing with metric MaxTSP, a simple heuristic is asymptotically optimum when a constant number of nodes are inserted. In the general case, we propose a 4/5-approximation algorithm for the reoptimization version of MaxTSP.     

An approximation algorithm for square packing

We consider the problem of packing squares into bins which are unit squares, where the goal is to minimize the number of bins used. We present an algorithm for this problem with an absolute worst-case ratio of 2, which is optimal provided P≠NP.     

Two-stage fuzzy production planning expected value model and its approximation method

This work develops a novel two-stage fuzzy optimization method for solving the multi-product multi-period (MPMP) production planning problem, in which the market demands and some of the inventory costs are assumed to be uncertainty and characterized by fuzzy variables with known possibility distributions. Some basic properties about the MPMP production planning problem are discussed. Since the fuzzy market demands and inventory costs usually have infinite supports, the proposed two-stage fuzzy MPMP production planning problem is an infinite-dimensional optimization problem that cannot be solved directly by conventional numerical solution methods. To overcome this difficulty, this paper adopts an approximation method (AM) to turn the original two-stage fuzzy MPMP production planning problem into a finite-dimensional optimization problem. The convergence about the AM is discussed to ensure the solution quality. After that, we design a heuristic algorithm, which combines the AM and simulated annealing (SA) algorithm, to solve the proposed two-stage fuzzy MPMP production planning problem. Finally, one real case study about a furniture manufacturing company is presented to illustrate the effectiveness and feasibility of the proposed modeling idea and designed algorithm.     

Solving certain singly constrained convex optimization problems in production planning

This paper considers the problem of minimizing a special convex function subject to one linear constraint. Based upon a theorem for lower and upper bounds on the Lagrange multiplier a fully polynomial time approximation scheme is proposed. The efficiency of the algorithm is demonstrated by a computational experiment.     

Approximation algorithms for a vehicle routing problem

In this paper we investigate a vehicle routing problem motivated by a real-world application in cooperation with the German Automobile Association (ADAC). The general task is to assign service requests to service units and to plan tours for the units such as to minimize the overall cost. The characteristics of this large-scale problem due to the data volume involve strict real-time requirements. We show that the problem of finding a feasible dispatch for service units starting at their current position and serving at most k requests is NP-complete for each fixed k ≥ 2. We also present a polynomial time (2k − 1)-approximation algorithm, where again k denotes the maximal number of requests served by a single service unit. For the boundary case when k equals the total number |E| of requests (and thus there are no limitations on the tour length), we provide a -approximation. Finally, we extend our approximation results to include linear and quadratic lateness costs.     

Resource augmentation in two-dimensional packing with orthogonal rotations

We consider the problem of packing two-dimensional rectangles into the minimum number of unit squares, when 90^° rotations are allowed. Our main contribution is a polynomial-time algorithm for packing rectangles into at most OPT bins whose sides have length (1+ε), for any positive ε. Additionally, we show near-optimal packing results for a number of related packing problems.     

Approximation results for a min-max location-routing problem

This paper studies a min-max location-routing problem, which aims to determine both the home depots and the tours for a set of vehicles to service all the customers in a given weighted graph, so that the maximum working time of the vehicles is minimized. The min-max objective is motivated by the needs of balancing or fairness in vehicle routing applications. We have proved that unless NP=P, it is impossible for the problem to have an approximation algorithm that achieves an approximation ratio of less than 4/3. Thus, we have developed the first constant ratio approximation algorithm for the problem. Moreover, we have developed new approximation algorithms for several variants, which improve the existing best approximation ratios in the previous literature.     

Transformation of Some Mixed Approximation Problems by Optimization Methods

The present paper considers the approximation of a function in the L 2 -norm by functions in a Haar space subject to a constraint set defined by the sup norm. This problem is examined from developments of the Karush-Kuhn-Tucker theorem for semi-infinite programming as well as from the multiobjective optimization approach. An extreme feasible set is characterized with the help of a version of the Chebyshev alternation theorem.