Serafini, Paolo; Ukovich, Walter A mathematical model for periodic scheduling problems. (English) Zbl 0676.90030 SIAM J. Discrete Math. 2, No. 4, 550-581 (1989). Summary: 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 an 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. Cited in 1 ReviewCited in 74 Documents MSC: 90B35 Deterministic scheduling theory in operations research 90C35 Programming involving graphs or networks 68Q25 Analysis of algorithms and problem complexity 90B10 Deterministic network models in operations research Keywords:cyclic scheduling; activities of periodic type; periodic events; time constraints; NP-complete; implicit enumeration; average complexity Software:PESPLib PDFBibTeX XMLCite \textit{P. Serafini} and \textit{W. Ukovich}, SIAM J. Discrete Math. 2, No. 4, 550--581 (1989; Zbl 0676.90030) Full Text: DOI