Loading...

Table of Content

    15 March 2025, Volume 29 Issue 1
    A survey of scheduling with maintenance periods
    Yuan YUAN, Yan LAN, Xin HAN
    2025, 29(1):  1-18.  doi:10.15960/j.cnki.issn.1007-6093.2025.01.001
    Asbtract ( 110 )   HTML ( 0)   PDF (685KB) ( 63 )  
    Figures and Tables | References | Related Articles | Metrics

    In recent years, scheduling problems with maintenance periods have been attracting more and more researchers in the field of operational research. There are four types of maintenance period in the scheduling literature: fixed maintenance period, flexible maintenance period, floating maintenance period and rate-modifying maintenance period. At present, the vast majority of results have been arising about the scheduling problems with maintenance period, but there is no paper to summarize them. To be convenient for interested researchers, we make a summary about scheduling problems with maintenance period. In this paper, complexity results, exact algorithms and approximation algorithms in single machine, flow shop and open shop scheduling environment with different target are surveyed briefly.

    Study on the production scheduling of prefabricated components with learning effect
    Na LI, Ran MA, Long LI, Yuzhong ZHANG
    2025, 29(1):  19-30.  doi:10.15960/j.cnki.issn.1007-6093.2025.01.002
    Asbtract ( 80 )   HTML ( 0)   PDF (656KB) ( 45 )  
    Figures and Tables | References | Related Articles | Metrics

    The single machine online scheduling problem with learning effect in prefabricated component production environment is provided to minimize the maximum weighted completion time in this paper. More precisely, it asks for an assignment of a series of independent prefabricated jobs arrived over time to a single machine, where the information of each prefabricated job including its basic processing time bj, release time rj, and positive weight wj is unknown in advance and is disclosed upon the arrival of this job. And the actual processing time of prefabricated job Jj with learning effect is pj = bj(abt), where a and b are non-negative parameters and t is the starting time of prefabricated job Jj. In particular, a job may not be interrupted, i.e., preemptive is not allowed, and the machine can process at most one job at a time. Firstly, the off-line optimal schedule of the problem is analyzed. Then, we investigate this schedule model in the online environment where jobs arrive online over time. Fortunately, we propose a deterministic online algorithm, and show that the online algorithm is best possible with a competitive ratio of 2 − bbmin, where bmin = min {bj|1 ≤ jn}. Furthermore, the effectiveness of the online algorithm is demonstrated by numerical experiments.

    Single two-agent scheduling problems with slack due date to minimize the total weighted tardiness
    Tongxin CUI, Qian XIA, Xingong ZHANG
    2025, 29(1):  31-40.  doi:10.15960/j.cnki.issn.1007-6093.2025.01.003
    Asbtract ( 70 )   HTML ( 1)   PDF (589KB) ( 20 )  
    Figures and Tables | References | Related Articles | Metrics

    This paper studies the scheduling problems with two competing agents on a single machine to minimize the total weighted tardiness under slack due date, where the slack due date of the job is equal to its actual processing time plus a certain slack variable. It includes two models: the first model is to minimize the total weighted tardiness of the first agent under the condition that the total number of tardiness jobs of the second agent does not exceed a given value; the second model is to minimize the total weighted tardiness of the first agent that the total completion time of the second agent does not exceed a given value. The optimal properties are given by dynamic programming. The pseudo-polynomial time algorithm and its time complexity is presented. Finally, two experiment examples are given to illustrate the feasibility of the algorithm.

    A new algorithm for improving the completion performance of knowledge graph of long-tail data
    Miaohui HE, Xuxiang DUAN, Zhiyou WU
    2025, 29(1):  41-54.  doi:10.15960/j.cnki.issn.1007-6093.2025.01.004
    Asbtract ( 100 )   HTML ( 0)   PDF (781KB) ( 33 )  
    Figures and Tables | References | Related Articles | Metrics

    Knowledge graph is an important semantic data in many intelligent applications, but the incompleteness of its data brings many difficulties to practical applications. Therefore, it is necessary to complete the missing semantic information in the knowledge graph. Knowledge graph embedding is one of the important methods of knowledge graph completion. This type of method usually has better results in the case of non-long-tail data, but its effect is poor in the case of long-tail data. Since the semantics of non-long-tail data is richer, in order to improve the effect of knowledge graph completion in the case of long-tail data, this paper transfers non-long-tail data as supervised knowledge to long-tail data, and proposes a new algorithm——the dual embedding method with the idea of expectation maximization algorithm, to improve the completion performance of knowledge graph, and its practical application effect. Through the comparative experiment of link prediction task in FB15K data set, the experimental results show that the dual embedding method with the idea of expectation maximization algorithm proposed in this paper is effective.

    The inspection and preventive maintenance policy for a δ-shock model which has two types of failures
    Qiaoqiao GAO, Dequan YUE
    2025, 29(1):  55-62.  doi:10.15960/j.cnki.issn.1007-6093.2025.01.005
    Asbtract ( 76 )   HTML ( 0)   PDF (732KB) ( 18 )  
    Figures and Tables | References | Related Articles | Metrics

    In this paper, the preventive maintenance policy for a δ-shock model is studied. The system is a geometric process degradation system. The failure of the system on the one hand is because of the lifetime of the system, on the other hand is because of the interval of two consecutive shocks less than a fixed value. The fault of the system can only be found by inspection. When the working time of the system reaches a certain value, the inspect will be carried out, and preventive maintenance will be carried out if there is no fault. Preventive maintenance will restore the system to the state after the last fault maintenance, and if the system fault, a fault repair will be carried out. Based on the two-dimensional policy composed of the interval of system detection and the failure times before replacement, the expression of the expected cost per unit time of system is obtained by using the renewal process and geometric process theory. Finally, numerical examples are given.

    Partial order analysis method for multiple criteria sensitivity
    Lizhu YUE, Liwei YAO, Yahua CUI, Ke XU
    2025, 29(1):  63-76.  doi:10.15960/j.cnki.issn.1007-6093.2025.01.006
    Asbtract ( 81 )   HTML ( 0)   PDF (769KB) ( 28 )  
    Figures and Tables | References | Related Articles | Metrics

    The sensitivity analysis method of multiple criteria decision making is mainly constructed by weight perturbation. When weight assignment is difficult or disputes occur, the evaluation results are often not robust enough. Partial order sensitivity analysis takes decision function as objective function and weight space as constraint condition to establish programming problem, and constructs the partial order relationship between schemes with the help of extreme point set. Ultimately, Hasse diagram is used to express the possible change results and the sensitivity of schemes and indicators is obtained. By changing the weight space, the partial order method can construct a variety of sensitivity analysis methods suitable for global, local and finite. The example application shows that the partial order results of the three kinds of sensitivity analysis are completely consistent with the simulation results, which reflects the effectiveness and uniqueness of the partial order method.

    Efficiency evaluation for the serial system in the absence of a given leader-follower order in the non-cooperative case
    Yao WEN, Junhua HU
    2025, 29(1):  77-97.  doi:10.15960/j.cnki.issn.1007-6093.2025.01.007
    Asbtract ( 71 )   HTML ( 0)   PDF (1226KB) ( 38 )  
    Figures and Tables | References | Related Articles | Metrics

    In the non-cooperative case, among the studies of efficiency evaluation of serial systems using data envelopment analysis (DEA) method, the excellent leader-follower or non-cooperative network DEA model can provide a unique evaluation result for the serial system and their internal sub-systems. However, the premise is a given leader-follower order that reveals which stage is more important for improving system's efficiency. Different leader-follower orders yield various evaluation results and not necessarily all systems obtain their best efficiency in the same order. Furthermore, existing studies on network DEA mostly look decision makers completely rational, which is not in line with the bounded rational behavior in practice. This study focuses on the question of "In the non-cooperative case without a given leader-follower order, how to evaluate efficiencies of the serial system and its internal sub-systems". To answer this question, we propose a novel approach for measuring efficiencies of the serial system and its sub-systems based on a lexicographical optimization approach and the prospect theory, considering the bounded rationality of decision makers and all leader-follower orders. This method can provide a unique, comprehensive, and comparable efficiency composition result. The experiment with the data of 14 electric power companies is used to validate this method.

    On the upper bounds of inverse signed total domination number
    Huahui SHANG, Lianying MIAO
    2025, 29(1):  98-104.  doi:10.15960/j.cnki.issn.1007-6093.2025.01.008
    Asbtract ( 68 )   HTML ( 0)   PDF (455KB) ( 20 )  
    References | Related Articles | Metrics

    The upper bounds of the inverse signed total domination number are studied. By sets analysis and optimizing, relations between degree, odd set and size are established. Furthermore, five upper bounds of inverse signed total domination number of graphs are obtained, and the graphs satisfying these bounds are given respectively.

    An approximation theorem for n-person non-cooperative games under uncertain parameters
    Congli CHEN, Hui YANG, Guanghui YANG, Chun WANG
    2025, 29(1):  105-113.  doi:10.15960/j.cnki.issn.1007-6093.2025.01.009
    Asbtract ( 51 )   HTML ( 0)   PDF (616KB) ( 14 )  
    References | Related Articles | Metrics

    In this paper, suppose that the range of varying uncertain parameters is known, an approximation theorem for n-person non-cooperative games with uncertain parameters is investigated. Based on the idea of bounded rationality, we prove the approximation theorem of n-person non-cooperative games with uncertain parameters, which provides a theoretical support for solving algorithm of NS-equilibria. In addition, we verify the rationality of this conclusion through a specific example.

    A class of pursuit-evasion game problems considering the influence of sliding friction
    Min HOU, Yang YU, Zhaopeng DAI, Lujing JING, Hongwei GAO
    2025, 29(1):  114-126.  doi:10.15960/j.cnki.issn.1007-6093.2025.01.010
    Asbtract ( 75 )   HTML ( 1)   PDF (724KB) ( 16 )  
    Figures and Tables | References | Related Articles | Metrics

    Based on the homicidal chauffeur game, one of the classic models of the pursuit-evasion game problem, this paper investigates the capture area of the game problem that is affected by the sliding friction when the car turns. The classic homicidal chauffeur game deals with the speed of a car turning a corner based on the ideal assumption of a sufficiently rough ground. However, in real sports, different ground roughness will have different effects on the speed of the car when cornering. In this paper, a model is established to give a new description of the speed of the car in the process of chasing and fleeing, to solve the optimal strategy, to analyze the changes in the capture area compared with the classic homicidal chauffeur game and to explain the reasons. The main conclusions can be used for land pursuit, space combat and other realistic scenes.

    Robust optimal investment and benefit payment adjustment strategy for target benefit pension plans with stochastic salary
    Xinru ZHANG, Shixia MA, Yumeng ZHANG, Rui MU
    2025, 29(1):  127-141.  doi:10.15960/j.cnki.issn.1007-6093.2025.01.011
    Asbtract ( 72 )   HTML ( 0)   PDF (712KB) ( 33 )  
    Figures and Tables | References | Related Articles | Metrics

    This paper considers the optimal investment and benefit payment problem with default risk and model uncertainty under target benefit plans~(TBPs). The pension funds can be invested in a risk-free asset, a stock whose price process follows Heston model and a defaultable bond. In particular, the salary of TBPs members is stochastic. Using the stochastic optimal control approach, we derive the robust optimal strategies as well as the corresponding value functions in the post-default and pre-default, respectively. Besides, we also consider the optimal strategies for the non-ambiguity case. Finally, numerical analysis is provided to illustrate the effects of parameters on the optimal strategies, which provides an effective decision-making basis for pension managers.

    Stochastic scheduling to minimize the expected total number of tardy jobs with machine maintenance activities
    Shipian DU, Manzhan GU
    2025, 29(1):  142-158.  doi:10.15960/j.cnki.issn.1007-6093.2025.01.012
    Asbtract ( 66 )   HTML ( 1)   PDF (707KB) ( 21 )  
    Figures and Tables | References | Related Articles | Metrics

    This paper studies the single machine stochastic scheduling problem with multiple machine maintenance activities, where all the jobs have the same processing time and due date which is a random variable. The goal is to determine the number of workshops and the number of jobs processed in each workshop so as to minimize the expected total number of tardy jobs. In the case where the due date follows the exponential distribution and the maintenance time function is concave, some properties of the optimal schedule are introduced, based on which the optimal schedule is proposed. Moreover, an optimal algorithm is proposed in the case where the due date follows the uniform distribution and the maintenance time function is a linear function.

    Equilibrium analysis of a fault fluid model with two types of customers and disaster arrival
    Lei YANG, Xiuli XU
    2025, 29(1):  159-171.  doi:10.15960/j.cnki.issn.1007-6093.2025.01.013
    Asbtract ( 63 )   HTML ( 1)   PDF (1092KB) ( 15 )  
    Figures and Tables | References | Related Articles | Metrics

    This paper makes an economic analysis of a complete fault fluid model with two types of customers and disaster arrival. Disaster arrival will empty the system and force customers to leave. Suppose that the arriving customers decide whether to enter or not according to the "benefit-loss" utility function. The system of linear differential equations is constructed, and the individual balking threshold and the social benefit function per unit time are obtained by using the matrix analysis method at both fully observable and almost observable levels of information. Finally, the influence of parameters on social benefit is discussed through numerical examples.

    An inertial alternating direction method of multiplier for low rank matrix completion
    Xihong YAN, Xiaoni TANG
    2025, 29(1):  172-184.  doi:10.15960/j.cnki.issn.1007-6093.2025.01.014
    Asbtract ( 75 )   HTML ( 1)   PDF (2554KB) ( 30 )  
    Figures and Tables | References | Related Articles | Metrics

    The alternating direction method of multiplier is attractive for solving matrix completion problems, which has the advantage of being able to decompose a minimization problem into many smaller and easier subproblems. Therefore, it is popular in the field of image processing and data analysis in recent years. Based on the framework of the alternating direction method of multiplier, we combine the inertial strategy and propose an inertial accelerated alternating direction method of multiplier to solve the matrix completion problems in this paper. In each iteration of the new method, for some of variables, the iterative points of the previous two iterations of the alternating direction method of multiplier are extrapolated to obtain the new iteration points, which improve the computational efficiency of the new method. Under the reasonable assumptions, we prove convergence of the new method. Finally, we also verify the effectiveness and feasibility of the new method by numerical experiments of random matrix completion and an example of image restoration.

    The extremal k-uniform hypergraphs with given number of pendent vertices on signless Laplacian spectral radius
    Yu YANG, Zhongxun ZHU, Junpeng ZHOU
    2025, 29(1):  185-197.  doi:10.15960/j.cnki.issn.1007-6093.2025.01.015
    Asbtract ( 64 )   HTML ( 0)   PDF (841KB) ( 14 )  
    Figures and Tables | References | Related Articles | Metrics

    For a $k$-uniform hypergraph $H=(V, E)$, let $B(H)$ be its incidence matrix and $\mathcal{Q}(H)=B(H)B(H)^{\top}$ be its signless Laplacian matrix. The signless Laplacian spectral radius of $H$ is the maximum modulus of all eigenvalues of $\mathcal{Q}(H)$. Let $\mathcal{H}^n_{k, r}$ be the class of connected $k$-uniform hypergraphs with $n$ vertices and $r$ pendent vertices. In this paper, the extremal hypergraphs having maximum spectral radii in $\mathcal{H}^n_{k, r}$ are characterized for $n-r\geq k$ and some cases $n-r\in [k-1]$, respectively.

    Total forcing and zero forcing of unicyclic graphs
    Baoxin LI, Shengjin JI
    2025, 29(1):  198-206.  doi:10.15960/j.cnki.issn.1007-6093.2025.01.016
    Asbtract ( 60 )   HTML ( 1)   PDF (715KB) ( 20 )  
    Figures and Tables | References | Related Articles | Metrics

    Let $S\subseteq V$ be an initial vertex subset of coloring, and all vertices of $S\subseteq V$ are black. Each vertex in $S$ is called $S$-colored, and all other vertices in $G$ are called $S$-uncolored. If a vertex $v$ with black color has just one uncolored neighbor $u$, then $v$ forces the vertex $u$ to be black. Such a process is called forcing process. The initial set $S$ is called a zero forcing set (forcing set) of $G$ if, by iteratively applying the forcing process, every vertex in $G$ becomes black. The minimum cardinality of a zero forcing set in $G$ is zero forcing number, denoted $F(G)$. If the induced subgraph $G[S]$ does not contain isolated vertices, then $S$ is called a total forcing set of $G$, and the minimum cardinality of a total forcing set in $G$ is total forcing number, denoted $F_t(G)$. Note that zero forcing number and total forcing number of graph $G$ has the relation, $F(G)\leq F_t (G)\leq 2F(G)$. Hence, it is interesting and meaningful to characterize all graphs satisfying $F(G)=F_t (G)$ or $2F(G)=F_t (G)$. In this paper, we study all graphs $G$ satisfying $F(G)=F_t (G)$ in unicyclic graphs. In addition, we discuss the upper bound of zero forcing number in all unicyclic graphs with given matching number $k$, and show that $F(G)\leq n-k$ and equality holds if and only if $G\cong C_4, A_0$. Moreover, we characterize all graphs such that their forcing number equal to $n-k-1$ if $G\not\cong C_4, A_0$.

    On harmonic index of trees with fixed domination number
    Xiaoling SUN, Yubin GAO, Jianwei DU
    2025, 29(1):  207-215.  doi:10.15960/j.cnki.issn.1007-6093.2025.01.017
    Asbtract ( 62 )   HTML ( 0)   PDF (488KB) ( 15 )  
    References | Related Articles | Metrics

    In order to predict the physical, chemical properties and biological activities of molecules, scientists have proposed many topological indices. As a variant of the well known Randićindex, the harmonic index is proven to be a valuable predictive index in the study of the physical and chemical properties of compounds. The harmonic index of trees with fixed domination number was investigated. By analyzing the structure of trees with fixed domination number and using the method of mathematical induction, the maximum and minimum harmonic indices of trees with fixed domination number are presented. Furthermore, the corresponding extremal trees are determined.

    Steiner k-hyper Wiener index of graph products
    Chaoping WANG, Mengmeng LIU
    2025, 29(1):  216-224.  doi:10.15960/j.cnki.issn.1007-6093.2025.01.018
    Asbtract ( 67 )   HTML ( 0)   PDF (561KB) ( 10 )  
    Figures and Tables | References | Related Articles | Metrics

    Let G be a connected graph. For $ 2\leqslant k\leqslant n-1$, the Steiner k-hyper Wiener index $ {\rm SWW}_{k}(G)$ is defined as ${\rm SWW}_{k}(G)=\frac{1}{2}\sum_{S\subseteq V(G), |S|=k}d_{G}(S)+\frac{1}{2}\sum_{S\subseteq V(G), |S|=k}d_{G}(S)^{2} $, where $d_{G}(S) $ is the Steiner distance of S, means the minimum size of a connected subgraph which vertex set contains S. In this paper, we establish expressions for the Steiner k-hyper Wiener index on the join and lexicographical product of graphs and give lower bounds for the Steiner $k$-hyper Wiener index on cartesian, cluster and corona product of graphs.

    The lower limit of the independence number in edge chromatic critical graphs
    Linming QI, Weiliang ZHAO, Lianying MIAO
    2025, 29(1):  225-231.  doi:10.15960/j.cnki.issn.1007-6093.2025.01.019
    Asbtract ( 64 )   HTML ( 0)   PDF (538KB) ( 28 )  
    References | Related Articles | Metrics

    In 1968, Vizing conjectured for any edge chromatic critical graph $G$ with maximum degree $\Delta$ and independence number $\alpha(G)$, $\alpha(G)\leqslant\dfrac{n}{2}$. This conjecture is still open. In this paper, we proved that $\alpha(G)\leqslant\dfrac{7\Delta-6}{12\Delta-6}|V|$ for $\Delta\in\{3, 4, 5, 6\} $ and $\alpha(G)\leqslant \dfrac{4\Delta-3}{7\Delta-3}|V|$ for $\Delta\in\{7, 8, 9\}$.

    Gallai's conjecture for complete bipartite graphs
    Xianya GENG, Hui CHAI
    2025, 29(1):  232-238.  doi:10.15960/j.cnki.issn.1007-6093.2025.01.020
    Asbtract ( 74 )   HTML ( 0)   PDF (516KB) ( 21 )  
    Figures and Tables | References | Related Articles | Metrics

    Let $G$ be a connected simple graph on $n$ vertices. The Gallai's conjecture (1966) asserts that every simple connected graph $G$ on $n$ vertices can be decomposed into at most $\left\lceil\frac{n}{2}\right\rceil$ paths. In this paper, we prove that Gallai's conjecture is true for each complete bipartite graph $K_{n_1, n_2}, $ where 1≤n2 < n1 and n1 is odd. Together with the conclusions of [1], we show that Gallai's conjecture holds for all complete bipartite graphs.