Loading...

Table of Content

    15 December 2024, Volume 28 Issue 4
    Analysis of M/G/1 queue with single vacation and modified (p, N)-policy
    Yanjun LUO, Yinghui TANG
    2024, 28(4):  1-17.  doi:10.15960/j.cnki.issn.1007-6093.2024.04.001
    Asbtract ( 336 )   HTML ( 5)   PDF (941KB) ( 48 )  
    Figures and Tables | References | Related Articles | Metrics

    This paper considers an $M/G/1$ queueing model with single vacation and modified $(p, N)$-policy. The modified $(p, N)$-policy means that when the vacation ends and the server returns to the system, if there are less than $N$ customers but at least one customer in the system, the server begins service with probability $p (0 \le p \le 1)$ or stays idle with probability $(1-p)$ until there are $N$ customers in the system and starts its service at once. By the renewal process theory, total probability decomposition technique and Laplace transform tool, we study the transient queue length distribution of the system, and obtain the expressions of the Laplace transform of the transient queue length distribution with respect to time $t$. Then, employing L'Hospital's rule and some algebraic manipulations, the recursive formulas of the steady-state queue length distribution are derived. Meanwhile, the explicit expressions for probability generating function of the steady-state queue length distribution and the expected queue size are presented. Finally, employing the renewal reward theorem, the explicit expression of the long-run expected cost per unit time is also presented. Numerical examples are provided to discuss the optimal control policy $N^*$ for economizing the system cost as well as the optimal two-dimensional control policy $(N^*, T^*)$ when the vacation time is a fixed length $T (T \ge 0)$.

    Research on the NDP-constraint online scheduling of jobs have agreeable processing times and delivery times
    Wenjie LI, Zhihui DU, Menglong SU
    2024, 28(4):  18-28.  doi:10.15960/j.cnki.issn.1007-6093.2024.04.002
    Asbtract ( 345 )   HTML ( 4)   PDF (766KB) ( 28 )  
    References | Related Articles | Metrics

    This paper studies the single-machine online schedule under the NDP-constraint to minimize the maximum delivery completion time. Here "NDP-constraint" means that the idle machine must schedule the available jobs at any time, i.e., the available jobs cannot be delayed for processing. In this paper, we study the restricted version in which the jobs have agreeable processing times and delivery times (if $p_{i}\geq p_{j}$, then $p_{i}\geq p_{j}$). we first present a lower bound of 4/3 and then design an online algorithm with the competitive ratio of 1.382.

    Research on the multi-objective model and algorithm for aircraft takeoff/landing scheduling based on rank 2 matrix approximation
    Bo XU, Weimin MA, Hua KE, Hao ZHANG
    2024, 28(4):  29-43.  doi:10.15960/j.cnki.issn.1007-6093.2024.04.003
    Asbtract ( 395 )   HTML ( 2)   PDF (976KB) ( 29 )  
    Figures and Tables | References | Related Articles | Metrics

    The aircraft takeoff/landing scheduling problem is an important problem for current airport operations. One difficulty in scheduling is that improving scheduling efficiency requires air traffic controller to issue more instructions, leading to a sharp increase in air traffic control workload. Overloading work may cause personnel fatigue, decision-making errors, and safety hazards. In view of this situation, a multi-objective mixed integer programming model for single runway takeoff/landing scheduling was constructed, which not only considers improving runway efficiency but also avoids excessively increasing air traffic control workload. The rank 2 matrix approximation based ant colony (RMA-AC) algorithm was designed. In comparison with the classical M-TPLP algorithm and CPLEX optimizer, numerical result validates that all the three methods have better performance than the first come first sever (FCFS) algorithm which is widely used in current aviation system. Specifically, the new algorithm RMA-AC is better than CPLEX for the runway efficiency improvement, and better than M-TPLP for the aircraft position shift control. It balances the runway efficiency and the air traffic controller workload. All these have positive effect on the airport efficiency improvement, delay reduction and safety scheduling.

    Reliability modeling and optimization of k=(M+N): G system based on retrial mechanism and switching failure
    Jing LI, Linmin HU, Mingjia LI
    2024, 28(4):  44-56.  doi:10.15960/j.cnki.issn.1007-6093.2024.04.004
    Asbtract ( 303 )   HTML ( 0)   PDF (994KB) ( 15 )  
    Figures and Tables | References | Related Articles | Metrics

    In this paper, the reliability and optimization model of repairable $k/(M+N):G$ retrial system with standby switching failure, Bernoulli vacation and working breakdown is established. It is assumed that when the working component fails, it is replaced by a warm standby component that has not yet failed. The replacement operation will lead to the failure of the warm standby component with a certain probability. In retrial space, the failed components follow the principle of random retrial. By using Runge-Kutta method and Cramer's rule, the transient and steady-state probabilities of the system are solved respectively, and the transient and steady-state reliability indexes and some other steady-state performance indexes of the system are obtained. Based on the defined cost elements and the steady-state performance indexes of the system, a minimization model of the total cost function per unit time is constructed, and the genetic particle swarm optimization (GA_PSO) hybrid algorithm is used to solve the optimization design model. The effects of different system parameters on the total cost function per unit time and steady-state performance index are evaluated by numerical experiments. The experimental results verify the reliability of the established model.

    Partial exactness of penalty function of multi-convex programming
    Yichen LAI, Zhiqing MENG
    2024, 28(4):  57-65.  doi:10.15960/j.cnki.issn.1007-6093.2024.04.005
    Asbtract ( 322 )   HTML ( 0)   PDF (675KB) ( 39 )  
    References | Related Articles | Metrics

    Multi-convex programming(MCP) is an important model in solving many engineering optimization problems in areas like machine learning and signal and information processing. In this paper, some new concepts of partial optimum, partial KKT condition, partial KKT ponit, partial Slater constraint qualification, partial exactness and partial stableness for the penalty function of multi-convex programming are defined. Under the partial Slater constraint qualification, a partial optimum of MCP is proved to be equivalent to partial KKT condition of MCP. The partial exactness of MCP is proved to be equivalent to partial KKT condition of MCP. The partial exactness of MCP is proved to be equivalent to partial stableness of MCP. These results are important for studying the exact penalty function of multi convex programming.

    An ND two-agent scheduling problem with rejection on a single machine related to the total completion time and makespan
    Qing GE, Lingfa LU, Jinjiang YUAN, Liqi ZHANG
    2024, 28(4):  66-74.  doi:10.15960/j.cnki.issn.1007-6093.2024.04.006
    Asbtract ( 276 )   HTML ( 0)   PDF (798KB) ( 24 )  
    References | Related Articles | Metrics

    In this paper, we consider the ND two-agent scheduling problem with rejection on a single machine. In this problem, there are two agents $A $ and $B $ and the job sets of them are denoted by $\mathcal{J}^A $ and $\mathcal{J}^B$ respectively. In the classical CO two-agent scheduling, two agents are competitive, i.e., $\mathcal{J}^A\cap \mathcal{J}^B=\varnothing $. However, in the ND two-agent scheduling, two agents may have common jobs, i.e., $\mathcal{J}^A\cap \mathcal{J}^B\neq\varnothing $ is allowed. In scheduling problems with rejection, each job is either accepted and processed on the machine, or rejected by paying a corresponding rejection cost. In this paper, we study the ND two-agent scheduling with rejection. In particular, we consider a constrained scheduling problem. That is, the objective is to minimize the sum of the total completion time $\sum C_j^A $ of accepted $A $-jobs and the total rejection cost of rejected $A $-jobs subject to an upper bound $Q $ on the sum of the makespan $C_{\max}^B $ of accepted $B $-jobs and the total rejection cost of the rejected $B $-jobs. For this problem, we provide a pseudo-polynomial-time algorithm and a fully polynomial-time approximation scheme.

    Study on DEA-based resources allocation with regret aversion
    Xu WANG, Yingming WANG, Yixin LAN
    2024, 28(4):  75-90.  doi:10.15960/j.cnki.issn.1007-6093.2024.04.007
    Asbtract ( 337 )   HTML ( 1)   PDF (882KB) ( 22 )  
    Figures and Tables | References | Related Articles | Metrics

    Considering a resources allocation scenario, in which the decision makers always tend to choose an allocation plan that does not render them regret. To this end, this paper proposes to employ regret aversion to help to allocate resources. Firstly, the data envelopment analysis approach is applied to measure the allocation performance. Then, the utility functions of beneficial resources and cost resources are distinguished. Thereafter, the regret value and rejoice value functions for resources allocation are built. With the help of Max-min rejoice value and Min-max regret value, the optimal resources allocation plan is determined. A numerical example is employed to show the applicability of the proposed approach. It shows that the method based on the regret aversion can help the decision maker to find an efficient resources allocation scheme and fairly distribute resources among decision making units.

    Alternative axiomatic characterization of the efficient compensation solution with applications
    Manchang ZENG, Jiagui ZHAO, Erfang SHAN
    2024, 28(4):  91-100.  doi:10.15960/j.cnki.issn.1007-6093.2024.04.008
    Asbtract ( 316 )   HTML ( 1)   PDF (778KB) ( 16 )  
    Figures and Tables | References | Related Articles | Metrics

    The compensation solution is one of the important component efficient allocation rules for cycle-free graph game. Béal et al.(2018) proposed and characterized its efficient extension. In this paper, we propose an alternative axiomatic characterization of the efficient compensation solution. We first show that the efficient compensation solution can be characterized by efficiency, relative fairness and fair distribution of surplus. Secondly, we compare this value with other allocation rules through an application example.

    A polyhedral study of piecewise linear unsplittable flow arc set
    Shiyu HUANG, Liang CHEN, Caixia KOU
    2024, 28(4):  101-110.  doi:10.15960/j.cnki.issn.1007-6093.2024.04.009
    Asbtract ( 686 )   HTML ( 4)   PDF (736KB) ( 21 )  
    Figures and Tables | References | Related Articles | Metrics

    Piecewise linear functions arise in many application domains, including transportation, telecommunications and production planning. In this paper, we concentrate on unsplittable multicommodity network flow problem with piecewise linear objective function. By introducing additional 0-1 variables, it can be modeled as a mixed integer linear programming formulation. We use the piecewise linear unsplittble flow arc set polyhedron of the considered problem as a substructure and derive two classes of valid inequalities. In addition, we describe the necessary and sufficient condition for these derived inequalities to be facet-defining. Finally, we demonstrate the effectiveness of using the derived inequalities as cutting planes to solve piecewise linear unsplittable multicommodity network flow problems by numerical results.

    Online scheduling on a single parallel-batch machine with linear lookahead
    Chengwen JIAO
    2024, 28(4):  111-116.  doi:10.15960/j.cnki.issn.1007-6093.2024.04.010
    Asbtract ( 1543 )   HTML ( 0)   PDF (672KB) ( 24 )  
    References | Related Articles | Metrics

    The online scheduling with lookahead is a very important scheduling model, which has the character that at any time, it can foresee the information of some jobs that will coming in the near feature. The information can be the number of jobs that can foresee, or the jobs that will come in some time intervals. The $LK_\beta$ is one of the models, in which the length of the time interval that can foresee is fixed with value $\beta, \beta\geq0$. This paper considers the online scheduling on a single parallel-batch machine with linear lookahead. The main character of the linear lookahead model is that at any time $t$, one can foresee the jobs that will come in the time interval $(t, \lambda t+\beta]$ with $\lambda\geq1, \beta\geq0$. The length of the interval $(t, \lambda t+\beta]$ is changed as the time $t$ going on, having the tend of steady growth. When $\lambda=1$, it is in fact the $LK_\beta$ lookahead model. In this paper, the objective is to minimize the makespan. When the capacity of the batch is unbounded and the jobs arrive with no-decreasing processing times, for different values of $\lambda, \beta$, it gives optimal algorithm and best possible online algorithm, respectively.

    Lower and upper bounds on the 2-rainbow domination number of a graph
    Zhihong XIE, Guoliang HAO, Wei ZHUANG
    2024, 28(4):  117-122.  doi:10.15960/j.cnki.issn.1007-6093.2024.04.011
    Asbtract ( 274 )   HTML ( 1)   PDF (685KB) ( 36 )  
    References | Related Articles | Metrics

    A $2$-rainbow dominating function of a graph $G$ is a function $f$ from the vertex set $V(G) $ of $G $ to the power set of the set $\{1,2\} $ such that any vertex $v$ with $f(v)=\varnothing$ satisfies that $\bigcup_{u\in N(v)}f(u)=\{1,2\} $, where $N(v) $ is the neighborhood of $v$. The value $\sum_{v\in V(G)}|f(v)| $ is called the weight of a $2$-rainbow dominating function $f $ of $G$. The $2$-rainbow domination number of $G $ is the minimum weight of a $2$-rainbow dominating function of $G$. By the structure analysis of graphs, some new lower and upper bounds on 2-rainbow domination number of graphs are derived in terms of the number of vertices, circumference, girth and minimum degree.

    Shapley index of the bonding operation on graphs
    Qingfeng DONG, Zhendong GU, Qianru ZHOU, Shuming ZHOU
    2024, 28(4):  123-134.  doi:10.15960/j.cnki.issn.1007-6093.2024.04.012
    Asbtract ( 302 )   HTML ( 0)   PDF (979KB) ( 21 )  
    Figures and Tables | References | Related Articles | Metrics

    How to allocate profit reasonablely is an important issue in cooperative game research. The distribution rule based on Shapley value, proposed by Shapley, the winner of the Nobel Prize in Economics, is the commonly used one in cooperative games. The cooperative game theory on graphs greatly enriches the research methods of game theory, and Shapley value on graphs has been widely applied in node influence, community detection and link prediction of social networks. Shapley distance on graphs is suggested based on Shapley value and it can be used to measure the cost of one vertex to access another one. Analogous to Wiener index and Kirchhoff index in graph theory, a new graph parameter, namely Shapley index, is proposed. In this paper, we establish the analytical expressions of Shapley distance and Shapley index of three kinds of conglutinate graphs, such as friendship graphs, book graphs and generalized rose graphs. These empirical examples provide methodological guidance for the computation of Shapley index of other complex topological structures.

    Subnetwork reliability analysis of Cayley graphs generated by complete graphs
    Xiaomin HU, Shurong ZHANG, Jie CAO, Weihua YANG
    2024, 28(4):  135-142.  doi:10.15960/j.cnki.issn.1007-6093.2024.04.013
    Asbtract ( 304 )   HTML ( 1)   PDF (769KB) ( 24 )  
    Figures and Tables | References | Related Articles | Metrics

    The research of subnetwork reliability is valuable for designation and development of high performance computer system, and provides theoretical basis for system maintenance. In this paper, we derive an upper bound and a lower bound of the subnetwork reliability in Cayley graphs generated by complete graphs under the probability fault model. The effectiveness of theoretical results are analyzed.

    Injective edge coloring of planar graphs without short cycles
    Yuehua BU, Wenwen CHEN, Junlei ZHU
    2024, 28(4):  143-151.  doi:10.15960/j.cnki.issn.1007-6093.2024.04.014
    Asbtract ( 274 )   HTML ( 0)   PDF (732KB) ( 18 )  
    References | Related Articles | Metrics

    To explore radio network packaging issues, Cardoso et al. proposed the concept of injective edge coloring of a graph in 2015. A $k$-injective edge coloring of $G$ is a coloring of the edges of $G, f$: $E(G)\to C=\{1,2,\cdots,k\}$, such that if $e_{1},\ e_{2},\ e_{3}$ are three consecutive edges in $G$, then $f(e_{1})\neq f(e_{3})$, where $e_{1},\ e_{2}$ and $e_{3}$ are consecutive if they form a path or a cycle of length 3. The injective edge coloring number, denoted by $\chi'_{i}(G)$, is the minimum number of colors such that $G$ has such a coloring. In this paper, we use minimal counter example and power transfer method to prove that if $G$ is a planar graph without $k$-cycles and $4^{-}$-cycles disjoint, then $\chi'_{i}(G)\leq3\Delta(G)-2$, where $5\leq k\leq10$.

    Mixed graphs with negative inertia index 1
    Ziyan CHEN, Yun QIAO, Yi WANG
    2024, 28(4):  152-161.  doi:10.15960/j.cnki.issn.1007-6093.2024.04.015
    Asbtract ( 866 )   HTML ( 0)   PDF (727KB) ( 28 )  
    Figures and Tables | References | Related Articles | Metrics

    A mixed graph is obtained by orienting some edges of a simple graph. The negative inertia index of a mixed graph is defined as the number of negative eigenvalues of its adjacency matrix. This paper mainly studies the negative inertia index of mixed graphs via the second kind Hermitian adjacency matrix. All mixed graphs with negative inertia index 1 are characterized.