This paper deals with a sequencing problem arising in the management of paced flowlines, that is production lines where jobs are released at constant time intervals. The problem is to sequence jobs to minimize total tardiness. The problem can be formulated as an assignment problem with a number of knapsack constraints. We prove the strong NP-hardness of the problem and give a number of lower bounds which are used in a branch-and-bound algorithm. Computational results in realistic settings confirm the eff ectiveness of the procedure developed. The results are particularly interesting with reference to mixed-model assembly lines in which several jobs of few diff erent types are produced periodically.

Agnetis, A., Macchiaroli, R., Pacciarelli, D., Rossi, F. (1997). Assigning jobs to time frames on a single machine to minimizetotal tardiness. IIE TRANSACTIONS, 29, 965-976.

Assigning jobs to time frames on a single machine to minimizetotal tardiness

AGNETIS, ALESSANDRO;
1997-01-01

Abstract

This paper deals with a sequencing problem arising in the management of paced flowlines, that is production lines where jobs are released at constant time intervals. The problem is to sequence jobs to minimize total tardiness. The problem can be formulated as an assignment problem with a number of knapsack constraints. We prove the strong NP-hardness of the problem and give a number of lower bounds which are used in a branch-and-bound algorithm. Computational results in realistic settings confirm the eff ectiveness of the procedure developed. The results are particularly interesting with reference to mixed-model assembly lines in which several jobs of few diff erent types are produced periodically.
1997
Agnetis, A., Macchiaroli, R., Pacciarelli, D., Rossi, F. (1997). Assigning jobs to time frames on a single machine to minimizetotal tardiness. IIE TRANSACTIONS, 29, 965-976.
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11365/27836
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo