Asia-Pacific Journal of Operational Research

In this paper, we examine the retailer’s information sharing decision in an authentic supply chain with a single supplier and a single retailer under different counterfeiter encroachment situations. We propose a Stackelberg game model to analyze the optimal wholesale price of the supplier, the optimal order quantity of the retailer and the optimal production quantity of the counterfeiter. We obtain the information sharing strategies of the retailer and analyze the impact of the counterfeiter on the authentic supply chain. It is revealed that: (1) under certain conditions, the retailer will voluntarily share information with the upstream supplier and (2) the existence of the counterfeiter may increase the profit of the authentic supply chain.

For a positive real number $k$, the $k$-Sombor index of a graph $G$, introduced by Réti et al, is defined as

In this paper, for $k\ge 1$ we present the extremal values of the $k$-Sombor index of trees with some given parameters, such as matching number, the number of pendant vertices, diameter. This generalizes the relevant results on Sombor index due to Chen, Li and Wang ((2002). Extremal values on the Sombor index of trees, MATCH Communications in Mathematical and in Computer Chemistry, 87, 23–49).

Handling $S{O}_k(G)$ appears to be different for $k<1$ in contrast to the case when $k\ge 1$. To demonstrate this, we also characterize the extremal trees with respect to the ${\mathrm{\text{SO}}}_{\frac{1}{2}}$ with matching number, the number of pendant vertices and diameter. In addition, three relevant conjectures are proposed.

This work investigates a new semi-online scheduling problem with lookahead. We focus on job scheduling on two identical parallel machines, where deterministic online algorithms only know the information of $k$ initial jobs (i.e., the initial-lookahead information), while the following jobs still arrive one-by-one in an over-list fashion. We consider makespan minimization as the objective. The study aims at revealing the value of knowing $k$ initial jobs, which are used to improve the competitive performance of those online algorithms without such initial-lookahead information. We provide the following findings: (1) For the scenario where the $k$ initial jobs are all the largest jobs with length $\mathrm{\Delta }$, we prove that the classical LIST algorithm is optimal with competitive ratio $(k+3)/(k+2)$; (2) For the scenario where the total length of these $k(>1)$ jobs is at least $\mathrm{\Delta }$, we show that any online algorithm has a competitive ratio at least 3/2, implying that the initial-lookahead knowledge is powerless since there exists a 3/2-competitive online algorithm without such information; (3) For the scenario where the total length of these $k(>\alpha )$ jobs is at least $\alpha \mathrm{\Delta }$ ($\alpha \ge 2$), we propose an online algorithm, named as LPT-LIST, with competitive ratio of $(\alpha +2)/(\alpha +1)$, implying that the initial-lookahead information indeed helps to improve the competitiveness of those online algorithms lacking such information.

In this paper, we consider a newsvendor system with strategic customers, who are boundedly rational and risk averse in terms of buying during the selling season or waiting for a clearance sale with price discounts. The newsvendor’s decision is to determine the optimal stock quantity. An optimization problem is formulated with the incorporation of competition among strategic customers with private product value information. We embed risk aversion within the quantal response equilibrium to characterize the strategic customer behavior. The influences of the decision biases of strategic customers on the newsvendor’s decision and profit are discussed. We find that the risk aversion considered alone always benefits the newsvendor. However, the bounded rationality considered alone benefits the newsvendor conditionally. Combining the two behavioral factor influences, the decision biases cause the newsvendor to order more and be better off when the critical fractile is high but to order less and be worse off when the critical fractile is low.

In this paper, we consider two single-processor online scheduling problems with an unexpected breakdown. Speaking specifically, there is a group of nonresumable jobs being processed on the single processor. Note that the breakdown will emerge on the processor suddenly, which signifies that its beginning time and its length are unknown in advance. In this study, we are interested in scheduling the jobs so as to minimize the maximum weighted completion time. Most noticeably, when all jobs respect an agreeable condition, i.e., for each two jobs $J_a$ and $J_b$, $w_a\ge w_b$ means that $p_a\ge p_b$, we design an optimal online algorithm. In addition, for the general version, we propose an online algorithm with a competitive ratio of at most 2.

