In this paper, we introduce a new class of generalized convex functions: weakly semi-$E$-convex functions and establish its corresponding weakly semi-$E$-convex programming. We discuss the properties of solutions of weakly semi-$E$-convex programming and give the optimality conditions of weakly semi-$E$-convex programming.
This paper studies the M/M/1 production inventory system with working vacations. The server takes multiple working vacations when there is no customers in the system. Based on the (s, S) inventory strategy, a four-dimensional Markov process of the number of customers in the system, the inventory level, the server state and the production state is established. We obtain the steady-state condition of the system by using quasi-birth-death process theory. Furthermore, we derive the steady-state performance indexes of the system and the system cost function. The effect of various parameters of the system on the performance indexes and inventory strategy is analyzed. Then the optimal inventory strategies and optimal costs with different service rates under working vacation are compared.
Combining cubic regularization and trust region method to solve the subproblem, we propose a second-order splitting algorithm for a class of large scale separable nonconvex optimization problems under inexact Hessian information. The global convergence result is obtained under some mild assumptions. It is proved that the algorithm needs at most $O\left( {{\varepsilon ^{ - 2}}} \right) $ evaluations to produce a $\varepsilon $-approximate stable solution. The algorithm is employed to solve a nonconvex binary classification problem in machine learning with nice numerical experiments results.
The sum-of-linear-products program has appeared in fields such as engineering practice and management science, and it is a class of NP-Hard problems. In view of the special structure of the objective function of this problem, it is reconstructed as a D.C. (difference of convex functions) programming problem. Based on the convex envelope of concave function, a D.C. relaxation subproblem is constructed and decomposed into two convex optimization problems. Then, by combining the D.C. relaxation with the standard bisection method of hyperrectangle, a new branch and bound algorithm is designed, and its theoretical convergence and computational complexity are analyzed. Finally, the effectiveness of the algorithm is verified by a large number of numerical experiments.
In this paper, we present an iterative algorithm to calculate the optimal approximation solution pair of the matrix equations $AXB+CYD=E $with constraint conditions $GX=H $and $\ WY=U$. The idea of the algorithm is to first find the gradient of the objective function $F(X, Y)={{\left\| E-AXB-CYD \right\|}^{2}}$ at the matrix $X $and $Y$, and then project the negative gradient to the convex constraint set respectively to obtain ${{g}_{X}}$ and ${{g}_{Y}}$. Finally, according to the idea of conjugate gradient method, the search directions ${{d}_{X}}$ and ${{d}_{Y}}$ are reconstructed on the feasible domain based on ${{g}_{X}}$ and ${{g}_{Y}}$. The theory shows that the algorithm can obtain the minimal norm least squares solution pair of the matrix equation $AXB+CYD=E $under the constraint conditions in finite iterative steps for any special class of initial matrix pair $({{X}^{(1)}}, {{Y}^{(1)}}) $satisfying the constraint conditions. In addition, the optimal approximation solution pair to a given matrix pair $\left( \bar{X}, \, \bar{Y} \right) $can be obtained by finding the minimal norm least squares solution pair of a new matrix equations $A\tilde{X}B+C\tilde{Y}D=\tilde{E}$, where $\tilde{E}=E-A\bar{X}B-C\bar{Y}D$. Numerical examples show that the algorithm can not only solve the optimal approximation solutions of matrix equations under generalized constraints, but also solve the optimal approximation solutions of equations under special constraints.
This paper studies on-line scheduling problem on two unit flowshop machines, in which there exist unbounded batch processing of two incompatible job families and lookahead intervals. The unit flowshop is that the processing time of any job is 1 at two machines. The jobs arrive on time. The goal is to minimize the maximum completion time of the jobs. At time $t$, the lookahead interval means on-line algorithm can predict the information of arriving workpieces in the interval $(t, t+\beta]$. Incompatible workpieces family means that workpieces belonging to different workpieces family cannot be arranged in the same batch. For this problem, we provide a best possible online algorithm $A_1(\beta)$ of competitive ratio $1+\alpha$ for $0 \leqslant \beta<1$, where $\alpha$ is the positive root of the equation $3 \alpha^{2}+(\beta+2) \alpha+\beta-2=0$.
A class of flexible flow-shop scheduling problem with due-dates is studied by using cooperative games theory. In this problem, jobs with an initial scheduling order need to be processed successively on multiple processes. There are multiple identical parallel machines at each processing stage. The cost of customer who owns one job is the sum of the job's weighted completion time and tardiness penalty. The scheduling objective is to minimize the sum of customers' costs. Considering that customers can collaborate to form coalitions and reschedule within coalitions to save costs, a cooperative game model is established. In this model, the customers can be seen as the players and the maximum cost savings obtained by rescheduling can be seen as the characteristic function. By analyzing the properties of cooperative games, the reasonable allocations of cost savings are used to reduce the customer's cost. When the jobs have identical processing time on the same processing stage and common due date, it is proved that the corresponding cooperative games are convex. Core allocations can be obtained by the $\beta$ rule and the Shapley value, and the Shapley value can be expressed in a simple form. Examples are given to verify the properties of the cooperative games and rationality of the cost allocation methods.
The optimization of refinery operations is a critical issue within the crude oil supply chain, garnering extensive research and application interest across both academic and industrial sectors. Typically, refinery optimization problems are modeled as Mixed Integer Non-Linear Programming (MINLP) problems. The complexity of these problems arises from the vast diversity of crude oil types and their derivative products, coupled with intricate processing procedures. Moreover, specific processing steps involve changes in material properties and rules, introducing non-convex, nonlinear, and integer constraints, which increase the solution-finding difficulty. Currently, academic research primarily focuses on modeling and solving small-scale issues or subsystems of operational processes. Commercial solvers like BARON and DICOPT in GAMS are commonly employed for such tasks. This paper introduces a Hybrid Distribution Recursion and Branch and Bound algorithm (Hybrid-DRBB) for solving MINLP in refinery optimization. This method relaxes and solves nonlinear and integer constraints separately, thereby obtaining near-optimal solutions for the original problem. Through numerical experiments utilizing real-world, large-scale data scenarios, we demonstrate the efficiency of our method in comparison to traditional commercial solvers, highlighting its reduced computational cost and improved solving approach.
It is well known that alternating direction method of multipliers (ADMM) and its variants are of the popular methods in solving many practical problems. However, the efficiency of ADMM based methods largely relies on the solvability of the involving subproblems. In this paper, we propose an inexact generalized proximal ADMM with optimal indefinite proximal term to solve the separable convex minimization problem with linear constraints. The relative-error criterion with only one constant belonging in [0, 1) is introduced to solve one of subproblems approximately, and the other subproblem is solved by introducing an optimal indefinite proximal term. The proposed method inherits the advantages of both the relative error criterion and the indefinite proximal term. Based on the variational inequality framework, the convergence of the developed method is rigorously conducted. Some numerical experiments on TV-$\ell $2 image restoration problem are conducted to illustrate the efficiency of the new method.
For a given set of jobs and a given set of machines, we assign the jobs to the machines without preemption. The early work maximization problem tries to find a schedule such that the total early work of the jobs is maximized, where the early work of a job is the processed time before the common due date. We prove that the worse-case ratio of LPT algorithm is at most 1.207.
In order to improve the utilization of resources and shorten the delivery time of customer orders, this paper discusses the online scheduling problem of batch processing machine with limited batch capacity. In the scenario of on-time release time of orders, an online scheduling model with different types of orders, only orders of the same type that can be grouped into batches and the processing time of batch which depends on the type of order is studied. Besides, if two consecutive batches belong to different types, there is a fixed setup time between them. Taking the total revenue as the optimization objective, two processing cases are investigated. As for the online model of a single batch processing machine, the lower bound of the problem is proved to be $ 1+w$, in which $ w$ is the largest revenue of a batch. At the same time, an online algorithm which considers setup time is designed, and the competitive ratio of the online algorithm proved by the Worst Case Analysis method is equal to the lower bound, which shows that the algorithm has the optimal competition. For the case of two parallel batch processing machines, an online algorithm with competitive ratio of $ 1+2\sqrt{w}$ is proposed. The results of the paper can be used to guide the design of efficient online scheduling scheme in practice.
Border security has always been a topic sparking intense debate. Moreover, border morphology realities separating countries are quite complex, exacerbating the complexity of border defence issues. As per relevant literature reviews, there is no perfect universal solution to address border defence problems, which makes it a matter of utmost concern. This paper aims to transform the problem into a pursuit-evasion differential game problem by delineating the border defence scenario. The method of differential game is subsequently used to solve the optimal strategy of the players, which ultimately yields a feasible algorithm. Specifically, this paper uses simple motion to describe player movement in the game, utilises the general equation form of the quadratic curve to demarcate the shape of the boundary, and defines the payoff function as the distance from the capture point to the boundary. The problem is studied by the geometric method, and a more concise value function form is yielded in the case of a circular boundary. The optimal strategy of the player in the game is ultimately constructed. A general algorithm for the quadratic curve boundary is further obtained based on the circular boundary. The model is then stretched from the game of degree to the game of kind, from two dimensions to three dimensions, from M-pursuers against a single evader to M-pursuers against N-evaders, and the result and algorithm are validated by using a numerical simulation.
The scheduling problem with operator non-availability periods and deteriorating jobs on a single machine is studied in this paper. The objective is to minimize the total weighted completion time. Unlike scheduling with machine non-availability constraints, a job can be processed in the operator non-availability time interval but can neither start nor complete in this period. We first show that there exists no polynomial-time approximation algorithm with a constant worst-case bound when the problem has two operator non-availability periods unless P=NP. We then present a pseudo-polynomial time algorithm and a fully polynomial-time approximation scheme (FPTAS) when there exists only one operator non-availability period.
Let $\mathcal{F}$ be a family of graphs. If $G$ does not contain every graph in $\mathcal{F}$ as a subgraph, then $G$ is said to be $\mathcal{F}$-free. The Turán number $ex(n, \mathcal{F})$ is defined to be the maximum number of edges in a graph on $n$ vertices that is $\mathcal{F}$-free. A linear forest is a graph whose connected components are all paths or isolated vertices. Let $\mathcal{L}_{n, k}'$ be the family of all linear forests of order $n$ with $k$ edges except $P_{k+1}\cup(n-k-1)K_1$. In this paper, we give Turán number of $\mathcal{L}_{n, k}'$ and corresponding extremal graphs. Furthermore, we give the maximum spectral radius of graphs of order $n$ that are $\mathcal{L}_{n, k}'$-free and the corresponding extremal graphs.
If the cost is generated in switching strategies of games, the best reply strategy of some players can be not maximize their payoffs. In order to improve weak Nash equilibrium, this paper introduces a more general cost function with switching strategies under population games model, and the new weak Nash equilibria contain Nash equilibria. In addition, according to replication dynamics, we obtain the stability of weak Nash equilibrium state in single-population game induced by the \times2$ symmetric matrix game with switching strategy cost. By simulation, it is easy to show that evolutionary stable state also is increased compared without switching strategies cost.
