Author name cluster

Guangwei Wu

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

5 papers

1 author row

TCS Journal 2026 Journal Article

Parameterized algorithms and complexity for scheduling with precedence constraints and time windows

Feng Shi
Na Feng
Yicong Zhu
Jingyi Liu
Jianxin Wang
Guangwei Wu

In the paper, we study several variants of the Scheduling problem with precedence constraints and time windows defined on a task set S, denoted by P∣prec, ri, di ∣γ, and present improved fixed-parameter algorithms parameterized by the maximum processing time p max and the maximum number μ of overlapping time windows, defined as μ = max t ∈ N | { i ∈ S ∣ r i ≤ t < d i } |. Firstly, we propose an algorithm for P∣prec, ri, di ∣C max with time complexity O ( ( p max + 2 ) μ p max n 3 ), where the aim is to find a feasible schedule minimizing the makespan C max, and n is the number of tasks. This significantly improves the previously best-known algorithm for P∣prec, ri, di ∣⋆ with time complexity O ( p max 2 μ · 16 μ μ · n 3 ), where ⋆ indicates that the variant has no objective function and just decides the existence of a feasible schedule. Next, for the unit processing time case P ∣ p r e c, p i = 1, r i, d i ∣ C max, we develop an algorithm with time complexity O(2 μ μmn 3), where m is the number of machines, improving the previously best-known algorithm for P ∣ p r e c, p i = 1, r i, d i ∣ ★ with time complexity O(16 μ n 4). Then, we extend the two algorithms to the typed machine setting, i. e. , P ∣ M j ( t y p e ), p r e c, r i, d i ∣ C max and P ∣ M j ( t y p e ), p r e c, p i = 1, r i, d i ∣ C max, as well as to variants with other objective functions such as the maximum flow time F max and mean weighted flow time F mean. Finally, we show that the problem P ∣ o u t t r e e, p i = 1, d i ∣ ★, where the precedence constraints are restricted to an outtree, is para-NP-hard when parameterized by the maximum vertex out-degree Δ of the outtree.

Details DOI

TCS Journal 2020 Journal Article

Improved approximation algorithms for two-stage flowshops scheduling problem

Guangwei Wu
Jianer Chen
Jianxin Wang

This paper considers the problem of scheduling n two-stage jobs on m two-stage flowshops so as to minimize the makespan. By studying the relationship between the problem and the classical makespan problem, we prove that if there is an α-approximation algorithm for the makespan problem, then for the general case of the problem, we can construct a 2α-approximation algorithm, and for two restricted cases which are of practical importance, we can construct an ( α + 1 / 2 ) -approximation algorithm. As a result, by employing the polynomial-time approximation scheme for the makespan problem, we get a ( 2 + ϵ ) -approximation algorithm for the general case and a ( 1. 5 + ϵ ) -approximation algorithm for the two restricted cases, which significantly improve the previous approximation ratios 2. 6 and 11/6 respectively.

Details DOI

TCS Journal 2020 Journal Article

On scheduling multiple two-stage flowshops

Guangwei Wu
Jianer Chen
Jianxin Wang

This paper studies the problem of scheduling n two-stage jobs on m multiple two-stage flowshops, with the objective of minimizing the makespan. The problem is NP-hard even when m is a fixed constant, and becomes strongly NP-hard when m is part of the input. A 2. 6-approximation algorithm along with its analysis is presented for an arbitrary m ≥ 2. This is the first approximation algorithm for multiple flowshops when the number m of flowshops is part of the input. The fact that m is part of the input and the time complexity O ( n log ⁡ n ) of the algorithm demonstrate that the problem, which plays an important role in the current research in cloud computing and data centers, can be solved efficiently with a reasonable level of satisfaction.

Details DOI

TCS Journal 2019 Journal Article

On scheduling inclined jobs on multiple two-stage flowshops

Guangwei Wu
Jianer Chen
Jianxin Wang

We study scheduling on multiple two-stage flowshops in which each job has to pass through an R-operation and a T-operation. Motivated by the current research in data centers, we consider two restricted versions of the problem in which the jobs are inclined: one restricts that for each job, the R-operation consumes no less time than the T-operation, while the other assumes that the T-operation consumes no less time than the R-operation for each job. For the first case, we present an online 2-competitive algorithm and an offline 11/6-approximation algorithm. For the second case, we give an online 5/2-competitive algorithm, and prove, for the offline setting, that the problem can be reduced to the problem in the first case.

Details DOI

TCS Journal 2019 Journal Article

Scheduling two-stage jobs on multiple flowshops

Guangwei Wu
Jianer Chen
Jianxin Wang

Scheduling two-stage jobs on multiple two-stage flowshops is studied. A new formulation for configurations of the scheduling is proposed, leading directly to improvements on complexity of scheduling algorithms for the problem. Motivated by observations in practice, we present a deeper study on the structures of the problem that leads to a new approach that gives very significant improved scheduling algorithms for the problem when the costs of the two stages differ significantly.

Details DOI