While in classical scheduling theory the locations of machines are assumed to be fixed we will show how to tackle location and scheduling problems simultaneously. Obviously, this integrated approach enhances the modeling power of scheduling for various real-life problems. In this paper, we present in an exemplary way theory and a solution algorithm for a specific type of a scheduling and a rather general, planar location problem, respectively. More general results and a report on numerical tests will be presented in a subsequent paper.
Given a finite set of points in the plane and a forbidden region R, we want to find a point X not an element of int(R), such that the weighted sum to all given points is minimized. This location problem is a variant of the well-known Weber Problem, where we measure the distance by polyhedral gauges and allow each of the weights to be positive or negative. The unit ball of a polyhedral gauge may be any convex polyhedron containing the origin. This large class of distance functions allows very general (practical) settings - such as asymmetry - to be modeled. Each given point is allowed to have its own gauge and the forbidden region R enables us to include negative information in the model. Additionally the use of negative and positive weights allows to include the level of attraction or dislikeness of a new facility. Polynomial algorithms and structural properties for this global optimization problem (d.c. objective function and a non-convex feasible set) based on combinatorial and geometrical methods are presented.
Facility location problems in the plane play an important role in mathematical programming. When looking for new locations in modeling real-word problems, we are often confronted with forbidden regions, that are not feasible for the placement of new locations. Furthermore these forbidden regions may habe complicated shapes. It may be more useful or even necessary to use approcimations of such forbidden regions when trying to solve location problems. In this paper we develop error bounds for the approximative solution of restricted planar location problems using the so called sandwich algorithm. The number of approximation steps required to achieve a specified error bound is analyzed. As examples of these approximation schemes, we discuss round norms and polyhedral norms. Also computational tests are included.
In this paper we deal with single facility location problems in a general normed space where the existing facilities are represented by sets. The criterion to be satis ed by the service facility is the minimization of an increasing function of the distances from the service to the closest point ofeach demand set. We obtain a geometrical characterization of the set of optimal solutions for this problem. Two remarkable cases - the classical Weber problem and the minmax problem with demand sets - are studied as particular instances of our problem. Finally, for the planar polyhedral case we give an algorithmic description of the solution set of the considered problems.
In this paper we deal with the determination of the whole set of Pareto-solutions of location problems with respect to Q general criteria.These criteria include median, center or cent-dian objective functions as particular instances.The paper characterizes the set of Pareto-solutions of a these multicriteria problems. An efficient algorithm for the planar case is developed and its complexity is established. Extensions to higher dimensions as well as to the non-convexcase are also considered.The proposed approach is more general than the previously published approaches to multi-criteria location problems and includes almost all of them as particular instances.
In this paper we deal with the determination of the whole set of Pareto-solutions of location problems with respect to Q general criteria. These criteria include as particular instances median, center or cent-dian objective functions. The paper characterizes the set of Pareto-solutions of all these multicriteria problems. An efficient algorithm for the planar case is developed and its complexity is established. the proposed approach is more general than the previously published approaches to multicriteria location problems and includes almost all of them as particular instances.
In continous location problems we are given a set of existing facilities and we are looking for the location of one or several new facilities. In the classical approaches weights are assigned to existing facilities expressing the importance of the new facilities for the existing ones. In this paper, we consider a pointwise defined objective function where the weights are assigned to the existing facilities depending on the location of the new facility. This approach is shown to be a generalization of the median, center and centdian objective functions. In addition, this approach allows to formulate completely new location models. Efficient algorithms as well as structure results for this algebraic approach for location problems are presented. Extensions to the multifacility and restricted case are also considered.