A Dual-based Heuristic for the Simple Facility Location Problem With Stochastic Demand

This paper deals with a stochastic version of the simple facility location problem where the demands of customers are random variables. Under the assumption of step function type distribution of demands, the problem is shown to be approximated by a mixed 0-1 linear programming problem. A heuristic procedure is developed to solve the problem, which successfully extends the well known dual-based approach by Bilde & Krarup, and Erlenkotter. Computational results with 20 test problems are presented to demonstrate the effectiveness of the proposed heuristic.     

A column generation approach to the heterogeneous fleet vehicle routing problem

We consider a vehicle routing problem with a heterogeneous fleet of vehicles having various capacities, fixed costs and variable costs. An approach based on column generation (CG) is applied for its solution, hitherto successful only in the vehicle routing problem with time windows. A tight integer programming model is presented, the linear programming relaxation of which is solved by the CG technique. A couple of dynamic programming schemes developed for the classical vehicle routing problem are emulated with some modifications to efficiently generate feasible columns. With the tight lower bounds thereby obtained, the branch-and-bound procedure is activated to obtain an integer solution. Computational experience with the benchmark test instances confirms that our approach outperforms all the existing algorithms both in terms of the quality of solutions generated and the solution time.     

Prioritized channel assignment in a cellular radio network

Dimensioning procedures for prioritized channel assignment in a cellular radio network are considered. Under the cutoff priority discipline, the prioritized channel assignment procedures for a single cell and multicell system are formulated as nonlinear discrete capacity allocation problems. Exact incremental algorithms which efficiently solve the proposed problems are devised. They are based on the properties of the blocking probabilities of new calls and handoff calls. Given the number of available frequency channels together with the arrival rates and the grade of service (GOS) for both types of calls in each cell, algorithm SP1 generates an optimal channel assignment which ensures priority for handoff calls. Given the arrival rates and distinct GOSs for new and handoff calls, algorithm SP2 finds the minimum number of channels required in each cell. Algorithm MP extends algorithm SP1 to a multicell system and provides the prioritized channel assignment for all calls in the system. The algorithms are very fast and are appropriate for the fair allocation of frequency channels among cells     

Spectrum-efficient call control in a dual-mode TDMA cellular system

This study deals with a call control strategy in a dual-mode time-division multiple access (TDMA) cellular system, which provides services both to analog and digital calls. Since analog calls consume the frequency resource several times as much as digital calls, we consider a call control strategy of the threshold type that the number of active analog calls is restricted within a prespecified level. Given the arrival rates and the grade of service (GOS) for both types of calls in the cells, two nonlinear integer optimization problems are considered for a multicell system as well as for a single cell system. One problem is to find the threshold parameters for optimizing the relevant objective measures. The other is to obtain the minimum numbers of required channels in the cells satisfying the GOS of both types of calls. The solution methods for the two kinds of optimization problems are devised based on the properties of the objective function and the blocking probabilities of both call types. The efficiency of the proposed algorithms is verified by extensive computational experiments with realistic input data     

Opportunistic packet scheduling algorithm for non-real-time service with a soft QoS requirement in a mobile broadband wireless access system

In this paper, we present a packet scheduling algorithm for a non-real-time service, with soft QoS requirements, which allows for degrading the QoS level, e.g., typically the packet delay, whenever necessary, in mobile broadband wireless Internet access systems. This algorithm is designed to properly trade off system throughput and delay performance, which can improve the system capacity by relaxing the delay constraint with respect to the underlying soft QoS requirement. This is as opposed to most of the existing packet scheduling algorithms for non-real-time service which are simply designed to maximize the system throughput without a delay constraint. The proposed adaptive exponential scheduling algorithm intentionally introduces additional delay to some users, especially under bad channel conditions, opportunistically allowing for serving users only under good channel conditions, as long as the resulting QoS degradation is acceptable for non-real-time service users. The results from a system-level simulation demonstrate that the system capacity can be significantly increased over existing algorithms, by as much as 65%, using the adaptive exponential scheduling algorithm while satisfying the given QoS-level requirements.     

浅论项目投资决策与设计阶段工程造价的控制

介绍了项目投资决策阶段和设计阶段工程造价控制中存在的问题,并对其原因进行了分析,提出了完善工程造价控制的几点建议,从而规范建筑市场,降低工程造价,提高了工程质量。     

Base station location in a cellular CDMA system

We consider a cellular CDMA system in which blocking is enforced when the relative interference exceeds a certain threshold level. This paper addresses a radio network design problem in such a CDMA system. Given the data of call‐traffic distributed over the service area and potential sites of base stations, the objective of the problem is to locate base stations so as to minimize the associated cost for establishing base stations while keeping the probability of blocking under control. We develop an efficient algorithm for solving the design problem. Computational experiments with real‐world data are conducted to show both the efficiency and the practicality of the proposed design method. This revised version was published online in August 2006 with corrections to the Cover Date.     

Load analysis of the soft handoff scheme in a CDMA cellular system

In a code-division multiple-access cellular system, the soft handoff with macrodiversity is known to increase the number of available channels in each cell from the interference-reduced radio environment. This capability, however, also incurs extra load on the system due to the increase in the number of channels occupied and reserved for macrodiversity. The objective is to evaluate the associated loads, thereby enabling effective channel management. We first differentiate two kinds of loads attributable to new and handoff calls, respectively. Further dividing handoff calls into two kinds, we derive a load balance equation from which three different loads at a cell are all exactly obtained in association with the size of the soft handoff region. Comparative analysis with the case of no soft handoff region, i.e., of hard handoff, shows the appropriate proportion of channels reserved for the macrodiversity in a given soft handoff region     

Perturbation-minimizing frequency assignment in a changingTDMA/FDMA cellular environment

A robust operation of assigning frequencies to requirements in a time-division multiple-access (TDMA) [or frequency-division multiple-access (FDMA)] cellular system should cope with environmental changes such as short-term demand rises and long-term capacity expansions while always keeping the required realignment process as simple as possible. In this paper, we consider the so-called perturbation-minimizing frequency assignment problem (PMFAP), the objective of which is to assign available frequencies for newly generated requirements with the minimum change in the existing frequency assignments while meeting the interference-related constraints. For PMFAP, we propose a heuristic algorithm based on the so-called Bv-Dw rearrangement technique, which can also be applied to the classic frequency assignment problem (PAP) with a slight modification. Two kinds of computational experiments, one for each of the above two problems, are performed to demonstrate the powerful features of the proposed solution method not only in its suitability for real-world frequency management, but also in solving the FAP     

Korean telecommunication industry in transition

This paper, as a preface to this special issue, gives an overview of recent developments in Korean telecommunication market and industry. It provides background information that is helpful for understanding the motivations behind research papers contained in this issue. In particular, we discuss the transition of the market structure from monopoly to deregulated competition, the activities in telecommunications R&D, and the building of nationwide telecommunication infrastructure in Korea. A taxonomy of the papers presented in this issue is given at the end. This revised version was published online in August 2006 with corrections to the Cover Date.