NO-WAIT FLOW SHOP consists of minimizing the completion time of a set of N parts that must undergo a series of m machines in the same order, with the constraint that each part, once started, cannot wait on or between the machines. The problem is known to be NP-complete for m≥3, while an O(NlogN) algorithm exists when m=2. In this paper, some new results are presented concerning the case in which parts are grouped into lots of identical parts. An •-approximate algorithm is proposed, based on the solution to a transportation problem. The relative error of the approximation goes to zero as the size of any lot grows. Experimental results are reported comparing the present approach with the only other •-approximate algorithm known in literature.
