Abstract
The paper considers cyclic scheduling problems arising in planning of robotic flowlines and logistics. The problems are reduced to finding the minimum (or maximum) cost-to-time ratio in doubly weighted graphs. New combinatorial algorithms are developed extending the cyclic project scheduling algorithm by Romanovskii (1967) and the minimum-cost-to-time-ratio algorithm by Dantzig, Blattner and Rao (1967). Whereas Romanovskii’s and Dantzig-Blattner-Rao’s algorithms are restricted to solving problems with fixed numerical data, the new algorithms can treat input data that are varied at prescribed intervals. Several special cases are solved in strongly polynomial time.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Brauner, N., Finke, G.: Optimal moves of the material handling system in a robotic cell. Int. J. Production Economics 74, 269–277 (2001)
Che, A., Chu, C., Levner, E.: A polynomial algorithm for 2-degree cyclic robot scheduling. European Journal of Operational Research 145(1), 31–44 (2003)
Chu, C.: A faster polynomial algorithm for 2-cyclic robotic scheduling. Journal of Scheduling 9(5), 453–468 (2006)
Cohen, E., Megiddo, N.: Improved algorithms for linear inequalities with two variables per inequality. SIAM Journal on Computing 23, 1313–1350 (1994)
Crama, Y., Kats, V., van de Klundert, J., Levner, E.: Cyclic scheduling in robotic flow-shop. Annals of operations Research 96(1-4), 97–123 (2000)
Dantzig, G.B., Blattner, W., Rao, M.R.: Finding a cycle in a graph with minimum cost to time ratio with application to a ship routing problem. In: Rosenstiehl, P. (ed.) Theory of Graphs, Dunod, Paris, Gordon, Breach, New York, pp. 77–84 (1967)
Dawande, M.N., Geismer, H.N., Sethi, S.P., Sriskandarajah, C.: Througput Optimization in Robotic Cells. Springer, Heidelberg (2007)
Dyer, M.E.: Linear time algorithms for two- and three-variable linear programming. SIAM Journal on Computing 13(1), 31–45 (1984)
Hanen, C., Munier, A.: Cyclic scheduling on parallel processors: An overview. In: Chretienne, P., Coffman Jr., E.G., Lenstra, J.K., Liu, Z. (eds.) Scheduling Theory and Its Applications, pp. 194–226. Wiley, Chichester (1995)
Kampmeyer, T.: Cyclic Scheduling Problems. PhD thesis, University of Osnabrück, Germany (2006)
Kats, V., Lei, L., Levner, E.: Minimizing the cycle time of multiple-product processing networks with a fixed operation sequence and time-window constraints. European Journal of Operational Research 187(3), 1196–1211 (2008)
Kats, V., Levner, E.: Cyclic scheduling on a robotic production line. Journal of Scheduling 5, 23–41 (2002)
Kats, V., Levner, E.: A polynomial algorithm for 2-cyclic robotic scheduling: A non-Euclidean case. In: Gelbukh, A., Reyes-Garcia, C.A. (eds.) MICAI 2006. LNCS (LNAI), vol. 4293, pp. 439–449. Springer, Heidelberg (2006)
Kats, V., Levner, E., Meyzin, L.: Multiple-part cyclic hoist scheduling using a sieve method. IEEE Transactions on Robotics and Automation 15(4), 704–713 (1999)
Khachiyan, L.G.: A polynomial algorithm in linear programming. Sov. Math. Dokl. 20, 191–199 (1979)
Lee, T.E., Posner, M.E.: Performance measures and schedules in periodic job shops. Operations Research 45(1), 72–91 (1997)
Lei, L.: Determining the optimal starting times in a cyclic schedule with a given route. Computers and Operations Research 20, 807–816 (1993)
Levner, E., Kats, V.: A parametrical critical path problem and an application for cyclic scheduling. Discrete Applied Mathematics 87, 149–158 (1998)
Levner, E., Kats, V., Sriskandarajah, C.: A geometric algorithm for finding two-unit cyclic schedules in no-wait robotic flowshop. In: Levner, E. (ed.) Proceedings of the Workshop on Intelligent Scheduling of Robots and FMS, Holon, Israel, pp. 101–112. HAIT Press (1996)
Megiddo, N.: Linear time algorithms for linear programming in R3 and related problems. SIAM Journal on Computing 12(4), 759–776 (1983)
Romanovskii, I.V.: Optimization of stationary control of a discrete deterministic process. Kybernetika (Cybernetics) 3(2), 66–78 (1967)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2008 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Kats, V., Levner, E. (2008). Parametric Algorithms for Cyclic Scheduling Problems with Applications to Robotics. In: Gelbukh, A., Morales, E.F. (eds) MICAI 2008: Advances in Artificial Intelligence. MICAI 2008. Lecture Notes in Computer Science(), vol 5317. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-88636-5_62
Download citation
DOI: https://doi.org/10.1007/978-3-540-88636-5_62
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-88635-8
Online ISBN: 978-3-540-88636-5
eBook Packages: Computer ScienceComputer Science (R0)