Asia-Pacific Journal of Operational Research

A new kind of second-order tangent derivative, second-order $M$-composed tangent derivative, for a set-valued function is introduced with help of a modified Dubovitskij–Miljutin cone. By using the concept, several generalized convex set-valued functions are introduced. When both the objective function and constrained function are second-order $M$-composed derivable, under the assumption of nearly cone-subconvexlikeness, by applying a separation theorem for convex sets, Fritz John and Kuhn–Tucker second-order necessary optimality conditions are obtained for a point pair to be a weak minimizer of set-valued optimization problem. Under the assumption of generalized pseudoconvexity, a Kuhn–Tucker second-order sufficient optimality condition is obtained for a point pair to be a weak minimizer of set-valued optimization problem. A unified second-order necessary and sufficient optimality condition is derived in terms of second-order $M$-composed tangent derivatives.

This paper is concerned with a new variant of the inverse 1-median location problem in which the aim is to modify the customer weights such that a predetermined facility location becomes a 1-median location and the total profit obtained via the weight improvements is maximized. We develop novel combinatorial approaches with linear time complexities for solving the problem on tree networks and in the plane under the rectilinear and Chebyshev norms.

In this paper, we consider quantitative stability for full random two-stage linear stochastic program with second-order conic constraints when the underlying probability distribution is subjected to perturbation. We first investigate locally Lipschitz continuity of feasible set mappings of the primal and dual problems in the sense of Hausdorff distance which derives the Lipschitz continuity of the objective function, and then establish the quantitative stability results of the optimal value function and the optimal solution mapping for the perturbation problem. Finally, the obtained results are applied to the convergence analysis of optimal values and solution sets for empirical approximations of the stochastic problems.

In order to identify critical activities and critical sequences under resource availability constraints, resource dependencies need to be established. By doing this, project managers and practitioners can focus their limited energy on specific activities and paths during the execution of a project schedule, thus guaranteeing that the project gets finished on time and with the available resources. This study proposes various rules to judge the superiority or inferiority of the methods of dependencies’ creation. The total number of critical sequences which is one of these rules, directly influences the degree of difficulty in controlling the whole project — a major concern for project managers. This study classifies activities in a resource-constrained project schedule on the basis of the relationships between activities and develops the basic idea behind the optimization of resource dependencies. Specifically, two mathematical models to minimize the total number of critical sequences and that of resource links through the table translation method are proposed. A computation example shows great improvement in the number of critical sequences, critical activities and resource links and gives effective results while solving the problems in the previous research. Moreover, simulations using J30, J60, and J120 instances by Kolisch highlight the high computing speed when searching for the actual minimum number of critical sequences and resource links thanks to the table translation method.

In this paper, we consider a scheduling problem with $m$ uniform parallel-batching machines $\{M_1,M_2,\dots ,M_m\}$ under game situation. There are $n$ jobs, each of which is associated with a load. Each machine $M_i(1\le i\le m)$ has a speed $s_i$ and can handle up to $b$ jobs simultaneously as a batch. The load of a batch is the load of the longest job in the batch. All the jobs in a batch start and complete at the same time. Each job is owned by an agent and its individual cost is the completion time of the job. The social cost is the largest completion time over all jobs, i.e., the makespan. We design a coordination mechanism for the scheduling game problem. We discuss the existence of Nash Equilibrium and offer an upper bound on the price of anarchy (POA) of the coordination mechanism. We present a greedy algorithm and show that: (i) under the coordination mechanism, any instance of the scheduling game problem has a unique Nash Equilibrium and it is precisely the schedule returned by the greedy algorithm; (ii) the mechanism has a POA no more than $1+\frac{s_{max}}{\bar{s}}\left(\right.1-\frac{1}{max\{m,b\}}\left)\right.+\delta$, where $s_{max}=max\{s_1,s_2,\dots ,s_m\}$, $\bar{s}=(s_1+s_2+\cdots +s_m)/m$, and $\delta$ is a small positive number that tends to 0.

