Asia-Pacific Journal of Operational Research

Pairwise comparison is commonly used to estimate the priority values of finite alternatives with respect to a given criterion. We evaluate seven specially selected direct methods of estimating priority vectors from reciprocal pairwise comparison matrices under four effectiveness measures. A simulation experiment is designed starting with true priority vectors that represent difficult cases of "no obvious best alternative" and "two equal best alternatives". The simulation results suggest that the geometric mean method is in general the best method with the normalized column mean method as a close second best.

A single item, single cycle economic production quantity model for perishable products is proposed where the demand is two-component and stock dependent. The production inventory scenario of products like cake, bread, fast foods, fishes, garments, cosmetics etc in the festival season is considered. The profit function is formulated under the assumption that the time period of the festival seasons is fixed and the display capacity of the produced item is limited. In the formulation process, to introduce more flexibility, a goal programming technique is incorporated to achieve the producer's desired profit and stock of as much inventory as possible below the display capacity level. A numerical example is presented to illustrate the proposed model. A sensitivity analysis of the model is also carried out.

We consider a non-preemptive single machine scheduling problem with forbidden intervals. Associated with each job is a given processing time and a delivery time to its customer, when the processing of the job is complete. The objective is to minimize the time taken for all the jobs to be delivered to the customers. The problem is strongly NP-hard in general. In this study, we show that the case with a fixed number of forbidden intervals can be solved by a pseudo-polynomial time algorithm, while no polynomial time approximation algorithm with a fixed performance ratio exists for the case with two forbidden intervals. We also develop a polynomial time approximation scheme (PTAS) for the case with a single forbidden interval.

This paper establishes a theory framework of a class of nonlinear Lagrangians for solving nonlinear programming problems with inequality constraints. A set of conditions are proposed to guarantee the convergence of nonlinear Lagrangian algorithms, to analyze condition numbers of nonlinear Lagrangian Hessians as well as to develop the dual approaches. These conditions are satisfied by well-known nonlinear Lagrangians appearing in literature. The convergence theorem shows that the dual algorithm based on any nonlinear Lagrangian in the class is locally convergent when the penalty parameter is less than a threshold under a set of suitable conditions on problem functions and the error bound solution, depending on the penalty parameter, is also established. The paper also develops the dual problems based on the proposed nonlinear Lagrangians, and the related duality theorem and saddle point theorem are demonstrated. Furthermore, it is shown that the condition numbers of Lagrangian Hessians at optimal solutions are proportional to the controlling penalty parameters. We report some numerical results obtained by using nonlinear Lagrangians.

The Knapsack Node Weighted Steiner Tree Problem (KNWSTP) is a generalization of the Steiner Tree Problem on graphs, which takes into account the classical cost function defined on the edges, as well as a prize function defined on the vertices and a limit on the size of the solution. It has several applications to network design. We propose an exact branch-and-bound algorithm for this problem, based on a relax-and-cut approach: the algorithm relaxes an exponential family of generalized subtour elimination constraints and takes into account only the violated ones as the computation proceeds. The performance of the algorithm has been tested on a wide set of benchmark problems, up to three hundred vertices, whose structure reflects the features of the most likely applications (sparse graphs with Euclidean costs) and covers different cases with respect to the prize function (only positive, or both positive and negative prizes) and the weight threshold.

Determination of the stability behavior of a queueing network is an important part of analyzing such systems. Gamarnik and Hasenbein (2005) have shown that if a fluid network has the finite decomposition property (FDP) and is not weakly stable, then any queueing network associated with the fluid network is not rate stable. In Gamarnik and Hasenbein's paper, the FDP was demonstrated for two station queueing networks only. In this paper, we show that the property holds for certain classes of queueing networks with any number of stations, thus allowing one to completely analyze the global stability of such queueing networks via the fluid model.

Conjugate gradient methods are efficient to minimize differentiable objective functions in large dimension spaces. Recently, Dai and Yuan introduced a tree-parameter family of nonlinear conjugate gradient methods and show their convergence. However, line search strategies usually bring computational burden. To overcome this problem, in this paper, we study the global convergence of a special case of three-parameter family(the CD-DY family) in which the line search procedures are replaced by fixed formulae of stepsize.