Improved approximation algorithms for non-preemptive multiprocessor scheduling with testing

Multiprocessor scheduling, also called scheduling on parallel identical machines to minimize the makespan, is a classic optimization problem which has been extensively studied. Scheduling with testing is an online variant, where the processing time of a job is revealed by an extra test operation, otherwise the job has to be executed for a given upper bound on the processing time. Albers and Eckl recently studied the multiprocessor scheduling with testing; among others, for the non-preemptive setting they presented an approximation algorithm with competitive ratio approaching 3.1016 when the number of machines tends to infinity and an improved approximation algorithm with competitive ratio approaching 3 when all test operations take one unit of time each. We propose to first sort the jobs into non-increasing order of the minimum value between the upper bound and the testing time, then partition the jobs into three groups and process them group by group according to the sorted job order. We show that our algorithm achieves better competitive ratios, which approach 2.9513 when the number of machines tends to infinity in the general case; when all test operations each takes one time unit, our algorithm achieves even better competitive ratios approaching 2.8081.

     

A framework for production rescheduling in sociotechnical manufacturing environments

No plan survives contact with reality. Despite the rich research base regarding handling uncertainty in production planning and control systems, there is an intellectual gap between theory and practice with regard to handling unforeseen events generated by internal and external factors, such as unforeseen machine downtimes and changes in demand. Motivated by longitudinal observations in two industrial settings and an analysis of the relevant literature, a framework for rescheduling decision-making in the face of unforeseen production events is proposed. In practical settings, the effectiveness of decisions depends on a set of situational factors. The findings of this research can be utilised further to provide guidelines for developing effective decision support principles and systems, addressing the needs of organisational decision-makers.     

Constant time approximation scheme for largest well predicted subset

The largest well predicted subset problem is formulated for comparison of two predicted 3D protein structures from the same sequence. A 3D protein structure is represented by an ordered point set A={a ₁,…,a _n }, where each a _i is a point in 3D space. Given two ordered point sets A={a ₁,…,a _n } and B={b ₁,b ₂,…b _n } containing n points, and a threshold d, the largest well predicted subset problem is to find the rigid body transformation T for a largest subset B _opt of B such that the distance between a _i and T(b _i ) is at most d for every b _i in B _opt . A meaningful prediction requires that the size of B _opt is at least αn for some constant α (Li et al. in CPM 2008, 2008). We use LWPS(A,B,d,α) to denote the largest well predicted subset problem with meaningful prediction. An (1+δ ₁,1?δ ₂)-approximation for LWPS(A,B,d,α) is to find a transformation T to bring a subset B′?B of size at least (1?δ ₂)|B _opt | such that for each b _i ∈B′, the Euclidean distance between the two points distance?(a _i ,T(b _i ))≤(1+δ ₁)d. We develop a constant time (1+δ ₁,1?δ ₂)-approximation algorithm for LWPS(A,B,d,α) for arbitrary positive constants δ ₁ and δ ₂. To our knowledge, this is the first constant time algorithm in this area. Li et al. (CPM 2008, 2008) showed an $O(n(\log n)^{2}/\delta_{1}^{5})$ time randomized (1+δ ₁)-distance approximation algorithm for the largest well predicted subset problem under meaningful prediction. We also study a closely related problem, the bottleneck distance problem, where we are given two ordered point sets A={a ₁,…,a _n } and B={b ₁,b ₂,…b _n } containing n points and the problem is to find the smallest d _opt such that there exists a rigid transformation T with distance(a _i ,T(b _i ))≤d _opt for every point b _i ∈B. A (1+δ)-approximation for the bottleneck distance problem is to find a transformation T, such that for each b _i ∈B, distance?(a _i ,T(b _i ))≤(1+δ)d _opt , where δ is a constant. For an arbitrary constant δ, we obtain a linear O(n/δ ⁶) time (1+δ)-algorithm for the bottleneck distance problem. The best known algorithms for both problems require super-linear time (Li et al. in CPM 2008, 2008).     

A practical model for last train rescheduling with train delay in urban railway transit networks

Last train timetable rescheduling aims at coordinating the arrival and departure times of feeder trains with connecting trains at transfer stations to eliminate the effect of unexpected incidents in train operations. It has become a challenging problem in the operations and management of urban railway transit networks because of high complexities in coordination among lines. In this paper, we propose a rescheduling model for last trains with the consideration of train delays caused by incidents that occurred in train operations. In the model, two aspects are considered. On one hand, we try to minimize the running time and the dwell time, and to maximize the average transfer redundant time and the network accessibility. On the other hand, we expect to minimize the difference between the original timetable and the rescheduled one. A genetic algorithm is developed to solve this problem. The case study of Beijing railway transit network shows that once a delay occurs in a section, the most effective way to adjust the timetable consists of adjusting the running time of trains that have strong transfer relationships with the delay section. If the delay is not substantially long, the suggested model would neutralize the influence of the delay.     