Cost and schedule management are important issues in an information technology outsourcing project. Generally, a client does not know much about market quotation and ability of vendors. Thus, an efficient approach should select a suitable vendor for the project with balanced cost and schedule. In this study, an improved standard English auction (ISEA) is designed, in which the multi-attribute situation is considered, and multi-attribute utility theory (MAUT) is introduced. A new auction protocol and a utility increment function are proposed, respectively. Finally, numerical examples are designed to demonstrate the auction process and its operation. Some insights are found: The ISEA is competent to describe the cost and schedule management process in an auction approach. The optimal incremental utility for client and vendor are found, and the proposed auction protocol is a mechanism for the client and vendor to obtain win–win results. The completely consistent results can be obtained from different size cases, which indicates that the validity of the designed auction mechanism and the effect of the utility increase function on the negotiation results.

Two classical pivoting algorithms, due to Lemke and Cottle–Dantzig, are studied on linear complementarity problems (LCPs) and their generalizations that arise from infinite duration two-person mean payoff games (MPGs) under zero-mean partition problem. Lemke’s algorithm was studied in solving MPGs via reduction to discounted payoff games or to simple stochastic games. We provide an alternative and efficient approach for studying the LCPs arising from the MPGs without any reduction. A binary MPG can easily be formulated as an LCP which has always terminated in a complementary solution in numerical experiments, but has not yet been proven either the processability of MPG’s by Lemke’s algorithm or a counter example that it will not terminate with a solution. Till now, the processability of MPG’s by Lemke’s algorithm remains open. A general MPG (with arbitrary outgoing arcs) naturally reduces to a generalized linear complementarity problem (GLCP) involving a rectangular matrix where the vertices are represented by the columns and the outgoing arcs from each vertex are represented by rows in a particular block. The noteworthy result in this paper is that the GLCP obtained from an MPG is processable by Cottle–Dantzig principal pivoting algorithm which terminates with a solution. Several properties of the matrix which arise in this context are also discussed.

Although existing contributions that explore service quality guarantee problem of a logistic service supply chain (LSSC) consider fairness concern behavior of one member, little attention is paid to considering the combination of members’ fairness concern and the joint decision of pricing and service quality guarantee in LSSC. Therefore, it is necessary to research how different fairness concern affects the joint decision of pricing and service quality guarantee in an LSSC. First considering a price and quality-sensitive logistics service market, a basic model without fairness concern of a customized LSSC is established. Then, a new model with fairness concern of a decentralized LSSC is constructed based on the basic model. The optimal decision of the LSSC with fairness concern is investigated in three cases. In each case, we analyze the effect of fairness concern on the optimal decision, and the expected profits and utilities. Finally, some numerical studies are shown to verify our theoretical analyses and some managerial insights are given.

This paper studies a two-agent single-machine scheduling problem with sum-of-processing-times-based learning consideration. The goal is to find an optimal schedule to minimize the total late work of the first agent subject to the restriction that the maximum lateness of the second agent has an upper bound. For this problem, a branch-and-bound algorithm along with several dominances and a lower bound is developed to find the optimal solution, and a tabu algorithm with several improvements is proposed to find the near-optimal solution. Computational experiments are provided to further measure the performance of the proposed algorithms.

For a system of two tandem queues with a finite intermediate buffer, we study the asymptotically maximal throughput as the number of servers in each station grows to infinity. First, we study the system with only dedicated servers, and then we examine the system with both dedicated and flexible servers. We assume that travel times between the two stations are negligible and that each server can only work on one customer at a time. We model the system as a birth–death Markov process, derive a closed form solution for the stationary distribution, and quantify the maximal asymptotic normalized throughput as the number of servers grows to infinity. We show that flexibility is more favorable for small systems, and as the number of servers grows, the benefits of flexibility decrease. Furthermore, we prove that when the number of servers goes to infinity, there is no need of flexibility at all, as the maximum value of the throughput is obtained. However, flexibility still has a secondary beneficial effect — a little flexibility (on the order of the square root of the number of dedicated servers at each station) guarantees that all dedicated servers are busy and results in faster convergence to the maximum throughput.