Scheduling activities with time-dependent durations and resource consumptions

Steffen Pottel and Asvin Goel

European Journal of Operational Research, 2022, vol. 301, issue 2, 445-457

Abstract: In this paper we study the problem of scheduling a given sequence of activities where each activity consumes a resource with limited availability. Activity durations as well as resource consumptions are assumed to be time-dependent. Because of the interaction of time-dependent activity durations and resource consumptions, scheduling policies based on starting each activity in the sequence as early as possible may fail due to unnecessarily high resource consumptions exceeding the limited availability of the resource. We propose a dynamic discretization discovery algorithm that generates a partially time-expanded network during the search. We propose an acceleration technique allowing to significantly reduce the computational effort if the approach is embedded in an iterative solution procedure that frequently evaluates activity sequences which start with the same activities. Furthermore, we extend our approach to the case where resources can be replenished between subsequent activities. We evaluate our approach as a route evaluation method for the case of routing a fleet of electric vehicles in which travel durations and the energy consumed when travelling from one location to another depend on the time of the day.

Keywords: Scheduling; Time-dependency; Resource constraints; Break scheduling; Electric vehicle routing (search for similar items in EconPapers)
Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221721009838
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:ejores:v:301:y:2022:i:2:p:445-457

DOI: 10.1016/j.ejor.2021.11.032

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().