Abstract In batch production systems, multiple items can be processed in the same batch if they share sufficiently similar production parameters. We consider the batch consolidation problem of minimizing the number of batches of a finite set of items. This article focuses on the case in which only one or two items can be processed in a single batch. The problem is NP ‐hard and cannot be approximated within 1.0021 of the optimum under the premise, P≠NP. However, the problem admits a ${{3}\over{2}}$ ‐approximation. The idea is to decompose the demands of items so that a maximum matching in the graph on the vertices of the decomposed demands provides a well‐consolidated batch set. © 2010 Wiley Periodicals, Inc. NETWORKS, Vol. 58(1), 12–19 2011

Abstract Consider a network of k servers and their users. Each server provides a unique service that has a certain utility for each user. Now comes an attacker who wishes to destroy a set of network edges to maximize his net gain, namely the total disconnected utilities of the users minus the total edge‐destruction cost. This k ‐server disconnection problem is N P ‐hard and, furthermore, cannot be approximated within a polynomially computable factor of the optimum when k is part of the input. Even for any fixed k ≥ 2, there is a constant ϵ > 0 such that approximation of the problem within a factor 1/(1 + ϵ) of the optimum is NP‐hard. However, a ( ${1\over 2}+{{1}\over {2^{k+1}-2}}$ )‐approximation can be created in the time of O (2 k ) applications of a min‐cut algorithm. The main idea is to approximate the optimum with special solutions computable in polynomial time due to supermodularity. Therefore, when the the network has, as is usual in most cases, only a few servers, a 0.5‐approximation can be carried out in polynomial time. © 2007 Wiley Periodicals, Inc. NETWORKS, Vol. 50(4), 273–282 2007

To provide heterogeneous quality-of-service (QoS) to various applications, the bandwidth of orthogonal frequency division multiplexing (OFDM) is divided into multiple number of sub-bands, which employ a different set of transmission technologies, such as multiple-input multiple-output (MIMO), packet scheduling, adaptive modulation and coding (AMC), and hybrid automatic repeat request (HARQ) depending on the traffic type. According to this concept, DiffSeg system, where the two-dimensional resource domain of OFDM is filled with four different resource units, called segments, and the occupancy ratio of each type of segment is determined by the segment map, has been recently proposed in [5][6]. In this paper, we introduce a concept of segment diversion to utilize the radio resource more efficiently considering the status of QoS. We then propose a system optimization model, which finds an optimal segment map and diversion ratios of real-time (RT) connections in order to maximize the residual resource for non-real-time (NRT) traffic while satisfying the minimum QoS requirement of RT traffic. We formulate an optimization problem using mixed integer programming, and then develop two computationally efficient algorithms: simplex-based heuristic and Maximum Diversion Rule. Especially, Maximum Diversion Rule is shown to achieve a near-optimal solution with dramatically less complexity.

We propose an algorithm for finding a multicast tree in packet-switched networks. The objective is to minimize total cost incurred at the multicast path. The routing model is based on the minimum cost Steiner tree problem. The Steiner problem is extended to incorporate two additional requirements. First, the delay experienced along the path from the source to each destination is bounded. Second, the destinations are allowed to join and leave multicasting anytime during a session. To minimize the disruption to on-going multicasting the algorithm adopts the idea of connecting a new destination to the current multicasting by a minimum cost path satisfying the delay bound. To find such a path is an NP-hard problem and an enumerative method relying on generation of delay bounded paths between node pairs is not likely to find a good routing path in acceptable computation time when network size is large. To cope with such difficulty, the proposed algorithm utilizes an optimization technique called Lagrangian relaxation method. A computational experiment is done on relatively dense and large Waxman's networks. The results seem to be promising. For sparse networks, the algorithm can find near-optimal multicast trees. Also the quality of multicast trees does not seem to deteriorate even when the network size grows. Furthermore, the experimental results shows that the computational efforts for each addition of node to the call are fairly moderate, namely the same as to solve a few shortest path problems.

We propose a static routing model for finding an optimal logical network configuration of a given ATM-based B-ISDN. The model is essentially identical to the model proposed by Kim (1995) which finds a virtual path configuration in which an optimal trade-off is achieved among the relevant gains of ATM technology. Unlike Kim's model, however our model explicitly considers the VP's quality of service to enhance the practicality and the bandwidth utilization. We propose a heuristic algorithm tailored to the computational structure of the model. A computational experiment shows that the algorithm finds good solutions in dramatically reduced computation time compared to the existing algorithm. This suggests the possibility of a real-time VP management system in which optimal routing is implemented on-line with dynamic routing, to maintain the optimality of the current solutions.