This paper concentrates on the single-machine scheduling problem with past-sequence-dependent setup times and general truncated learning effects, where the job processing times are non-increasing function of their positions in a sequence. Under common, slack and different (unrestricted) due-date assignments, our goal is to minimize the weighted sum of number of early/tardy jobs and due-date assignment cost, where the weight is not related to the job but to a position, i.e., the position-dependent weight. Under the three due-date assignments, some optimal properties and three optimal solution algorithms are proposed to solve these problems, respectively.

The CDT subproblem, which minimizes a quadratic function over the intersection of two ellipsoids, is a classical quadratic programming problem. In this paper, we study a method of solving CDT with a positive Lagrangian duality gap. An efficient splitting algorithm is proposed for finding the global optimal solutions. A cutting plane is firstly added to divide the feasible set of CDT into two subsets, and then two new quadratic programming problems with ellipsoidal and linear constraints are generated accordingly. Using the newly developed technique — second-order cone constraints to enhance the efficiencies of the SDP relaxation-based algorithms on the two subproblems, an optimal solution of CDT can be acquired by comparing the objective values of the two subproblems. Numerical experiments show that the new algorithm outperforms the two recent SDP relaxation-based algorithms, the two-parameter eigenvalue-based algorithm and the solver Gurobi 9.5 for certain types of CDT.

In this paper, we study the well-known resource availability cost problem with stochastic resource availability. The objective is to determine the initial levels of all renewable resources and establish a schedule corresponding to each scenario such that the expected resource availability cost is minimized. We assume that resource shortfalls can be compensated externally but at a noticeable higher cost. We formulate the problem as a two-stage stochastic programming model (TSSPM). We also develop an exact decomposition-based algorithm (DBA) for the particular case of the problem with at most two resources, which also functions as a heuristic for the original problem. Since the number of scenarios influences the performance of the developed solution approaches, we utilize a fast scenario reduction method to reduce the number of scenarios. Computational results indicate that the DBA outperforms the TSSPM formulation in solution quality and CPU runtime.

Given a network $G=(N,A,c)$ and an $s-t$ cut $[S,\bar{S}]$ with the capacity $\beta$ and the constant value $\alpha$, an inverse minimum $s-t$ cut problem with value constraint is to modify the vector capacity $c$ as little as possible to make the $s-t$ cut $[S,\bar{S}]$ become a minimum $s-t$ cut with the capacity $\alpha$. The distinctive feature of this problem with the inverse minimum cut problems is the addition of a constraint in which the capacity of the given cut has to equal to the preassumed value $\alpha$. In this paper, we investigate the inverse minimum $s-t$ cut problem with value constraint under the bottleneck weighted Hamming distance. We propose two strongly polynomial time algorithms based on a binary search to solve the problem. At each iteration of the first one, we solve a feasible flow problem. The second algorithm considers the problem in two cases $\beta >\alpha$ and $\beta <\alpha$. In this algorithm, we first modify the capacity vector such that the given cut becomes a minimum $s-t$ cut in the network and then, by preserving optimality this $s-t$ cut, adjust it to satisfy value constraint.

In real-life applications, there generally exist Decision Makers (DMs) who have preferences over outputs and inputs. Choosing appropriate weights for different criteria by DMs often arises as a problem. The Best-Worst Method (BWM) in Multiple Criteria Decision-Making (MCDM) depends on very few pairwise comparisons and just needs DMs to identify the most desirable and the least desirable criteria. Unlike MCDM, Data Envelopment Analysis (DEA) does not generally assume a priority for an output (an input) over any other outputs (inputs). The link between DEA and MCDM can be introduced by considering Decision-Making Units (DMUs) as alternatives, outputs as criteria to be maximized, and inputs as criteria to be minimized. In this study, we propose a linear programming model to embed DEA and BWM appropriately. We first propose a modified BWM linear programming model to satisfy all conditions that DMs can assume. We then illustrate how a conventional DEA model can be developed to include the BWM conditions. From our approach, the MCDM problem to obtain the optimal weights of different criteria are measured. At the same time, the relative efficiency scores of DMUs corresponding to the MCDM criteria are also calculated. We provide the foundation of measuring the efficiency scores when most desirable and the least desirable inputs and outputs are known. To show the process of the proposed approach, a numerical example (including 17 DMUs with seven inputs and outputs) is also discussed.