Network construction problems with due dates

Averbakh, Igor; Pereira, Jordi

Keywords: scheduling, network design, Network construction, Emergency restoration, Integrated network design and scheduling

Abstract

A network needs to be constructed by a server (construction crew) that has a constant construction speed which is incomparably slower than the server’s travel speed within the already constructed part of the network. A vertex is recovered when it becomes connected to the depot by an already constructed path. Due dates for recovery times are associated with vertices. The problem is to obtain a construction schedule that minimizes the maximum lateness of vertices, or the number of tardy vertices. We introduce these new problems, discuss their computational complexity, and present mixed-integer linear programming formulations, heuristics, a branch-and-bound algorithm, and results of computational experiments.

Más información

Título de la Revista: EUROPEAN JOURNAL OF OPERATIONAL RESEARCH
Volumen: 244
Número: 3
Editorial: ELSEVIER SCIENCE BV
Fecha de publicación: 2015
Página de inicio: 715
Página final: 729
Idioma: English
DOI:

10.1016/j.ejor.2015.02.014

Notas: WOS Core Collection ISI SCOPUS