A successive approximation algorithm for the multiple knapsack problem

It is well-known that the multiple knapsack problem is NP-hard, and does not admit an FPTAS even for the case of two identical knapsacks. Whereas the 0-1 knapsack problem with only one knapsack has been intensively studied, and some effective exact or approximation algorithms exist. A natural approach for the multiple knapsack problem is to pack the knapsacks successively by using an effective algorithm for the 0-1 knapsack problem. This paper considers such an approximation algorithm that packs the knapsacks in the nondecreasing order of their capacities. We analyze this algorithm for 2 and 3 knapsack problems by the worst-case analysis method and give all their error bounds.     

A primal-dual approximation algorithm for the Asymmetric Prize-Collecting TSP

We present a primal-dual ?log(n)?-approximation algorithm for the version of the asymmetric prize collecting traveling salesman problem, where the objective is to find a directed tour that visits a subset of vertices such that the length of the tour plus the sum of penalties associated with vertices not in the tour is as small as possible. The previous algorithm for the problem (V.H. Nguyen and T.T Nguyen in Int. J. Math. Oper. Res. 4(3):294–301, 2012) which is not combinatorial, is based on the Held-Karp relaxation and heuristic methods such as the Frieze et al.’s heuristic (Frieze et al. in Networks 12:23–39, 1982) or the recent Asadpour et al.’s heuristic for the ATSP (Asadpour et al. in 21st ACM-SIAM symposium on discrete algorithms, 2010). Depending on which of the two heuristics is used, it gives respectively 1+?log(n)? and $3+ 8\frac{\log(n)}{\log(\log(n))}$ as an approximation ratio. Our algorithm achieves an approximation ratio of ?log(n)? which is weaker than $3+ 8\frac{\log(n)}{\log(\log(n))}$ but represents the first combinatorial approximation algorithm for the Asymmetric Prize-Collecting TSP.     

A classification scheme for local government documents collections

The University of Dayton's Roesch Library required a classification scheme for its local documents collection. It needed a scheme that would assign each title a unique call number. Existing schemes were examined but rejected. A new alphanumeric scheme was devised. It is intended primarily for collections limited to publications from the governments and civic organizations of no more than several countries.     

The value of rescheduling functionality within standard MRP packages

One of the basic functions of an MRP system is to issue rescheduling messages that urge the planner tospeed up or slow down open orders. It seems in practice that these messages are not used at all by planners. This is mostly due to the inaccuracy of MRP, that more or less ignores safety time, safety stocks and lotsize flexibility in the calculation of reschedule-in messages. Reschedule-out messages are usually ignored because planners do not see the value of the message. Other reasons for not adhering to rescheduling messages are a lack of maintenance of MRP parameters or simply the wrong use of the MRP function. In the future, MRP rescheduling functionality will be used even less than today, due to the changing role of MRP within the planning framework. With the uprise of finite capacity scheduling packages, MRP is being pushed one level upward in the planning hierarchy. This means that rescheduling functionalities for the short term will become completely obsolete in MRP systems.     

An ant colony optimization approach for the proportionate multiprocessor open shop

Multiprocessor open shop makes a generalization to classical open shop by allowing parallel machines for the same task. Scheduling of this shop environment to minimize the makespan is a strongly NP-Hard problem. Despite its wide application areas in industry, the research in the field is still limited. In this paper, the proportionate case is considered where a task requires a fixed processing time independent of the job identity. A novel highly efficient solution representation is developed for the problem. An ant colony optimization model based on this representation is proposed with makespan minimization objective. It carries out a random exploration of the solution space and allows to search for good solution characteristics in a less time-consuming way. The algorithm performs full exploitation of search knowledge, and it successfully incorporates problem knowledge. To increase solution quality, a local exploration approach analogous to a local search, is further employed on the solution constructed. The proposed algorithm is tested over 100 benchmark instances from the literature. It outperforms the current state-of-the-art algorithm both in terms of solution quality and computational time.

     

A practical greedy approximation for the directed Steiner tree problem

