The graph ordering problem here addressed derives from industrial applications where one can associate vertices with process steps and edges with jobs. A linear layout of the vertices corresponds then to a production schedule, and one wants to find a layout minimizing the average completion time of the jobs. We prove that the problem is NP-hard in general and is polynomial on trees. We then provide a 2-approximate algorithm and investigate necessary conditions for optimality. On this basis, we devised a combinatorial branch-and-bound algorithm and tested it on random graphs with up to 100 nodes.

Minimum Flow Time Graph Ordering

ARBIB, CLAUDIO;FLAMMINI, MICHELE;
2003-01-01

Abstract

The graph ordering problem here addressed derives from industrial applications where one can associate vertices with process steps and edges with jobs. A linear layout of the vertices corresponds then to a production schedule, and one wants to find a layout minimizing the average completion time of the jobs. We prove that the problem is NP-hard in general and is polynomial on trees. We then provide a 2-approximate algorithm and investigate necessary conditions for optimality. On this basis, we devised a combinatorial branch-and-bound algorithm and tested it on random graphs with up to 100 nodes.
2003
3-540-20452-0
File in questo prodotto:
Non ci sono file associati a questo prodotto.
Pubblicazioni consigliate

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/11697/25909
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 6
  • ???jsp.display-item.citation.isi??? 4
social impact