Multi-periodic scheduling with release times and deadlines minimizing the number of machine periods
Gutiérrez, Sandra, Jiménez, Fernando, Salazar, Fernanda, Torres, Luis M., Torres, Ramiro, Pérez, Emilio Journal of Scheduling
· Springer Nature
· 2026-10-01
· DOI: 10.1007/s10951-026-00884-1
Аннотация
In this paper, a multi-periodic discrete interval scheduling problem is considered. This problem stems from an application to improve customer service in the branch offices of the Internal Revenue Service of Ecuador. A set of jobs must be scheduled non-preemptively on a set of parallel identical machines such that each job is processed in a time interval of a given length between its arrival time and its deadline. Moreover, the planning horizon is divided into several time periods and the state of a machine can either be active or inactive at each of these periods. Machines may perform jobs only while they are active, and each machine can process at most one job at the same time. The task consists of (i) selecting feasible processing intervals for the jobs, (ii) determining which machines are active at each period, and (iii) assigning selected job intervals to active machines. The goal is to minimize the total number of machine periods required to schedule all jobs. Two integer programming models are proposed for this problem, along with an asymptotically optimal algorithm for the special case in which all jobs have equal processing times. The algorithms are evaluated on both real-world and simulated instances.
Gutiérrez, Sandra, Jiménez, Fernando, Salazar, Fernanda et al. Multi-periodic scheduling with release times and deadlines minimizing the number of machine periods. // Journal of Scheduling. – 2026. – DOI: 10.1007/s10951-026-00884-1. – URL: http://link.springer.com/openurl/fulltext?id=doi:10.1007/s10951-026-00884-1
Gutiérrez, Sandra, Jiménez, Fernando, Salazar, Fernanda, Torres, Luis M, Torres, Ramiro, Pérez, & Emilio (2026). Multi-periodic scheduling with release times and deadlines minimizing the number of machine periods. Journal of Scheduling. https://doi.org/10.1007/s10951-026-00884-1
Gutiérrez, et al. “Multi-periodic scheduling with release times and deadlines minimizing the number of machine periods.” Journal of Scheduling, 2026. doi:10.1007/s10951-026-00884-1.
@article{Gutirrez2026,
title = {Multi-periodic scheduling with release times and deadlines minimizing the number of machine periods},
author = {Gutiérrez and Sandra and Jiménez and Fernando and Salazar and Fernanda and Torres and M., Luis and Torres and Ramiro and Pérez and Emilio},
journal = {Journal of Scheduling},
year = {2026},
doi = {10.1007/s10951-026-00884-1},
url = {http://link.springer.com/openurl/fulltext?id=doi:10.1007/s10951-026-00884-1}
}
In this paper, we consider cost-sharing problems defined on rooted trees. We refer to these problems as cost-tree problems and to the induced transferable utility cooperative games as irrigation games. We introduce a formal notion of...
In this paper, we focus on nonlinear programming problems with cardinality constraints that restrict the number of nonzero components of the decision vector. We start with a straightforward mixed-integer programming reformulation....
Portfolio selection is a critical issue in financial management under uncertainty. In this paper, we propose a complex approach for portfolio selection with quantile return approximation. In particular, we propose a practical workflow...
The transcendental logarithmic (translog) production function is recognised as a flexible functional form for modelling production processes. It accommodates varying elasticities of input substitution and diverse types of...
This study investigates mothership-drone route determination using two optimization approaches: a Mixed Integer Linear Programming (MILP) model based on a discrete hexagonal grid, and a Mixed Integer Nonlinear Programming (MINLP) model...