The directed Steiner tree (DST) NP-hard problem asks, considering a directed weighted graph with n nodes and m arcs, a node r called root and a set of k nodes X called terminals, for a minimum cost directed tree rooted at r spanning X. The best known polynomial approximation ratio for DST is a \(O(k^\varepsilon )\)-approximation greedy algorithm. However, a much faster k-approximation, returning the shortest paths from r to X, is generally used in practice. We give two new algorithms : a fast k-approximation called Greedy\(_\text {FLAC}\) running in \(O(m \log (n)k + \min (m, nk)nk^2)\) and a \(O(\sqrt{k})\)-approximation called Greedy\(_\text {FLAC}^\triangleright \) running in \(O(nm + n^2 \log (n)k +n^2 k^3)\). We provide computational results to show that, Greedy\(_\text {FLAC}\) rivals in practice with the running time of the fast k-approximation and returns solution with smaller cost in practice.     

Improved mixed-integer programming models for the multiprocessor scheduling problem with communication delays

We revise existing and introduce new mixed-integer programming models for the Multiprocessor scheduling problem with communication delays. The basis for both is the identification of two major modeling strategies one of which can be considered ordering-based, and the other assignment-based. We first reveal redundancies in the encoding of feasible solutions found in present formulations and discuss how they can be avoided. For the assignment-based approach, we propose new inequalities that lead to provably stronger continuous relaxations and better performance in practice. Moreover, we derive a third, novel modeling strategy and show how to more compactly linearize assignment formulations with quadratic constraints. In a comprehensive experimental comparison of representative models that reflect the state-of-the-art in terms of strength and size, we evaluate not only running times but also the obtained lower and upper bounds on the makespan for the harder instances of a large scale benchmark set.     

Taking into account the rescheduling problem during the scheduling phase

The scheduling problem in production management has been studied for a considerable time, and several types of software are used. A problem arises in updating the production planning, or ‘rescheduling’, when an unexpected event occurs in the shop control. Solving this problem is difficult because the implications of such events are usually impossible to forecast. To prevent this problem, we propose to manipulate a set of equivalent schedules during the short time schedule. Then, if an unexpected event prevents realization of a given schedule, it will be possible to find an equivalent one, without full rescheduling. The primary requirement is to find a formal representation of a set of schedules. This has already been explored using CPM graphs with nodes associated to a set of tasks. We propose in this paper to use an extension of such graphs, PQR trees, that represent both precedence and group constraints. We first reiterate the notion of PQR trees. We present methods to take into account date constraints in such a structure, and we give a model for the general job-shop problem.     

A simple approximation algorithm for minimum weight partial connected set cover

Let \(LTQ_n\) be the n-dimensional locally twisted cube. Hsieh and Tu (Theor Comput Sci 410(8–10):926–932, 2009) proposed an algorithm to construct n edge-disjoint spanning trees rooted at a particular vertex 0 in \(LTQ_n\). Later on, Lin et al. (Inf Process Lett 110(10):414–419, 2010) proved that Hsieh and Tu’s spanning trees are indeed independent spanning trees (ISTs for short), i.e., all spanning trees are rooted at the same vertex r and for any other vertex \(v(\ne r)\), the paths from v to r in any two trees are internally vertex-disjoint. Shortly afterwards, Liu et al. (Theor Comput Sci 412(22):2237–2252, 2011) pointed out that \(LTQ_n\) fails to be vertex-transitive for \(n\geqslant 4\) and proposed an algorithm for constructing n ISTs rooted at an arbitrary vertex in \(LTQ_n\). Although this algorithm can simultaneously construct n ISTs, it is hard to be parallelized for the construction of each spanning tree. In this paper, from a modification of Hsieh and Tu’s algorithm, we present a fully parallelized scheme to construct n ISTs rooted at an arbitrary vertex in \(LTQ_n\) in \({\mathcal O}(n)\) time using \(2^n\) vertices of \(LTQ_n\) as processors.     

A simple greedy approximation algorithm for the minimum connected $$$$-Center problem

In this paper, we consider the connected \(k\)-Center (\(CkC\)) problem, which can be seen as the classic \(k\)-Center problem with the constraint of internal connectedness, i.e., two nodes in a cluster are required to be connected by an internal path in the same cluster. \(CkC\) was first introduced by Ge et al. (ACM Trans Knowl Discov Data 2:7, 2008), in which they showed the \(NP\)-completeness for this problem and claimed a polynomial time approximation algorithm for it. However, the running time of their algorithm might not be polynomial, as one key step of their algorithm involves the computation of an \(NP\)-hard problem. We first present a simple polynomial time greedy-based \(2\)-approximation algorithm for the relaxation of \(CkC\)—the \(CkC^*\). Further, we give a \(6\)-approximation algorithm for \(CkC\).     

