A Mathematical Model for Periodic Scheduling Problems

TLDR

The paper proposes a mathematical model for scheduling periodic activities. The authors develop a model and an implicit‑enumeration algorithm based on network flow, and explore extensions and case studies. They prove the problem is NP‑complete, establish a foundation for resource‑based modelling of periodic activities, and demonstrate its usefulness through applications.

Abstract

A mathematical model is proposed for scheduling activities of periodic type. First a model is proposed for scheduling periodic events with particular time constraints. This problem, which could be considered the extension to periodic phenomena of ordinary scheduling with precedence constraints, is shown to be NP-complete. An algorithm for it of implicit enumeration type is designed based on network flow results, and its average complexity is discussed. Some extensions of the model are considered. The results of this first part serve as a basis in modelling periodic activities using resources. Several cases are considered. Finally some applications are presented for which the proposed model can be a useful tool.