Search

We consider the Pareto-scheduling of two competing agents on a single machine, in which the jobs of each agent have their “own equal processing times” (shortly, OEPT). In the literature, two special versions of the OEPT model, in which the jobs have either unit or equal processing times, have been well studied, where the criteria are given by various regular objective functions without including the late work criteria. However, for equal processing times, the exact complexity of three problems is still unaddressed. Two-agent scheduling related to late work criteria is also a hot topic in recent years. This inspires our research by also including the total (weighted) late work as criteria. We show that, for equal processing times, all the problems are binary NP-hard if the criterion of one agent is the total tardiness or the total late work and the criterion of the other agent is either the total tardiness or the total late work or the weighted number of tardy jobs or the total weighted completion time. As a result, complexity classification for equal processing times is completely addressed. We further show that all the problems under the OEPT model are either polynomially solvable or ordinary NP-hard, which results in a complete complexity classification for the OEPT model.

Lapping has a history of hundreds of years, yet it still relies on the experience of workers. To improve the automaticity and controllability of the lapping process, a modeling method of friction and wear is developed to predict the surface profile evolution of the workpiece and lapping plate in the lapping process. In the proposed method, by solving the balance equations of resultant force and moment, the inclination angles of the workpiece can be calculated; thus, a more accurate contact pressure distribution of the workpiece/lapping plate interface can be calculated. Combined with the material removal rate model, the continuous evolution process of the workpiece and lapping plate can be predicted in the lapping process. The modeling method was validated by a lapping test of a flat optical glass workpiece (Φ 100 mm) with a composite copper plate. The results show that the proposed method can predict the evolution of the surface profile of the workpiece and lapping plate with high accuracy. Consequently, the lapping plate can be dressed at the right time point. Benefit from this, in the validation test the Peak to Valley (PV) value of the workpiece (with 5 mm edge exclusion) was reduced from 5.279 µm to 0.267 µm in 30 min. The proposed surface profile evolution modeling method not only improves the lapping efficiency but also provides an opportunity to understand the lapping process.

In this paper, we study the single-machine Pareto-scheduling of jobs with multiple weighting vectors for minimizing the total weighted late works. Each weighting vector has its corresponding weighted late work. The goal of the problem is to find the Pareto-frontier for the weighted late works of the multiple weighting vectors. When the number of weighting vectors is arbitrary, it is implied in the literature that the problem is unary NP-hard. Then we concentrate on our research under the assumption that the number of weighting vectors is a constant. For this problem, we present a dynamic programming algorithm running in pseudo-polynomial time and a fully polynomial-time approximation scheme (FPTAS).

We investigate the Pareto-scheduling problem with two competing agents on a single machine to minimize the total weighted completion time of agent A&rsquo, s jobs and the total weighted late work of agent B&rsquo, s jobs, the B-jobs having a common due date. Since this problem is known to be NP-hard, we present two pseudo-polynomial-time exact algorithms to generate the Pareto frontier and an approximation algorithm to generate a (1+ϵ)-approximate Pareto frontier. In addition, some numerical tests are undertaken to evaluate the effectiveness of our algorithms.

Ambient temperature produces great effects on battery state-of-charge (SOC) estimation, due to the unstable estimation algorithm, the weakened traceability of battery model, and variable model parameters at various temperatures, especially lower temperatures. The widely used method based on the equivalent circuit model (ECM) offline in using different algorithm, like current integral, the extended Kalman filter (EKF), or the unscented Kalman filter (UKF), can obtain an accurate SOC estimation at room temperature, but it is difficult to guarantee the high precision at lower temperatures. To address this problem, the battery model is investigated at different temperature, and an offset item is proposed to develop the observer equation in the estimated model. Then, the square root of the Sigma points Kalman filter (SR-UKF) is applied, and on the basis of the individual model parameter-temperature table and the developed model, the high accuracy of SOC estimation is achieved. Additionally, considering the burden of original parameter modification (all model parameters modified) at various temperature which will increase the product cost and computational complexity of the battery management system (BMS), the relationship between individual model parameter and the error of SOC estimation is built, which is helpful for the simplification of parameter modification. The results indicate that the proposed method based on the developed estimated model and the simplified parameter modification can achieve an accurate, stable, and efficient SOC estimation.

