The Two-machine Flow-shop Scheduling Problem with a Single Server and Unit Server Times

Authors

  • Shi Ling Department of Mathematics, Hubei University for Nationalities, Enshi 445000, China
  • Cheng Xue Guang School of Mathematics and Statistics, Wuhan University, Wuhan 430072, China

DOI:

https://doi.org/10.26713/jims.v4i1.74

Keywords:

Two-machine, Flow-shop, Single server, Complexity, NP-hardness, Worst-case analysis

Abstract

We consider the problem of two-machine flow-shop scheduling with a single server and unit server times, we show that this problem is NP-hard in the strong sense and present a simple greedy algorithm for it with worst-case bound $\frac{3}{2}$.

Downloads

Download data is not yet available.

Downloads

CITATION

How to Cite

Ling, S., & Guang, C. X. (2012). The Two-machine Flow-shop Scheduling Problem with a Single Server and Unit Server Times. Journal of Informatics and Mathematical Sciences, 4(1), 123–127. https://doi.org/10.26713/jims.v4i1.74

Issue

Section

Research Articles