Cyclic scheduling problems for multiprocessor system

N. S. Grigorieva

Zapiski Nauchnykh Seminarov POMI, Investigations on applied mathematics and informatics. Part III, Tome 539 (2024), pp. 66-85

Résumé

We consider the multiprocessors scheduling problem, when a set of jobs $V$ is done on $m$ identical parallel processors and set of jobs $V$ is to be repeated an infinitely number of times. The goal is to generate a periodic schedule, which is a schedule of one iteration that is repeated within a fixed time interval, which called the period (or cycle time). The aim of cyclic scheduling is to find a periodic schedule with the minimum period. We consider Periodic Scheduling on Identical Processors problem. Precedence constraints between jobs are represented by an uniform graph $G$. We propose algorithms for constructing cyclic schedules for four problems with parallel processors: the problem with unit processing times and three problems with arbitrary processing times. The problem with unit processing times and the problem with preemptions can be solved in polynomial time.

Bibliographie

[1] E. Levner, V. Kats, V. E. Levit, “An improved algorithm for a cyclic robotic scheduling problem”, Eur. J. Oper. Res., 97 (1997), 500–508 | DOI | Zbl

[2] V. Kats, E. Levner, “Cyclic scheduling on a robotic production line”, J. Scheduling, 5 (2002), 23–41 | DOI | MR | Zbl

[3] W. Kubiak, “Solution of the Liu-Layland problem via bottleneck just-in-time sequencing”, J. Scheduling, 8:4 (2005), 295–302 | DOI | MR | Zbl

[4] C. Hanen,, A. Munier, “A study of the cyclic scheduling problem on parallel processors”, Discrete Appl. Math., 57 (1995), 167–192 | DOI | MR | Zbl

[5] A. Munier, “The complexity of a cyclic scheduling problem with identical machines and precedence constraints”, Eur. J. Oper. Res., 91:3 (1996), 471–480 | DOI | MR | Zbl

[6] P. Brucker , T. Kampmeyer, “A general model for cyclic machine scheduling problems”, Discret. Appl. Math., 156:13 (2008), 2561–2572 | DOI | MR | Zbl

[7] J. R. L. Graham, E. L. Lawner, R. Kan, Ann. of Disc. Math., 5 (1979), 287 | DOI | Zbl

[8] J. Ullman, J. Comp. Sys. Sci, 171 (1975), 384 | DOI

[9] E. G. Coffman (ed.), Computer and Job-Shop Scheduling Theory, John Wiley, 1978 | MR

[10] E. G. Coffman, R. L. Graham, “Optimal schedule for two-processor systems”, Acta Informat, 1 (1972), 200–213 | DOI | MR

[11] C. Hanen, A. Munier, Cyclic scheduling on parallel processors: an overview, Scheduling theory and its applications, eds. Chretienne Philippe, Coffman Edward G, Lenstra Jan Karel, Liu Zhen, John Wiley and Sons, New York, 1994 | MR

[12] B. Dupont de Dinechin, A. M. Kordon, “Converging to periodic schedules for cyclic scheduling problems with resources and deadlines”, Computers Operations Research, 51 (2014), 227–236 | DOI | MR | Zbl

[13] R. L. Graham, “Bounds for certain multiprocessing anomalies”, Bell System Tech. J., 45 (1966), 1563–1581 | DOI

[14] N. Grigoreva, “Cyclic Scheduling for Parallel Processors with Precedence Constrains”, The 2 International Scientific and Practical Conference on Mathematical modeling, Programming and Applied mathematics (2020, 5–6 November, Veliky Novgorod, Russia), J. Physics. Conf. Ser., 2020

[15] N. Shirvani, R. Ruiz, S. Sharokh, “Cyclic scheduling of perishable products in parallel machine with release dates, due dates and deadline”, Int. J. Production Economics, 156 (2014), 1–12 | DOI

[16] A. Munier, “The complexity of a cyclic scheduling problem with identical machines and precedence constraints”, Eur. J. Oper. Res., 91:3 (1996), 471–480 | DOI | MR | Zbl

[17] R. R. Muntz, E. G. Coffman, “Preemptive scheduling of real-time tasks on multiprocessor systems”, J. Assoc. Comput. Mach., 17:2 (1970), 324–338 | DOI | MR | Zbl

[18] P. Sucha, Z. Hanzalek, “Deadline constrained cyclic scheduling on pipelined dedicated processors considering multiprocessor tasks and changeover times”, Math. Comput. Model, 47:9–10 (2008), 925–942 | DOI | MR | Zbl