Table of Content

30 December 2022, Volume 37 Issue 4

Previous Issue    Next Issue

A Note on Preemptive Scheduling with Multiple Maintenance Activities to Minimize the Total Late Work

HE Ru-yan, YUAN Jin-jiang, ZHANG Yuan

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

Asbtract ( 105 )   PDF (374KB) ( 104 )  

Related Articles | Metrics

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. 

A Sufficient Condition for Networks to be n-Neighbor d-Diagnosable under the Comparison Model

WANG Shi-ying, ZHAO Li-na

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

Asbtract ( 96 )   PDF (378KB) ( 72 )  

Related Articles | Metrics

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]

Ergodicity of Bandwidth and Cutwidth on Families of Graphs and Trees

LIN Yi-shu, CHANG Cai-bing, LIU Yan

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

Asbtract ( 99 )   PDF (346KB) ( 118 )  

Related Articles | Metrics

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.





Forming a Critical Tree with Cutwidth k

ZHANG Zhen-kun, YE Xi-qiong

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

Asbtract ( 103 )   PDF (408KB) ( 54 )  

Related Articles | Metrics

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.

Induced Matching-Extendability of Halin Graphs

ZHANG Qing-nan, HUI Zhi-hao, YANG Yu, WANG An,

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

Asbtract ( 166 )   PDF (344KB) ( 115 )  

Related Articles | Metrics

 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.

Independent Roman {2}-Domination in Trees

LI Bei-bei, SHANG Wei-ping

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

Asbtract ( 154 )   PDF (336KB) ( 129 )  

Related Articles | Metrics

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. 

A Note on Two-Agent Scheduling with Rejection on a Single Machine

ZHANG Li-qi, ZHOU Song-tao, LU Ling-fa

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

Asbtract ( 81 )   PDF (268KB) ( 51 )  

Related Articles | Metrics

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.

Online Parallel-Batch Machines Scheduling with a Single Server

FU Ru-yan, LIN Lin,

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

Asbtract ( 87 )   PDF (281KB) ( 56 )  

Related Articles | Metrics

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. 

A Note on Single-Machine Lot Scheduling with Splittable Jobs to Minimize the Number of Tardy Jobs

SHEN Hui-jun, GENG Zhi-chao

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

Asbtract ( 133 )   PDF (295KB) ( 92 )  

Related Articles | Metrics

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. 

Research on Unbounded Parallel-Batch Scheduling with Jobs Having Set-Up Times

GAO Yuan, DANG Jia-rui, PENG Juan

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

Asbtract ( 100 )   PDF (293KB) ( 58 )  

Related Articles | Metrics

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. 

A Note on the Girth of 3-Regular Hamiltonian Graph

ZHAO Qiu-lan, YUAN Jin-jiang

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

Asbtract ( 102 )   PDF (226KB) ( 93 )  

Related Articles | Metrics

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.

Characterizations of Cycle-Forced 2-Connected Claw-Free Cubic Graphs

ZHANG Yi-ran, WANG Xiu-mei

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

Asbtract ( 107 )   PDF (336KB) ( 89 )  

Related Articles | Metrics

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.