Asia-Pacific Journal of Operational Research

In this paper, we study the optimal or best approximation of any linear operator by low rank linear operators, especially, any linear operator on the ${\ell }_p$-space, $p\in [1,\infty )$, under ${\ell }_p$ norm, or in Minkowski distance. Considering generalized singular values and using techniques from differential geometry, we extend the classical Schmidt–Mirsky theorem in the direction of the ${\ell }_p$-norm of linear operators for some $p$ values. Also, we develop and provide algorithms for finding the solution to the low rank approximation problems in some nontrivial scenarios. The results can be applied to, in particular, matrix completion and sparse matrix recovery.

In this study, we consider zone-based registration (ZBR) in mobile communication networks. In ZBR, when a mobile moves to a new zone, it registers its zone to the network database to keep the mobile’s current zone, and to connect an incoming call to the mobile when it is generated. A mobile can store one zone, or more than one zones. Among various types of ZBR, we focus on two-zone-based registration (TZR), which is known to have good performance. In TZR, a mobile can store two zones that it has recently registered, and does not register when it crosses either zone that it has already kept. In general, in TZR, a mobile registers its zone less often than in single-zone-based registration (SZR). However, TZR increases the paging cost, because the network may not know the exact zone where the mobile is. Mathematical modeling and performance analysis are performed to obtain the exact performance of SZR and TZR, by considering the busy-line effect and implicit registration effect of outgoing calls from a mobile. From numerical results for various circumstances, it is shown that TZR is superior to SZR in most cases.

This paper is devoted to the study of solving method for a type of inverse linear semidefinite programming problem in which both the objective parameter and the right-hand side parameter of the linear semidefinite programs are required to adjust. Since such kind of inverse problem is equivalent to a mathematical program with semidefinite cone complementarity constraints which is a rather difficult problem, we reformulate it as a nonconvex semi-definte programming problem by introducing a nonsmooth partial penalty function to penalize the complementarity constraint. The penalized problem is actually a nonsmooth DC programming problem which can be solved by a sequential convex program approach. Convergence analysis of the penalty models and the sequential convex program approach are shown. Numerical results are reported to demonstrate the efficiency of our approach.

In recent years, the notion of scale elasticity—the relative changes of outputs with respect to relative changes of inputs—has received a lot of ink in the literature. However, all prior studies, except a few of them, assume that changes are equi-proportional. This simplifying assumption makes scale elasticity measure to preserve the throughput mix and implicitly ignores both input independencies and decision-maker preferences. This paper seeks to investigate two main objectives. It initially proposes the notion of directional scale elasticity to allow evaluation of elasticity in any direction which may naturally alter the mix. Subsequently, by providing a tangible geometric interpretation, it attempts to clarify the measure. Relevant computations are used to construct cross sections of frontier in a given direction by enlisting the advantages of parametric optimization algorithm.

We consider the problem of online scheduling a single machine with family setups under job availability. A setup must be scheduled when the next job comes from a different family from the last completed one, if any. The aim is to minimize the total completion time of all jobs. For the special case of identical processing times, we provide a lower bound for the competitive ratio and an online algorithm with its competitive analysis.

The constrained position shift (CPS) model is a famous model in the aircraft arrival sequencing and scheduling (ASS) problem, which allows each aircraft to shift forward or backward at most $k$ (a given integer number) positions in the first come first serve (FCFS) sequence. However, CPS is insufficient to cope with the case that some aircraft requiring more than $k$ positions shift. From this point, we modify it to be a more applicable model, named weighted constrained position shift (W-CPS) model. Three methods are developed to solve W-CPS, which are dynamic programming (DP), mixed integer programming (MIP) and ant colony (AC) algorithm. Numerical results validate the efficiency of these methods.

In this work, a system dynamics simulation approach is proposed to evaluate the effect of sharing information with partners in a supply chain when it is faced with supply-related disruptions which severely affect the product manufacturing. We focus on a simple two-echelon supply chain involving one retailer and two suppliers, and study the retailer’s decision on allocating orders between the suppliers. Three specific settings of information sharing by the suppliers are investigated: (i) no information shared; (ii) information partially shared; and (iii) information completely shared. After establishing corresponding ordering policy under each setting, we conduct extensive numerical analysis to simulate shocks to suppliers’ manufacturing capacity and calculate the resulting extra cost as measure of the effectiveness of information sharing. Simulation results show that with more information shared by suppliers, the retailer is able to make response to disruptions more accurately and timely, the negative impact of which thus can be reduced by larger extent, even though not completely eliminated.

In this paper, we formulate a stochastic periodic-review inventory model with lead-time that considers both duration- and quantity-dependent inventory costs, and show that the optimality equation has the same format as the standard newsvendor problem with a modified demand distribution. We suggest (i) an approximation of the optimal order-up-to level, based on discretization of the inventory cost accounting, and (ii) two heuristic formulas, based on the two-moment normal approximation of the modified demand distribution, and on an approximated deterministic model. We evaluate the performances of these formulas using a Brownian motion demand process under different scenarios, and discuss their advantages and disadvantages.

This paper attempt to generate a representative subset of the Pareto optimal set for multiple objective mixed integer linear programming problem using the weighted L₁ norm distance. The procedure presented in this paper is somewhat similar to the one used in the ideal-point methods and its aim is to generate at each iteration the closest-points to the ideal vector corresponding to the decision maker’s initial aspiration level for a new tradeoff parameter. Unlike most of the known algorithms for generating a discrete representation of the Pareto optimal set, the procedure generates at each iteration a nondominated point by solving only one mixed integer linear programming problem. The obtained solution minimizes the weighted L₁ norm distance to the ideal vector with respect to the distance between the ideal vector and previously found vectors. More generally, this approach is able to generate all Pareto optimal solutions, where all of the decision variables are restricted to be integer. In order to explain the presented details, several illustrative examples are provided.

In this paper, we consider a three-machine makespan minimization permutation flow shop scheduling problem with shortening job processing times. Shortening job processing times means that its processing time is a nonincreasing function of its execution start time. Optimal solutions are obtained for some special cases. For the general case, several dominance properties and two lower bounds are developed to construct a branch-and-bound (B&B) algorithm. Furthermore, we propose a heuristic algorithm to overcome the inefficiency of the branch-and-bound algorithm.