Acta mathematica scientia,Series A ›› 2012, Vol. 32 ›› Issue (6): 1121-1125.

• Articles • Previous Articles     Next Articles

Scheduling a Single Server and Equal Processing Times in a Two-machine Flow-shop

 SHI Ling1, CHENG Xue-Guang2   

  1. 1.Department of Mathematics, Hubei University for Nationalities, Hubei Enshi 445000;

    2.School of Mathematics and Statistics, Wuhan University, Wuhan 430072
  • Received:2011-05-20 Revised:2012-03-16 Online:2012-12-25 Published:2012-12-25

Abstract:

We consider the problem of two-machine flow-shop scheduling with a single server and equal processing 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 3/2.

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

CLC Number: 

  • 90B35
Trendmd