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(N log N) 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 our approach with the only other ε-approximate algorithm known in literature.
Agnetis, A. (1997). No-Wait Flow Shop Scheduling with Large Lot Sizes. ANNALS OF OPERATIONS RESEARCH, 70, 415-438 [10.1023/A:1018942709213].
No-Wait Flow Shop Scheduling with Large Lot Sizes
Agnetis, Alessandro
1997-01-01
Abstract
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(N log N) 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 our approach with the only other ε-approximate algorithm known in literature.
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
https://hdl.handle.net/11365/7819
Attenzione
Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo