Timing problems and algorithms: Time decisions for sequences of activities

Timing problems and algorithms: Time decisions for sequences of activities

Authors: Vidal, Thibaut; Crainic, Teodor Gabriel; Gendreau, Michel; Prins, Christian

Networks - 2015 Volume 65, Pages 102-128

© 2015 Wiley Periodicals, Inc.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.

https://doi.org/10.1002/net.21587

Cite as:

@article{Vidal_2015,
	doi = {10.1002/net.21587},
	url = {https://doi.org/10.1002%2Fnet.21587},
	year = 2015,
	month = {feb},
	publisher = {Wiley},
	volume = {65},
	number = {2},
	pages = {102--128},
	author = {Thibaut Vidal and Teodor Gabriel Crainic and Michel Gendreau and Christian Prins},
	title = {Timing problems and algorithms: Time decisions for sequences of activities},
	journal = {Networks}
}



    Leave a Reply

    Your email address will not be published. Required fields are marked *

    x
    This site uses cookies to make navigation simple and efficient. By continuing you declare that you want to automatically accept the privacy policy. More. Close