On Approximation Algorithms for Two-Stage Scheduling Problems Conference Paper uri icon


  • Springer International Publishing AG 2017. We study scheduling on parallel two-stage flowshops in which each job has to pass through two operations: an R-operation and a T -operation. Motivated by the current research in data centers, we consider two restricted versions of the problem: 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 takes more 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.

name of conference

  • Frontiers in Algorithmics - 11th International Workshop, FAW 2017, Chengdu, China, June 23-25, 2017, Proceedings

published proceedings

  • Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

author list (cited authors)

  • Wu, G., Chen, J., & Wang, J.

citation count

  • 2

complete list of authors

  • Wu, Guangwei||Chen, Jianer||Wang, Jianxin

publication date

  • May 2017