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

Abstract

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.

Read at publisher →

Similar articles