A continuous approximation method for dynamic pricing problem under costly price modifications

This paper presents a heuristic method to solve a dynamic pricing problem under costly price modifications. This is an extremely difficult nonlinear problem that has been solved only for a few special instances. Here we provide a new approach that involves an approximate reformulation of the problem, which can subsequently be solved in closed-form using elementary calculus techniques. Numerical results show that the approach is quite accurate; approximating the optimal revenue with errors usually much less than 1%. Moreover, the accuracy rapidly improves as the optimal number of price changes increases, which are precisely the cases conventional approaches would fail.     

A better constant-factor approximation for weighted dominating set in unit disk graph

This paper presents a (10+ε)-approximation algorithm to compute minimum-weight connected dominating set (MWCDS) in unit disk graph. MWCDS is to select a vertex subset with minimum weight for a given unit disk graph, such that each vertex of the graph is contained in this subset or has a neighbor in this subset. Besides, the subgraph induced by this vertex subset is connected. Our algorithm is composed of two phases: the first phase computes a dominating set, which has approximation ratio 6+ε (ε is an arbitrary positive number), while the second phase connects the dominating sets computed in the first phase, which has approximation ratio 4. This work is supported in part by National Science Foundation under grant CCF-9208913 and CCF-0728851; and also supported by NSFC (60603003) and XJEDU.     

Improved approximation algorithms for metric MaxTSP

We present two polynomial-time approximation algorithms for the metric case of the maximum traveling salesman problem. One of them is for directed graphs and its approximation ratio is . The other is for undirected graphs and its approximation ratio is . Both algorithms improve on the previous bests. A preliminary version of this paper appeared in the Proceedings of 13th European Symposium on Algorithms (ESA2005), Lecture Notes in Computer Science, Vol. 3669, pp. 179–190, 2005.     

A tighter insertion-based approximation of the crossing number

Let G be a planar graph and F a set of additional edges not yet in G. The multiple edge insertion problem (MEI) asks for a drawing of \(G+F\) with the minimum number of pairwise edge crossings, such that the subdrawing of G is plane. Finding an exact solution to MEI is NP-hard for general F. We present the first polynomial time algorithm for MEI that achieves an additive approximation guarantee—depending only on the size of F and the maximum degree of G, in the case of connected G. Our algorithm seems to be the first directly implementable one in that realm, too, next to the single edge insertion. It is also known that an (even approximate) solution to the MEI problem would approximate the crossing number of the F-almost-planar graph \(G+F\), while computing the crossing number of \(G+F\) exactly is NP-hard already when \(|F|=1\). Hence our algorithm induces new, improved approximation bounds for the crossing number problem of F-almost-planar graphs, achieving constant-factor approximation for the large class of such graphs of bounded degrees and bounded size of F.     

A new approximation algorithm for the Selective Single-Sink Buy-at-Bulk problem in network design

The Selective Single-Sink Buy-at-Bulk problem was proposed by Awerbuch and Azar (FOCS 1997). For a long time, the only known non-trivial approach to approximate this problem is the tree-embedding method initiated by Bartal (FOCS 1996). In this paper, we give a thoroughly different approximation approach for the problem with approximation ratio $O(\sqrt{q})$ , where q is the number of source terminals in the problem instance. Our approach is based on a mixed strategy of LP-rounding and the greedy method. When the number q (which is always at most n) is relatively small (say, q=o(log² n)), our approximation ratio $O(\sqrt{q})$ is better than the currently known best ratio O(logn), where n is the number of vertices in the input graph.     

A simple linear time approximation algorithm for multi-processor job scheduling on four processors

Multiprocessor job scheduling problem has become increasingly interesting, for both theoretical study and practical applications. Theoretical study of the problem has made significant progress recently, which, however, seems not to imply practical algorithms for the problem, yet. Practical algorithms have been developed only for systems with three processors and the techniques seem difficult to extend to systems with more than three processors. This paper offers new observations and introduces new techniques for the multiprocessor job scheduling problem on systems with four processors. A very simple and practical linear time approximation algorithm of ratio bounded by 1.5 is developed for the multi-processor job scheduling problem P ₄|fix|C _max, which significantly improves previous results. Our techniques are also useful for multiprocessor job scheduling problems on systems with more than four processors.