×

zbMATH — the first resource for mathematics

CROSS cyclic resource-constrained scheduling solver. (English) Zbl 1334.90048
Summary: Cyclic scheduling problems consist in ordering a set of activities executed indefinitely over time in a periodic fashion, subject to precedence and resource constraints. This class of problems has many applications in manufacturing, embedded systems and compiler design, production and chemical systems. This paper proposes a Constraint Programming approach for cyclic scheduling problems, based on modular arithmetic: in particular, we introduce a modular precedence constraint and a global cumulative constraint along with their filtering algorithms. We discuss two possible formulations. The first one (referred to as CROSS) models a pure cyclic scheduling problem and makes use of both our novel constraints. The second formulation (referred to as CROSS\(^\ast\)) introduces a restrictive assumption to enable the use of classical resources constraints, but may incur a loss of solution quality. Many traditional approaches to cyclic scheduling operate by fixing the period value and then solving a linear problem in a generate-and-test fashion. Conversely, our technique is based on a non-linear model and tackles the problem as a whole: the period value is inferred from the scheduling decisions. Our approach has been tested on a number of non-trivial synthetic instances and on a set of realistic industrial instances. The method proved to effective in finding high quality solutions in a very short amount of time.
MSC:
90B35 Deterministic scheduling theory in operations research
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Artigues, C.; Demassey, S.; Néron, E., Resource-constrained project scheduling, Control Systems, Robotics and Manufacturing Series, (2010), Wiley
[2] M. Ayala, C. Artigues, On integer linear programming formulations for the resource-constrained modulo scheduling problem, Technical Report 10393, LAAS-CNRS, Toulouse, France, 2010.
[3] Baptiste, P.; Le Pape, C.; Nuijten, W., Constrains-based scheduling: applying constraint programming to scheduling, (2001), Springer · Zbl 1094.90002
[4] Beldiceanu, Nicolas; Carlsson, Mats; Thiel, Sven, Sweep synchronization as a global propagation mechanism, Comput. Oper. Res., 33, 10, 2835-2851, (October 2006)
[5] Bhattacharyya, S. S.; Sriram, S., Embedded multiprocessors - scheduling and synchronization (signal processing and communications), (2009), CRC Press
[6] Blachot, F.; Dupont de Dinechin, B.; Huard, G., SCAN: A heuristic for near-optimal software pipelining, (Proc. of Euro-Par 2006, vol. 4128, (2006)), 289-298
[7] Bonfietti, A.; Benini, L.; Lombardi, M.; Milano, M., An efficient and complete approach for throughput-maximal SDF allocation and scheduling on multi-core platforms, (Proc. of DATE, (2010)), 897-902
[8] Brucker, Peter; Kampmeyer, Thomas, Tabu search algorithms for cyclic machine scheduling problems, J. Sched., 1994, 303-322, (2005) · Zbl 1123.90018
[9] Brucker, Peter; Kampmeyer, Thomas, A general model for cyclic machine scheduling problems, Discrete Appl. Math., 156, 13, 2561-2572, (July 2008)
[10] Chen, H.; Chu, C.; Proth, J.-M., Cyclic scheduling of a hoist with time window constraints, IEEE Trans. Robot. Autom., 14, 1, 144-152, (Feb. 1998)
[11] Codina, J. M.; Llosa, J.; González, A., A comparative study of modulo scheduling techniques, (Proc. of ICS ʼ02, (2002)), 97-106
[12] Dasdan, A., Experimental analysis of the fastest optimum cycle ratio and mean algorithms, ACM Trans. Des. Autom. Electron. Syst., 9, 4, 385-418, (October 2004)
[13] Draper, D. L.; Jonsson, A. K.; Clements, D. P.; Joslin, D. E., Cyclic scheduling, (Proc. of IJCAI, (1999), Morgan Kaufmann Publishers Inc.), 1016-1021
[14] Dupont de Dinechin, B., From machine scheduling to VLIW instruction scheduling, ST J. Res., 1, 2, 1-35, (2004)
[15] Eichenberger, A. E.; Davidson, E. S., Efficient formulation for optimal modulo schedulers, ACM SIGPLAN Not., 32, 5, 194-205, (1997)
[16] Georgiadis, L.; Goldberg, A. V.; Tarjan, R.; Werneck, R. F., An experimental study of minimum mean cycle algorithms, (Proc. of ALENEX, (2009)), 1-13
[17] Ghamarian, A.; Geilen, M.; Basten, T.; Theelen, B.; Mousavi, M. R.; Stuijk, S., Liveness and boundedness of synchronous data flow graphs, (Proc. of FMCAD, (2006)), 68-75
[18] Hagog, M.; Zaks, A., Swing modulo scheduling for gcc, (Proc. of the 2004 GCC Developersʼ Summit, (2004)), 55
[19] Hanen, C., Study of a NP-hard cyclic scheduling problem: the recurrent job-shop, Eur. J. Oper. Res., 72, 1, 82-101, (1994) · Zbl 0801.90061
[20] Huff, R. A., Lifetime-sensitive modulo scheduling, (Proceedings of the ACM SIGPLAN 1993 Conference on Programming Language Design and Implementation, vol. 28, (June 1993), ACM), 258-267
[21] Ito, K.; Parhi, K. K., Determining the minimum iteration period of an algorithm, J. VLSI Signal Process., 244, 3, 229-244, (1995)
[22] Kudlur, M.; Mahlke, S., Orchestrating the execution of stream programs on multicore platforms, (Proc. of PLDI, vol. 43, (May 2008)), 114-124
[23] Le Pape, C.; Couronné, P., Time-versus-capacity compromises in project scheduling, (Proc. of the 13th Workshop of the UK Planning Special Interest Group, (1994))
[24] Lee, E. A.; Messerschmitt, D. G., Static scheduling of synchronous data flow programs for digital signal processing, IEEE Trans. Comput., 36, 1, 24-35, (January 1987)
[25] Levner, E.; Kats, V.; Alcaide López de Pablo, D.; Cheng, T. C.E., Complexity of cyclic scheduling problems: A state-of-the-art survey, Comput. Ind. Eng., 59, 2, 352-361, (September 2010)
[26] Llosa, J.; Gonzalez, A.; Ayguade, E.; Valero, M., Swing modulo scheduling: A lifetime-sensitive approach, (Proc. of PACT, (1996), IEEE Computer Society), 80-87
[27] Llosa, J.; Gonzalez, A.; Ayguade, E.; Valero, M.; Eckhardt, J., Lifetime-sensitive modulo scheduling in a production environment, IEEE Trans. Comput., 50, 3, 234-249, (2001)
[28] Lombardi, M.; Bonfietti, A.; Milano, M.; Benini, L., Precedence constraint posting for cyclic scheduling problems, (Proc. of CPAIOR, (2011)), 137-153 · Zbl 1302.90087
[29] Lombardi, M.; Milano, M., A MIN-flow algorithm for minimal critical set detection in resource constrained project scheduling, Artif. Intell., 182-183, 58-67, (2012) · Zbl 1248.90051
[30] McCormick, S. T.; Pinedo, M. L., Transient behavior in a flexible assembly system, Int. J. Flex. Manuf. Syst., 3, 1990, 27-44, (1991)
[31] McCormick, S. T.; Rao, U. S., Some complexity results in cyclic scheduling, Math. Comput. Model., 20, 2, 107-122, (July 1994)
[32] Parhi, K. K.; Messerschmitt, D. G., Rate-optimal fully-static multiprocessor scheduling of data-flow signal processing programs, (Proc. of IEEE International Symposium on Circuits and Systems, vol. 217, (1989), IEEE), 1923-1928
[33] Parhi, K. K.; Messerschmitt, D. G., Static rate-optimal scheduling of iterative data-flow programs via optimum unfolding, IEEE Trans. Comput., 40, 2, 178-195, (1991)
[34] Policella, N.; Cesta, A.; Oddi, A.; Smith, S. F., From precedence constraint posting to partial order schedules: A csp approach to robust scheduling, AI Commun., 20, 3, 163-180, (2007) · Zbl 1146.90421
[35] Rau, R. B., Iterative modulo scheduling: an algorithm for software pipelining loops, (Proc. of the 27th Annual International Symposium on Microarchitecture, (1994), ACM), 63-74
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.