Skip to Main content Skip to Navigation
Journal articles

Timing problems and algorithms: Time decisions for sequences of activities

Abstract : Timing problems involve the choice of task execution dates within a predetermined processing sequence, and under various additional constraints or objectives such as time windows, time‐dependent costs, or flexible processing times, among others. Their efficient resolution is critical in branch and bound and neighborhood search methods for vehicle routing, project and machine scheduling, as well as in various applications in network optimization, resource allocation, and statistical inference. Timing‐related problems have been studied for years, yet research on this subject suffers from a lack of consensus, and most knowledge is scattered among operations research and applied mathematics domains. This article introduces a classification of timing problems and features, as well as a unifying multidisciplinary analysis of timing algorithms. In relation to frequent application cases within branching schemes or neighborhood searches, the efficient resolution of series of similar timing subproblems is also analyzed. A dedicated formalism of reoptimization “by concatenation” is introduced to that extent. The knowledge developed through this analysis is valuable for modeling and algorithmic design, for a wide range of combinatorial optimization problems with time characteristics, including rich vehicle routing settings and emerging nonregular scheduling applications, among others.
Complete list of metadatas

https://hal-utt.archives-ouvertes.fr/hal-02521888
Contributor : Daniel Gavrysiak <>
Submitted on : Friday, March 27, 2020 - 4:35:30 PM
Last modification on : Monday, July 20, 2020 - 12:34:52 PM

Links full text

Identifiers

Collections

ROSAS | UTT | CNRS

Citation

Thibaut Vidal, Teodor Gabriel Crainic, Michel Gendreau, Christian Prins. Timing problems and algorithms: Time decisions for sequences of activities. Networks, Wiley, 2015, 65 (2), pp.102-128. ⟨10.1002/net.21587⟩. ⟨hal-02521888⟩

Share

Metrics

Record views

265