Network construction problems with due dates. (English) Zbl 1346.90322
Summary: 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.
MSC:
| 90B35 | Deterministic scheduling theory in operations research |
| 90C35 | Programming involving graphs or networks |
Keywords:
scheduling; network design; network construction; emergency restoration; integrated network design and schedulingReferences:
| [1] | Averbakh, I., Emergency path restoration problems, Discrete Optimization, 9, 1, 58-64 (2012) · Zbl 1242.90073 |
| [2] | Averbakh, I.; Pereira, J., The flowtime network construction problem, IIE Transactions, 44, 8, 681-694 (2012) |
| [3] | Brucker, P., Scheduling algorithms (2007), Springer: Springer New York · Zbl 1126.90001 |
| [4] | Cavdaroglu, B.; Hammel, E.; Mitchell, J. E.; Sharkey, T. C.; Wallace, W. A., Integrating restoration and scheduling decisions for disrupted independent infrastructure systems, Annals of Operations Research, 203, 1, 279-294 (2013) · Zbl 1272.90014 |
| [5] | Crauwels, H. A.J.; Potts, C. N.; Wassenhove, L. N., Local search heuristics for single machine total weighted tardyness scheduling problem, INFORMS Journal on Computing, 10, 341-350 (1998) · Zbl 1092.90516 |
| [6] | Elgindy, T.; Ernst, A.; Baxter, M.; Savelsbergh, M. W.P.; Kalinowski, T., Incremental network design with shortest paths, European Journal of Operational Research, 238, 675-684 (2014) · Zbl 1338.90074 |
| [8] | Fischetti, M.; Laporte, G.; Martello, S., The delivery man problem and cumulative matroids, Operations Research, 41, 6, 1055-1064 (1993) · Zbl 0791.90062 |
| [9] | Garey, M.; Johnson, D., Computers and intractability (1979), Freeman: Freeman New York · Zbl 0411.68039 |
| [10] | Guha, S.; Moss, A.; Naor, J. S.; Schieber, B., Efficient recovery from power outage, (Vitter, J.; Larmore, L.; Leighton, F., Proceedings of the 31st annual ACM symposium on theory of computing (STOC) (1999), Atlanta, GA, USA), 574-582 · Zbl 1345.90042 |
| [13] | Kalinowski, T.; Matsypura, D.; Savelsbergh, M., Incremental network design with maximum flows, European Journal of Operational Research, 242, 1, 51-62 (2015) · Zbl 1341.90024 |
| [14] | Lenstra, J. K.; Kan, A. H.G. R., Complexity results for scheduling chains on a single machine, European Journal of Operational Research, 4, 4, 270-275 (1980) · Zbl 0439.90041 |
| [15] | Nurre, S. C.; Cavdaroglu, B.; Mitchell, J. E.; Sharkey, T. C.; Wallace, W. A., Restoring infrastructure systems: An integrated network design and scheduling (inds) problem, European Journal of Operational Research, 223, 794-806 (2012) · Zbl 1292.90189 |
| [16] | Nurre, S. G.; Sharkey, T. C., Integrated network design and scheduling problems with parallel identical machines: Complexity results and dispatching rules, Networks, 63, 4, 306-326 (2014) · Zbl 1390.90118 |
| [17] | Savelsbergh, M.; Uma, R.; Wein, J., An experimental study of lp-based approximation algorithms for scheduling problems, INFORMS Journal on Computing, 17, 1, 123-136 (2005) · Zbl 1239.90053 |
| [18] | Shore, M. L.; Foulds, L. R.; Gibbons, P. B., An algorithm for the steiner problem in graphs, Networks, 12, 323-333 (1982) · Zbl 0514.05036 |
| [19] | Sousa, J. P.; Wolsey, L. A., A time indexed formulation of non-preemtive single machine scheduling problems, Mathematical Programming, 54, 353-367 (1992) · Zbl 0768.90041 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