This paper investigates the scheduling of family jobs with release dates on an unbounded parallel-batch machine. The involved objective functions are makespan and maximum flow time. It was reported in the literature that the single-criterion problem for minimizing makespan is strongly NP-hard when the number of families is arbitrary, and is polynomially solvable when the number of families is fixed. We first show in this paper that the single-criterion problem for minimizing maximum flow time is also strongly NP-hard when the number of families is arbitrary. We further show that the Pareto optimization problem (also called bicriteria problem) for minimizing makespan and maximum flow time is polynomially solvable when the number of families is fixed, by enumerating all Pareto optimal points in polynomial time. This implies that the single-criterion problem for minimizing maximum flow time is also polynomially solvable when the number of families is fixed.

This paper investigates the ND-agent scheduling of linear-deteriorating tasks on a single machine with positional due indices. Under the ND-agent setting, there are two agents A and B and each agent X ∈ {A, B} has its set of tasks T ( X ) , called X-tasks. Moreover, ND-agent means that T ( A ) and T ( B ) are allowed to be non-disjoint, which is a generalization of the traditional two-agent setting. Each task has a linear-deteriorating processing time and a positional due index. In this paper, we consider two problems: The first problem is to find a feasible schedule which minimizes the total completion time of the A-tasks under the condition that the maximum cost of the B-tasks is bounded by a threshold value. The second problem is the Pareto scheduling problem to minimize the total completion time of the A-tasks and the maximum cost of the B-tasks, simultaneously. We show in this paper that the two problems are solvable in O(n2) time and in O(n4) time, respectively. If the maximum cost of the tasks of agent B is restricted to some lateness-like criteria, for the version without the positional restriction, the time complexity for solving the above two problems can be reduced to O(nlog n) and O(n3log n), respectively. Our research includes a new technique for calculating the number of non-dominated points.

In this paper, we consider two problems about the preemptive scheduling of a set of jobs with release times on a single machine. In the first problem, each job has a deadline. The objective is to find a feasible schedule which minimizes the total completion time of the jobs. In the second problem (called two-agent scheduling problem), the set of jobs is partitioned into two subsets $$\mathcal{J}^{(1)}$$J(1) and $$\mathcal{J}^{(2)}$$J(2). Each job in $$\mathcal{J}^{(2)}$$J(2) has a deadline. The objective is to find a feasible schedule which minimizes the total completion time of the jobs in $$\mathcal{J}^{(1)}$$J(1). For the first problem, Du and Leung (Journal of Algorithms 14:45---68, 1993) showed that the problem is NP-hard. We show in this paper that there is a flaw in their NP-hardness proof. For the second problem, Leung et al. (Operations Research 58:458---469, 2010) showed that the problem can be solved in polynomial time. Yuan et al. (Private Communication) showed that their polynomial-time algorithm is invalid so the complexity of the second problem is still open. In this paper, by a modification of Du and Leung's NP-hardness proof, we show that the first problem is NP-hard even when the jobs have only two distinct deadlines. Using the same reduction, we also show that the second problem is NP-hard even when the jobs in $$\mathcal{J}^{(2)}$$J(2) has a common deadline $$D>0$$D>0 and a common release time 0.

We present fastHan, an open-source toolkit for four basic tasks in Chinese natural language processing: Chinese word segmentation (CWS), Part-of-Speech (POS) tagging, named entity recognition (NER), and dependency parsing. The backbone of fastHan is a multi-task model based on a pruned BERT, which uses the first 8 layers in BERT. We also provide a 4-layer base model compressed from the 8-layer model. The joint-model is trained and evaluated on 13 corpora of four tasks, yielding near state-of-the-art (SOTA) performance in dependency parsing and NER, achieving SOTA performance in CWS and POS. Besides, fastHan's transferability is also strong, performing much better than popular segmentation tools on a non-training corpus. To better meet the need of practical application, we allow users to use their own labeled data to further fine-tune fastHan. In addition to its small size and excellent performance, fastHan is user-friendly. Implemented as a python package, fastHan isolates users from the internal technical details and is convenient to use. The project is released on Github., ACL2021 Demo Track