当期目录

2022年 第37卷 第4期    刊出日期：2022-12-30

上一期    下一期

关于工件具有多个维护区间最小化总误工量的可中断排序的一个注记

贺茹艳, 原晋江, 张源

2022, 37(4):  331-342.  doi:10.13371/j.cnki.chin.q.j.m.2022.04.001

摘要 ( 71 )   PDF (374KB) ( 81 )  

相关文章 | 计量指标

We study the single-machine preemptive scheduling problem with multiple maintenance activities to minimize the total late work, in which the jobs must be processed in the time space not occupied by the maintenance intervals. For this problem, we present a polynomial algorithm to determine the optimal schedule and establish a formula expression to the optimal value. Moreover, our result is used to correct some minor errors in the literature related to the single-machine (preemptive or non-preemptive) scheduling with one maintenance activity to minimize the total late work. 

在比较模型下网络是 n-邻 d-可诊断的充分条件

王世英, 赵丽娜

2022, 37(4):  343-354.  doi:10.13371/j.cnki.chin.q.j.m.2022.04.002

摘要 ( 58 )   PDF (378KB) ( 29 )  

相关文章 | 计量指标

Diagnosability of multiprocessor systems is an important research topic. The system and an interconnection network have an underlying topology, which is usually presented by a graph. In 2012, Peng et al. proposed a metric for fault diagnosis of the graph, namely, the n-neighbor diagnosability that restrains every fault-free node to contain at least n fault-free neighbors. It is difficult to get the n-neighbor diagnosability of the graph from the definition of the n-neighbor diagnosability. Afterwards, some sufficient and necessary conditions are given. It is also difficult to find the n-neighbor diagnosability of the graph from those results. In this paper, we show some new sufficient conditions for the graph to be n-neighbor d-diagnosable under the MM^∗ model. It improves the corresponding result of [Theoretical Computer Science 773 (2019) 107-114].

图族和树族的带宽和割宽的遍历性

林艺舒, 常彩冰, 刘岩

2022, 37(4):  355-365.  doi:10.13371/j.cnki.chin.q.j.m.2022.04.003

摘要 ( 55 )   PDF (346KB) ( 74 )  

相关文章 | 计量指标

Bandwidth, cutwidth, cyclic bandwidth, bandwidth sum and cyclic bandwidth
sum are well-known indices about optimal labeling of graphs applied in VLSI design,
network communications, and other areas involving the graph layout. To design the
graphs with the given indices, we need to study the ergodicity. Let F be a set of graphs
under consideration and ϕ an integer-valued function defined on F, namely, ϕ is an index,
such as bandwidth and cutwidth. If there exists a graph G ∈ F such that ϕ(G) =x for
any integer x in the interval [a,b], where a and b are the minimum and maximum of ϕ
on F, respectively, then ϕ is said to have ergodicity on F. Let G_n be the set of simple
connected graphs with order n and T_n the set of trees with order n. In this paper, we
investigate the ergodicity of bandwidth, cutwidth, cyclic bandwidth, the bandwidth sum
and cyclic bandwidth sum on T_n and G_n.





K 割宽临界树的构造

张振坤, 叶稀琼

2022, 37(4):  366-379.  doi:10.13371/j.cnki.chin.q.j.m.2022.04.004

摘要 ( 63 )   PDF (408KB) ( 32 )  

相关文章 | 计量指标

The cutwidth of a graph G is the minimum number of overlap edges when G is embedded into a path P_n. The cutwidth problem for a graph G is to determine the cutwidth of G. A graph G with cutwidth k is k-cutwidth critical if every proper subgraph of G has cutwidth less than k and G is homeomorphically minimal. In this paper, we completely investigated methods of forming a k-cutwidth (k >1) critical tree T.

哈林图的导出匹配可扩性

张庆楠, 惠志昊, 杨雨, 王安

2022, 37(4):  380-385.  doi:10.13371/j.cnki.chin.q.j.m.2022.04.005

摘要 ( 130 )   PDF (344KB) ( 80 )  

相关文章 | 计量指标

 Let G be a connected graph having a perfect matching. The graph G is said to be induced matching (IM) extendable if every induced matching M of G is contained in a perfect matching of G. In this paper, we show that Halin graph G =T ∪C is IMextendable if and only if its characteristic tree T is isomorphic to K_1,3, K_1,5, K_1,7 or S_2,2.

具有特定独立的罗马2-控制数的树

李贝贝, 尚卫苹

2022, 37(4):  386-393.  doi:10.13371/j.cnki.chin.q.j.m.2022.04.006

摘要 ( 104 )   PDF (336KB) ( 110 )  

相关文章 | 计量指标

For a graph G = (V,E), a Roman {2}-dominating function f :V → {0,1,2} has the property that for every vertex v ∈V with f(v) = 0, either v is adjacent to at least one vertex u for which f(u) = 2, or at least two vertices u₁ and u₂ for which f(u₁) =f(u₂) = 1. A Roman {2}-dominating function f = (V₀,V₁,V₂) is called independent if V₁∪V₂ is an independent set. The weight of an independent Roman {2}-dominating function f is the value ω(f) =\sum_v∈V f(v), and the independent Roman {2}-domination number i_{R2}(G) is the minimum weight of an independent Roman {2}-dominating function on G. In this paper, we characterize all trees with i_{R2}(T) =γ(T)+ 1, and give a linear time algorithm to compute the value of i_{R2}(T) for any tree T. 

