The quay crane scheduling problem studied in this article is to determine the handling sequence of ship bays for quay cranes assigned to a container ship considering handling priority of every ship bay. This article p...
详细信息
The quay crane scheduling problem studied in this article is to determine the handling sequence of ship bays for quay cranes assigned to a container ship considering handling priority of every ship bay. This article provides a mixed integer programming model for the considered quay crane scheduling problem that is NP-complete in nature. An approximation algorithm is proposed to obtain near optimal solutions and a worst-case analysis for the approximation algorithm is performed. Computational experiments are conducted to examine the proposed model and solution algorithm. The computational results show that the proposed approximation algorithm is effective and efficient in solving the considered quay crane scheduling problem.
This paper studies the problem of constructing maximum-lifetime data aggregation trees in wireless sensor networks for collecting sensor readings. This problem is known to be NP-hard. Wireless sensor networks in which...
详细信息
This paper studies the problem of constructing maximum-lifetime data aggregation trees in wireless sensor networks for collecting sensor readings. This problem is known to be NP-hard. Wireless sensor networks in which transmission power levels of sensors are adjustable and heterogeneous are considered. An approximation algorithm is developed to construct a data aggregation tree whose inverse lifetime is guaranteed to be within a bound from the optimal one. Adjustable transmission power levels of the sensors introduce an additional term in the bound compared with the bound for networks in which transmission power levels of all sensors are fixed. The additional term is proportional to the difference between the maximum and minimum amounts of energy for a sensor to transmit a message using respectively its maximum and minimum transmission power levels. The proposed algorithm is further enhanced to obtain an improved version. Simulation results show that properly adjusting transmission power levels of the sensors yields higher lifetime of the network than keeping their transmission power levels at the maximum level.
This paper studies single machine scheduling with batch deliveries, where a common due window for all jobs has to be determined, not given in advance. The objective is to minimize the overall cost for the process and ...
详细信息
This paper studies single machine scheduling with batch deliveries, where a common due window for all jobs has to be determined, not given in advance. The objective is to minimize the overall cost for the process and delivery. Concretely, it includes the penalty of a job being early or tardy, the cost for holding and delivering a job, and the cost incurred by a late starting or a long duration of the common due window. Observing the NP-hardness, we provide an optimal algorithm of the problem and convert it to a fully polynomial time approximation scheme for a special case.
To enable Small and Medium-sized Enterprises (SMEs) level garment manufacturers to measure and monitor the work of individual workers without incurring a large financial burden, a smart sewing work measurement system ...
详细信息
To enable Small and Medium-sized Enterprises (SMEs) level garment manufacturers to measure and monitor the work of individual workers without incurring a large financial burden, a smart sewing work measurement system was developed using an IoT-based power monitoring device and an approximation algorithm. The amount of electric current used in the sewing work was measured, and the measured data was transmitted to a server using Wi-Fi communication. The analysis of the data was conducted through the Symbolic Aggregate approximation (SAX) and Dynamic Time Warping (DTW) methods. The daily workload of each worker derived from the system developed through this study showed an error rate of 8% compared to the actual workload, and the time measured by the sensor was different from the time measured by a manager using a stopwatch. These differences are considered to be due to measurement errors in the stopwatch, human noise from the measurer and the operator, and the relatively few samples relative to the total workload. The IoT-based power monitoring and work measurement system for sewing work developed through this study can be applied to smart garment manufacturing factories at an acceptable cost level, while SMEs can realise high recognition rates and semi-real-time monitoring.
We investigate the optimal piecewise linear interpolation of the bivariate product xy over rectangular domains. More precisely, our aim is to minimize the number of simplices in the triangulation underlying the interp...
详细信息
We investigate the optimal piecewise linear interpolation of the bivariate product xy over rectangular domains. More precisely, our aim is to minimize the number of simplices in the triangulation underlying the interpolation, while respecting a prescribed approximation error. First, we show how to construct optimal triangulations consisting of up to five simplices. Using these as building blocks, we construct a triangulation scheme called crossing swords that requires at most - times the number of simplices in any optimal triangulation. In other words, we derive an approximation algorithm for the optimal triangulation problem. We also show that crossing swords yields optimal triangulations in the case that each simplex has at least one axis-parallel edge. Furthermore, we present approximation guarantees for other well-known triangulation schemes, namely for the red refinement and longest-edge bisection strategies as well as for a generalized version of K1-triangulations. Thereby, we are able to show that our novel approach dominates previous triangulation schemes from the literature, which is underlined by illustrative numerical examples.
In the incremental version of the k-median problem, we find a sequence of facility sets F-1 subset of F-2 subset of center dot center dot center dot subset of F-n, where each F-k contains at most k facilities. This se...
详细信息
In the incremental version of the k-median problem, we find a sequence of facility sets F-1 subset of F-2 subset of center dot center dot center dot subset of F-n, where each F-k contains at most k facilities. This sequence is said to be delta-competitive if the cost of each F-k is at most delta times the optimum cost of k facilities. The best deterministic (randomized) algorithm available for the metric space has a competitive ratio of 8 (7.656). The best one for the one"dimensional problem finds a 5.828-competitive sequence. We give a 7.076-competitive solution for the high-dimensional Euclidean space. (C) 2016 Elsevier B.V. All rights reserved.
In this paper, we consider the group prize-collecting Steiner tree problem with submodular penalties (GPCST-SP problem). In this problem, we are given an undirected connected graph G = (V, E) with a pre-specified root...
详细信息
In this paper, we consider the group prize-collecting Steiner tree problem with submodular penalties (GPCST-SP problem). In this problem, we are given an undirected connected graph G = (V, E) with a pre-specified root r and a partition V = {V-0, V-1, ..., V-k} of V with r is an element of V-0. Assume c : E -> R+ is an edge cost function and p : 2(V) -> R+ is a submodular penalty function, where R+ is the set of nonnegative real numbers. For a group V-i is an element of V, we say it is spanned by a tree if the tree contains at least one vertex of that group. The goal of the GPCST-SP problem is to find an r-rooted tree that minimizes the costs of the edges in the tree plus the penalty cost of the subcollection S containing these groups not spanned by the tree. Our main result is a 2I-approximation algorithm for the problem, where I = max{vertical bar V-i vertical bar vertical bar i = 0, 1, 2, ..., k}.
We present an approximation algorithm for the problem of finding a minimum-cost k-vertex connected spanning subgraph, assuming that the number of vertices is at least 6k(2). The approximation guarantee is six times th...
详细信息
We present an approximation algorithm for the problem of finding a minimum-cost k-vertex connected spanning subgraph, assuming that the number of vertices is at least 6k(2). The approximation guarantee is six times the kth harmonic number (which is O(log k)), and this is also an upper bound on the integrality ratio for a standard linear programming relaxation.
In this paper. we consider the asymmetric traveling salesman problem with the gamma- parameterized triangle inequality for gamma is an element of |1/2, 1|. That means the edge weights in the given complete graph G = (...
详细信息
In this paper. we consider the asymmetric traveling salesman problem with the gamma- parameterized triangle inequality for gamma is an element of |1/2, 1|. That means the edge weights in the given complete graph G = (V, E, omega) satisfy omega(u, w) <= gamma . (omega(u, v) + omega(v, w)) for all distinct nodes u, v, w is an element of V. L.S. Chandran and L.S. Ram gave the first constant factor approximation algorithm with polynomial running time for this problem. They achieve performance ratio. gamma/1-gamma. M. Blaser, B. Manthey and J. Sgall obtain a 1+gamma/2-gamma-gamma(3)-approximation algorithm. We devise an approximation algorithm with performance ratio max{1 + gamma(3)/1-gamma(2), gamma+gamma(2)+1/2 + gamma(3)/1(-)gamma(2)}, which is better than both 1+gamma/2-gamma-gamma(3) and gamma/1-gamma for almost all gamma is an element of |1/2, 1|. (c) 2008 Elsevier Inc. All rights reserved.
In this paper we discuss a minmax regret version of the single-machine scheduling problem with the total flow time criterion. Uncertain processing times are modeled by closed intervals. We show that if the determinist...
详细信息
In this paper we discuss a minmax regret version of the single-machine scheduling problem with the total flow time criterion. Uncertain processing times are modeled by closed intervals. We show that if the deterministic problem is polynomially solvable, then its minmax regret version is approximable within 2. (C) 2007 Elsevier B.V. All rights reserved.
暂无评论