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

Shi Ling, Cheng Xue Guang

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}$.

Keywords


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

Full Text:

PDF


DOI: http://dx.doi.org/10.26713%2Fjims.v4i1.74

eISSN 0975-5748; pISSN 0974-875X