关于单机双代理可拒绝排序的一个注记

张利齐, 周松涛, 录岭法

2022, 37(4):  394-402.  doi:10.13371/j.cnki.chin.q.j.m.2022.04.007

摘要 ( 47 )   PDF (268KB) ( 36 )  

相关文章 | 计量指标

In a recent paper, Feng et al. [5] (Two-agent scheduling with rejection on a single machine. Appl. Math. Model. 39 (2015) 1183-1193) studied some two-agent scheduling problems with rejection on a single machine. The authors showed that all problems are NP-hard and then provided four dynamic programming algorithms. Unfortunately, we observe that some mistakes are contained in the two dynamic programming algorithms. In this note, we first show by a counter-example that the above two algorithms are incorrect. Furthermore, we also provide two new dynamic programming algorithms to solve the same problems.

带有单个服务器的多台平行批处理机在线排序问题

付乳燕, 林琳

2022, 37(4):  403-411.  doi:10.13371/j.cnki.chin.q.j.m.2022.04.008

摘要 ( 47 )   PDF (281KB) ( 35 )  

相关文章 | 计量指标

We consider parallel-batch machines scheduling problem with a single server to minimize the maximum completion time. Jobs arrive over time. Every batch has to be loaded by the sever before being processed on machines. The loading (setup) operation of a batch occurs only when some machine is idle, and the server can perform only one setup operation every time. For some special case, we provide a best possible online algorithm with competitive ratio (√ 5+ 1)/2. For general case, we give another online algorithm with competitive ratio 3. 

工件允许拆分加工的单机排序问题

申惠军, 耿志超

2022, 37(4):  412-421.  doi:10.13371/j.cnki.chin.q.j.m.2022.04.009

摘要 ( 92 )   PDF (295KB) ( 43 )  

相关文章 | 计量指标

The single-machine lot scheduling problem with splittable jobs to minimize the number of tardy jobs has been showed to be weakly NP-hard in the literature. In this paper, we show that a generalized version of this problem in which jobs have deadlines is strongly NP-hard, and also present the results of some related scheduling problems. 

工件有安装时间的无界平行分批排序研究

高园, 党佳瑞, 彭娟

2022, 37(4):  422-429.  doi:10.13371/j.cnki.chin.q.j.m.2022.04.010

摘要 ( 57 )   PDF (293KB) ( 36 )  

相关文章 | 计量指标

We study the scheduling on an unbounded parallel-batch machine with jobs having set-up times to minimize a regular objective function which is either of the sumform or of the max-form. As we know, in the existing literature, the research about parallel-batch scheduling does not consider the set-up times of jobs. However, the set-up times of jobs are widely presented in practical applications. Each job considered in this paper has a set-up time. The set-up time of each batch is equal to the maximum set-up time of all jobs contained in the batch, and the processing time of each batch is equal to the longest processing time of the jobs contained in the batch. Depending on the different definitions of the completion time of a job, we consider two types of jobs: batch jobs and drop-line jobs. For batch jobs, the completion time of a job is given by the completion time of the batch containing this job. For drop-line jobs, the completion time of a job is given by the starting time of the batch containing this job plus the processing time of this job. In this paper, we give pseudo-polynomial time algorithms for the above scheduling problems in which the jobs have agreeable processing times and set-up times. In addition, when the objective functions are the total weighted completion time, the maximum lateness, and the maximum cost, we present a polynomial time algorithm, respectively. 

关于3-正则哈密尔顿图的围长的一个注记

赵秋兰, 原晋江

2022, 37(4):  430-431.  doi:10.13371/j.cnki.chin.q.j.m.2022.04.011

摘要 ( 52 )   PDF (226KB) ( 69 )  

相关文章 | 计量指标

It is well-known that the Petersen graph is nonhamiltonian. A very short proof for this result was presented in [2] due to D. B. West. In this note, by extending the proof technique in [2], we briefly show that the girth of every 3-regular hamiltonian graph on n≥10 vertices is at most (n+ 4)/3.

圈强迫的2-连通无爪三正则图的刻画#br#

#br#

张义冉, 王秀梅

2022, 37(4):  432-440.  doi:10.13371/j.cnki.chin.q.j.m.2022.04.012

摘要 ( 73 )   PDF (336KB) ( 63 )  

相关文章 | 计量指标

Let G be a graph and C be an arbitrary even cycle of G. The graph G is called a cycle-forced graph if G−V (C) has a unique perfect matching. When C is an arbitrary induced even cycle of G, G is called an induced-cycle-forced graph. If G−V (C) has no perfect matching, G is said to be cycle-bad. This paper gives characterizations of these three type of graphs in the class of 2-connected claw-free cubic graphs.