Asia-Pacific Journal of Operational Research

We consider the time-dependent scheduling with proportional and delivery times on a single machine. Three models of the processing times are addressed here, they are proportional deterioration, proportional-linear shortening and proportional-linear increasing. The objective is to minimize the time by which all jobs are delivered. For the first model, we prove that the problem is polynomial solvable when jobs have identical release dates. When jobs arrive dynamically, we first give the proof of the NP-hardness and present a two-approximation algorithm. Then we propose a fully polynomial time approximation scheme for the case where the number of distinct release dates is a constant by applying the “rounding-the-input-data” technique. For the second and third models, when jobs have identical release dates, we prove that they are polynomial solvable, when jobs have different release dates, we present two-approximation algorithms for each of them.

While single-period stochastic inventory problems have been studied in academia and industry, the impacts of both carbon emissions reduction and partial distribution information have not been investigated. In this paper, we consider carbon emission reduction in a single-period inventory problem where both product price and demand are stochastic. When only partial information on the first and second moments of the two stochastic elements is specified, we use the max–min criterion to construct two optimization models under cap-and-trade and carbon tax policies. For each model, we prove the existence of the optimal robust decisions on production quantity and cleaning equipment investment. By comparing the profit and carbon emission between these two models, we identify certain conditions that improve the economic and environmental performance of the manufacturer. Finally, we conduct a numerical study to test the robustness of the optimal operational decisions under each carbon policy.

The traceability of Blockchain Technology (BT) has been implemented widely in many industries, but coupled with this fact is that more and more consumers focus on personal privacy information security. This paper mainly studies a BT-enabled operation system with customers’ privacy preferences and enterprises’ privacy protection. From the short-term perspective, we first investigate the impacts of different privacy attitudes from consumers on the optimal pricing and privacy protection decisions of enterprises in two scenarios with and without BT. Then, we give the conditions of enterprises adopting BT. Furthermore, from the long-term perspective, when privacy protection insurance is provided for risk-averse consumers, we also investigate the evolutionary stability strategies between enterprises and consumers using the evolutionary game theory. Finally, numerical analysis is adopted to verify the theoretical results and show that privacy protection and BT are important to the operation of enterprises and the purchasing behavior of consumers.

Given an undirected complete graph $G=(V,E)$ on $kn$ vertices with a non-negative weight function on $E$, the maximum-weight $k$-cycle ($k$-path) packing problem aims to compute a set of $n$ vertex-disjoint cycles (paths) in $G$ containing $k$ vertices so that the total weight of the edges in these $n$ cycles (paths) is maximized. For the maximum-weight $k$-cycle packing problem, we develop an algorithm achieving an approximation ratio of $\alpha \cdot {(\frac{k-1}{k})}^2$, where $\alpha$ is the approximation ratio for the maximum traveling salesman problem. For the case $k=4$, we design a better $\frac{2}{3}$-approximation algorithm. When the weights of edges obey the triangle inequality, we propose a $\frac{3}{4}$-approximation algorithm and a $\frac{3}{5}$-approximation algorithm for the maximum-weight $k$-cycle packing problem with $k=4$ and $k=5$, respectively. For the maximum-weight $k$-path packing problem with $k=3$ (or $k=5$) with the triangle inequality, we devise an algorithm with approximation ratio $\frac{3}{4}$ and give a tight example.

Learning a fast global model that describes the observed phenomenon well is a crucial goal in the inherently distributed Vehicular Networks. This global model is further used for decision-making, which is especially important for some safety-related applications (i.e., the altering of accident and warning of traffic jam). Most existing works have ignored the network overhead caused by synchronizing with neighbors, which inevitably delays the time for agents to stabilize. In this paper, we focus on developing an asynchronous distributed clustering algorithm to learn the global model, where cluster models, rather than raw data points, are shared and updated. Empirical experiments on a message delay simulator show the efficiency of our methods, with a reduced convergence time, declined network overhead and improved accuracy (relative to the standard solution). This algorithm is further improved by introducing a tolerant delay. Compared to the algorithm without delay, the performance is improved significantly in terms of convergence time (by as much as 47%) and network overhead (by around 53%) if the underlying network is geometric or regular.

In this paper, we study a single machine scheduling problem with due date assignment under a group technology environment. The due dates of jobs are assignable according to the following three methods: the common (CON) due date assignment, the slack (SLK) due date assignment, and the different (DIF) due date assignment. Our objective is to determine a group sequence and job sequences within all groups, together with a due date assignment, to minimize a total cost function including earliness, tardiness, due date assignment and flow time costs, in which all unit costs are different and position-dependent. We present a unified $O(nlogn)$ time algorithm to solve the problem for all the three due date assignment methods.

In machine learning, most models can be transformed into unconstrained optimization problems, so how to solve the unconstrained optimization problem for different objective functions is always a hot issue. In this paper, a class of unconstrained optimization where objection function has $p$th-order derivative and Lipschitz continuous simultaneously is studied. To handle such problems, we propose an accelerated regularized Chebyshev–Halley method based on the Accelerated Hybrid Proximal Extragradient (A-HPE) framework. It proves that convergence complexity of the proposed method is $O({𝜀}^{-\frac{1}{5}})$, which is consistent with the lower iteration complexity bound for third-order tensor methods. Numerical experiments on functions in machine learning demonstrate the promising performance of the proposed method.

It is difficult to balance detection speed and detection accuracy in current methods for sampling on feature maps. We combine the parameterless interpolation algorithm used in the traditional method with the algorithm in deep learning to improve shortcomings of the traditional interpolation algorithm by introducing learnable parameters into the algorithm. The new algorithm guarantees the features of the original image by calculating the correlation between feature map channels and pixels to ensure the correct restoration of the image features during up-sampling. In this paper, we propose a new up-sampling operation model — Reparametric Blend Up-sampling (RBU), which uses the method of rearranging pixels to obtain a feature map that matches the up-sampling size, uses blending to compute inter-pixel and inter-channel correlations and back-propagates the model to learn the appropriate parameters to ensure feature extraction. In the field of object detection, this model replaces the original up-sampling operation and improves the mAP mean value by 1.1% and the detection of small target objects by 3.1% in the VOC dataset with the richest application scenarios.

In this paper, we consider how to maximize the liquid welfare in a combinatorial auction where bidders have monotone valuations and are budget constrained. We study the setting that budgets are public information and present a universally truthful, budget feasible and computationally-efficient randomized $O(\sqrt{mn})$-approximate mechanism, where $m$ is the number of items and $n$ is the number of bidders, respectively.

We are given a set of $m$ identical parallel machines and a set of $n$ jobs in large computing systems, where each job $J_j$ consists of a bag of $b_j$ identical tasks with a processing time $p_j$, and has a rejection penalty $w_j$. Job $J_j$ is either accepted in which case all the $b_j$ tasks must be processed by one of the machines, or rejected which incurs a rejection penalty $w_j$. The problem of bag-of-tasks scheduling with rejection is to find a feasible schedule, so as to minimize the makespan plus the total rejection penalty of all rejected jobs. In this paper, we present a polynomial time approximation scheme.