We consider the NP-hard twin robot scheduling problem, which was introduced by Erdogan et al. (Naval Res Logist (NRL) 61(2):119-130, 2014). Here, two moving robots positioned at the opposite ends of a rail have to per...
详细信息
We consider the NP-hard twin robot scheduling problem, which was introduced by Erdogan et al. (Naval Res Logist (NRL) 61(2):119-130, 2014). Here, two moving robots positioned at the opposite ends of a rail have to perform automated storage and retrieval jobs at given positions along the gantry rail with a non-crossing constraint. The objective is to minimize the makespan. We extend the original problem by considering pickup and delivery times and present exact and approximation algorithms with a performance ratio of approximate to 1.1716 for large instances. Further, we compare the presented algorithms in a comprehensive numerical study.
We consider the problem of placing n points, each one inside its own, prespecified disk, with the objective of maximizing the distance between the closest pair of them. The disks can overlap and have different sizes. ...
详细信息
We consider the problem of placing n points, each one inside its own, prespecified disk, with the objective of maximizing the distance between the closest pair of them. The disks can overlap and have different sizes. The problem is NP-hard and does not admit a PTAS. In the L-infinity metric, we give a 2-approximation algorithm running in O(n root n log(2) n) time. In the L-infinity metric, we give a quadratic time algorithm that gives an 8 /3-approximation in general, and a similar to 2.2393-approximation when all the disks are congruent. (C) 2004 Elsevier Inc. All rights reserved.
We study the problem of finding shortest tours/paths for "lawn mowing" and "milling" problems: Given a region in the plane, and given the shape of a "cutter" (typically, a circle or a squ...
详细信息
We study the problem of finding shortest tours/paths for "lawn mowing" and "milling" problems: Given a region in the plane, and given the shape of a "cutter" (typically, a circle or a square), find a shortest tour/path for the cutter such that every point within the region is covered by the cutter at some position along the tour/path. In the milling version of the problem, the cutter is constrained to stay within the region. The milling problem arises naturally in the area of automatic tool path generation for NC pocket machining. The lawn mowing problem arises in optical inspection, spray painting, and optimal search planning. Both problems are NP-hard in general. We give efficient constant-factor approximation algorithms for both problems. In particular, we give a (3 + epsilon)-approximation algorithm for the lawn mowing problem and a 2.5-approximation algorithm for the milling problem. Furthermore, we give a simple 6/5-approximation algorithm for the TSP problem in simple grid graphs, which leads to an 11/5-approximation algorithm for milling simple rectilinear polygons, (C) 2000 Elsevier Science B.V. All rights reserved.
In this paper we study a variant of the bin packing problem in which the items to be packed are structured as the leaves of a tree. The problem is motivated by document organization and retrieval. We show that the pro...
详细信息
In this paper we study a variant of the bin packing problem in which the items to be packed are structured as the leaves of a tree. The problem is motivated by document organization and retrieval. We show that the problem is NP-hard and we give approximation algorithms for the general case and for the particular case in which all the items have the same size. (C) 2003 Elsevier B.V. All rights reserved.
We consider the problem of time-constrained scheduling of packets in a communication network. Each packet has, in addition to its source and its destination, a release time and a deadline. The goal of an algorithm is ...
详细信息
We consider the problem of time-constrained scheduling of packets in a communication network. Each packet has, in addition to its source and its destination, a release time and a deadline. The goal of an algorithm is to maximize the number of packets that arrive to their destinations by their respective deadlines, given the network constraints. We consider the line network, and a setting where each node has a buffer of size B packets (where B can be finite or infinite), and each edge has capacity Ca parts per thousand yen1. To the best of our knowledge this is the first work to study time-constrained scheduling in a setting when buffers can be of limited size. We give approximation algorithms that achieve expected approximation ratio of O(max {log (au) n-log (au) B,1}+max {log I-au a'log pound (au) C,1}), where n is the length of the line, and I pound is the maximum slack a message can have (the slack is the number of time steps a message can be idle and still arrive within its deadline). A special case of our setting is the setting of buffers of unlimited capacity and edge capacities 1, which has been previously studied by Adler et al. (Theory Comput. Syst. 35(6):599-623, 2002). For this case our results considerably improve upon previous results: We obtain an approximation ratio of O(min{log*n,log*Sigma,log*M}) (where M is the number of messages in the instance), which is a significant improvement upon the results of Adler et al. who obtained a guarantee of O(min {log n,log I pound,log M}).
We consider the problem of scheduling a set of jobs on a single machine subject to inventory constraints, i.e., conditions that jobs add or remove items to or from a centralized inventory, respectively. Jobs that remo...
详细信息
We consider the problem of scheduling a set of jobs on a single machine subject to inventory constraints, i.e., conditions that jobs add or remove items to or from a centralized inventory, respectively. Jobs that remove items cannot be processed if the required number of items is not available. We focus on scheduling problems on a single machine where the objective is to minimize the total weighted completion time. In this paper, we design 2-approximation algorithms for special cases of the problem that run in polynomial time.
A directed multigraph is said to be d-regular if the indegree and outdegree of every vertex is exactly d. By Hall's theorem, one can represent such a multigraph as a combination of at most n(2) cycle covers, each ...
详细信息
A directed multigraph is said to be d-regular if the indegree and outdegree of every vertex is exactly d. By Hall's theorem, one can represent such a multigraph as a combination of at most n(2) cycle covers, each taken with an appropriate multiplicity. We prove that if the d-regular multigraph does not contain more than [d/2] copies of any 2-cycle then we can find a similar decomposition into n(2) pairs of cycle covers where each 2-cycle occurs in at most one component of each pair. Our proof is constructive and gives a polynomial algorithm to find such a decomposition. Since our applications only need one such a pair of cycle covers whose weight is at least the average weight of all pairs, we also give an alternative, simpler algorithm to extract a single such pair. This combinatorial theorem then comes handy in rounding a fractional solution of an LP relaxation of the maximum Traveling Salesman Problem (TSP) problem. The first stage of the rounding procedure obtains two cycle covers that do not share a 2-cycle with weight at least twice the weight of the optimal solution. Then we show how to extract a tour from the 2 cycle covers, whose weight is at least 2/3 of the weight of the longest tour. This improves upon the previous 5/8 approximation with a simpler algorithm. Utilizing a reduction from maximum TSP to the shortest superstring problem, we obtain a 2.5 -approximation algorithm for the latter problem, which is again much simpler than the previous one. For minimum asymmetric TSP, the same technique gives two cycle covers, not sharing a 2-cycle, with weight at most twice the weight of the optimum. Assuming triangle inequality, we then show how to obtain from this pair of cycle covers a tour whose weight is at most 0.842 log(2) n larger than optimal. This improves upon a previous approximation algorithm with approximation guarantee of 0-999 log(2) n. Other applications of the rounding procedure are approximation algorithms for maximum 3-cycle cover (factor 2/3,
The Joint Replenishment Problem () is a fundamental optimization problem in supply-chain management, concerned with optimizing the flow of goods from a supplier to retailers. Over time, in response to demands at the r...
详细信息
The Joint Replenishment Problem () is a fundamental optimization problem in supply-chain management, concerned with optimizing the flow of goods from a supplier to retailers. Over time, in response to demands at the retailers, the supplier ships orders, via a warehouse, to the retailers. The objective is to schedule these orders to minimize the sum of ordering costs and retailers' waiting costs. We study the approximability of , the version of with deadlines, where instead of waiting costs the retailers impose strict deadlines. We study the integrality gap of the standard linear-program (LP) relaxation, giving a lower bound of , a stronger, computer-assisted lower bound of , as well as an upper bound and approximation ratio of . The best previous upper bound and approximation ratio was;no lower bound was previously published. For the special case when all demand periods are of equal length, we give an upper bound of , a lower bound of , and show APX-hardness.
We consider the robust (min-max regret) version of identical parallel machine scheduling problem, in which jobs may be outsourced to balance total cost against production efficiency. The total cost is measured in term...
详细信息
We consider the robust (min-max regret) version of identical parallel machine scheduling problem, in which jobs may be outsourced to balance total cost against production efficiency. The total cost is measured in terms of the total completion time of jobs processed in-house and the cost of outsourcing the rest. Processing times of in-house jobs are uncertain and they are described as two types of scenarios: discrete and interval. The objective is to obtain a robust (min-max regret) decision that minimises the absolute deviation of total cost from the optimal solution under the worst-case scenario. We first prove the worst-case scenario for any feasible solution. For the interval scenario, we further prove that the maximum regret value can be obtained in polynomial time for any feasible schedule. We also prove that for any discrete scenario, the minimum total cost can be obtained in polynomial time. Since the problem with the interval scenario is strongly NP-hard, we then transform the problem into an equivalent robust single machine scheduling problem. Finally, we develop 2-approximation algorithms for the problem with discrete and interval scenarios, respectively. These results are helpful for bridging the scheduling theory and practice in identical parallel machining environments with outsourcing and uncertain processing times.
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 uni...
详细信息
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 vertical bar E vertical bar of requests (and thus there are no limitations on the tour length), we provide a (2 - 1/vertical bar E vertical bar)-approximation. Finally, we extend our approximation results to include linear and quadratic lateness costs.
暂无评论