×

The basic cyclic scheduling problem with deadlines. (English) Zbl 0729.90051

Author’s summary: “The purpose of this paper is to study the latest schedule existence, calculation and properties of a basic cyclic scheduling problem with deadlines. First it is shown that, in the general case, a latest schedule exists but may be difficult to compute. Then we focus on a special case which we call the optimal cyclic production problem. We derive an upper bound for the number of maximal-path values needed to compute the latest starting times and show the K-periodic structure of the latest starting time sequences.”

MSC:

90B35 Deterministic scheduling theory in operations research
90B30 Production models
90C35 Programming involving graphs or networks
90-08 Computational methods for problems pertaining to operations research and mathematical programming
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] J. Carlier and P. Chretienne, Timed Petri net schedules, in: Advances in Petri Nets (Springer, Berlin, to appear).; J. Carlier and P. Chretienne, Timed Petri net schedules, in: Advances in Petri Nets (Springer, Berlin, to appear). · Zbl 0667.68051
[2] Carlier, J.; Chretienne, P.; Girault, C., Modelling scheduling problems with timed Petri nets, (Advances in Petri Nets (1984), Springer: Springer Berlin), 62-83 · Zbl 0562.68050
[3] Chretienne, P., Timed Petri nets, State Thesis (1983), P. and M. Curie University: P. and M. Curie University Paris, (in French)
[4] Chretienne, P., Maximal paths of a bi-valued graph, RAIRO Rech. Opér., 18, 3, 221-245 (1984), (in French)
[5] Chretienne, P., Transient and asymptotic behaviour analysis of a timed event graph, RAIRO Tech. Sci. Info, 4, 1, 127-142 (1985) · Zbl 0556.68020
[6] Cohen, G.; Dubois, D.; Quadrat, J. P.; Viot, M., A linear system theoretic view of discrete events processes and its use for performance evaluation in manufacturing, IEEE Trans. Automat. Control, 30, 210-220 (1985) · Zbl 0557.93005
[7] Hanen, C.; Carlier, J.; Chretienne, P., Optimizing static pipelines with timed Petri nets, Proc. 7th Workshop on Applications and Theory of Petri Nets, Oxford (1987)
[8] H. Hillion and J.M. Proth, Performance evaluation of job-shop systems using timed event graphs, IEEE Trans. Automat. Control, to appear.; H. Hillion and J.M. Proth, Performance evaluation of job-shop systems using timed event graphs, IEEE Trans. Automat. Control, to appear. · Zbl 0656.90054
[9] Karp, R. M., A characterization of the minimum cycle mean in a digraph, Discrete Math., 23, 309-311 (1978) · Zbl 0386.05032
[10] Lawler, E. L.; Martel, C. U., Scheduling periodically occurring tasks on multiple processors, Inform. Process. Lett., 12, 9-12 (1981) · Zbl 0454.68018
[11] Liu, C. L.; Layland, J. W., Scheduling algorithms for multiprogramming in a hard-real-time environment, J.ACM, 20, 1, 46-61 (1973) · Zbl 0265.68013
[12] Ramamritham, K.; Stankovic, J. A., Dynamic task scheduling in hard-real-time distributed systems, IEEE Softw., 1, 65-75 (1984)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.