Cyclic flowshop scheduling with operators and robots: Vyacheslav Tanaev’s vision and lasting contributions. (English) Zbl 1280.90054
Summary: This note discusses the pioneering role and main contributions of V. S. Tanaev in the field of cyclic robotic flowshop scheduling. Open questions (either explicitly or implicitly) posed in his papers and kept unsolved up to date are exposed.
MSC:
| 90B35 | Deterministic scheduling theory in operations research |
| 68T40 | Artificial intelligence for robotics |
Biographic References:
Tanaev, Vyacheslav S.References:
| [1] | Agnetis, A. (2000). Scheduling no-wait robotic cells with two and three machines. European Journal of Operational Research, 123(2), 303–314. · Zbl 0967.90042 · doi:10.1016/S0377-2217(99)00258-1 |
| [2] | Aizenshtat, V. S. (1963). Multi-operator cyclic processes. Doklady of the National Academy of Sciences of Belarus, 7(4), 224–227 (in Russian). |
| [3] | Bedini, R., Lisini, G. G., & Sterpos, P. (1979). Optimal programming of working cycles for industrial robots. The ASME Journal of Mechanical Design, 101, 250–257. · doi:10.1115/1.3454046 |
| [4] | Blokh, A. Sh., & Tanaev, V. S. (1966). Multioperator processes. Izvstiya Akademii Nauk Belarusi, Seriya Fizika-Matematycnyk Nauk, 2, 5–11 (in Russian). |
| [5] | Brauner, N. (2008). Identical part production in cyclic robotic cells: Concepts, overview and open questions. Discrete Applied Mathematics, 156(13), 2480–2492. · Zbl 1152.90429 · doi:10.1016/j.dam.2008.03.021 |
| [6] | Che, A., & Chu, C. (2005). A polynomial algorithm for no-wait cyclic hoist scheduling in an extended electroplating line. Operations Research Letters, 33(3), 274–284. · Zbl 1140.90393 · doi:10.1016/j.orl.2003.10.012 |
| [7] | Che, A., & Chu, C. (2009). Multi-degree cyclic scheduling of a no-wait robotic cell with multiple robots. European Journal of Operational Research, 199(1), 77–88. · Zbl 1176.90201 · doi:10.1016/j.ejor.2008.10.035 |
| [8] | Che, A., Chu, C., & Chu, F. (2002a). Multicyclic hoist scheduling with constant processing times. IEEE Transactions on Robotics and Automation, 18(1), 69–80. · doi:10.1109/70.988976 |
| [9] | Che, A., Chu, C., & Levner, E. (2002b). A polynomial algorithm for 2-degree cyclic robot scheduling. European Journal of Operational Research, 145(1), 31–44. · Zbl 1012.90008 · doi:10.1016/S0377-2217(02)00175-3 |
| [10] | Che, A., Yan, P., Yang, N., & Chu, C. (2010a). Optimal cyclic scheduling of a hoist and multi-type parts with fixed processing times. International Journal of Production Research, 48(5), 1225–1243. · Zbl 1197.90198 · doi:10.1080/00207540802552659 |
| [11] | Che, A., Yan, P., Yang, N., & Chu, C. (2010b). A branch and bound algorithm for optimal cyclic scheduling in a robotic cell with processing time windows. International Journal of Production Research. doi: 10.1080/00207540903225205 . · Zbl 1197.90340 · doi:10.1016/j.ijpe.2010.05.010 |
| [12] | Chen, H., Chu, C., & Proth, J.-M. (1998). Cyclic scheduling of a hoist with time window constrains. IEEE Transactions on Robotics and Automation, 14, 144–152. · doi:10.1109/70.660860 |
| [13] | Chu, C. (2006). A faster polynomial algorithm for 2-cyclic robotic scheduling. Journal of Scheduling, 9, 453–468. · Zbl 1154.90431 · doi:10.1007/s10951-006-8501-1 |
| [14] | Cuninghame-Green, R. A. (1962). Describing industrial processes with interface and approximating their steady-state behaviour. Operational Research Quarterly, 13, 95–100. · doi:10.1057/jors.1962.10 |
| [15] | Dawande, M. N., Geismer, H. N., & Sethi, S. P. (2005). Dominance of cyclic solutions and challenges in the scheduling of robotic cells. SIAM Review, 47(4), 709–721. · Zbl 1080.90063 |
| [16] | Dawande, M. N., Geismer, H. N., Sethi, S. P., & Sriskandarajah, C. (2007). Throughput optimization in robotic cells. New York: Springer. · Zbl 1155.90003 |
| [17] | Hanen, C., & Munier-Kordon, A. (1995). A study of the cyclic scheduling problem on parallel processors. Discrete Applied Mathematics, 57(2–3), 167–192. · Zbl 0830.68009 · doi:10.1016/0166-218X(94)00102-J |
| [18] | Hanen, C., & Munier-Kordon, A. (2009). Periodic schedules for linear precedence constraints. Discrete Applied Mathematics, 157(2), 280–291. · Zbl 1155.90383 · doi:10.1016/j.dam.2008.03.018 |
| [19] | Karp, R. M. (1978). A characterization of the minimum cycle mean in a digraph. Discrete Mathematics, 23, 309–311. · Zbl 0386.05032 · doi:10.1016/0012-365X(78)90011-0 |
| [20] | Karp, R. M., & Orlin, J. B. (1981). Parametric shortest path algorithms with an application to cyclic staffing. Discrete Applied Mathematics, 3, 37–45. · Zbl 0453.68032 · doi:10.1016/0166-218X(81)90026-3 |
| [21] | Karzanov, A. V., & Livshits, E. M. (1978). Minimal quantity of operators for serving a homogeneous linear technological process. Automation and Remote Control, 39(3), 445–450. · Zbl 0426.90043 |
| [22] | Kats, V., & Levner, E. (1997a). Minimizing the number of robots to meet a given cyclic schedule. Annals of Operations Research, 69, 209–226. · Zbl 0880.90075 · doi:10.1023/A:1018980928352 |
| [23] | Kats, V., & Levner, E. (1997b). A strongly polynomial algorithm for no-wait cyclic robotic flowshop scheduling. Operations Research Letters, 21, 171–179. · Zbl 0892.90101 · doi:10.1016/S0167-6377(97)00036-9 |
| [24] | Kats, V., & Levner, E. (2002). Cyclic scheduling in a robotic production line. Journal of Scheduling, 5(1), 23–41. · Zbl 0995.90032 · doi:10.1002/jos.92 |
| [25] | Kats, V., & Levner, E. (2010). Cyclic routing algorithms in graphs: Performance analysis and applications to robot scheduling. Computers and Industrial Engineering. doi: 10.1016/j.cie.2010.04.009 . |
| [26] | Kats, V., Levner, E., & Meyzin, L. (1999). Multiple-part cyclic hoist scheduling using a sieve method. IEEE Transactions on Robotics and Automation, 15(4), 704–713. · doi:10.1109/70.781993 |
| [27] | Lee, T. E., & Pozner, M. E. (1997). Performance measures and schedules in periodic job shops. Operations Research, 45(1), 72–91. · Zbl 0892.90102 · doi:10.1287/opre.45.1.72 |
| [28] | Lei, L., & Wang, T. J. (1989). A proof: the cyclic scheduling problem is NP-complete. Working Paper no. 89-0016, Rutgers University, April. |
| [29] | Levner, E., & Kats, V. (1995). Efficient algorithms for cyclic robotic flowshop problem. In R. Storch (Ed.), Proceedings of the international working conference IFIP WG5.7 on managing concurrent manufacturing to improve industrial performance (pp. 115–123). Seattle: University of Washington. |
| [30] | Levner, E., Kats, V., & Levit, V. (1997). An improved algorithm for cyclic flowshop scheduling in a robotic cell. European Journal of Operational Research, 197, 500–508. · Zbl 0919.90088 · doi:10.1016/S0377-2217(96)00272-X |
| [31] | Levner, E., Meyzin, L., & Ptuskin, A. (1998). Periodic scheduling of a transporting robot under incomplete input data: a fuzzy approach. Fuzzy Sets and Systems, 98(3), 255–266. · doi:10.1016/S0165-0114(96)00387-9 |
| [32] | Leung, J. M. Y., & Levner, E. (2006). An efficient algorithm for multi-hoist cyclic scheduling with fixed processing times. Operations Research Letters, 34(4), 465–472. · Zbl 1133.90340 · doi:10.1016/j.orl.2005.07.010 |
| [33] | Liu, J., & Jiang, Y. (2005). An efficient optimal solution to the two-hoist no-wait cyclic scheduling problem. Operations Research, 53(2), 313–327. · Zbl 1165.90462 · doi:10.1287/opre.1040.0167 |
| [34] | Livshits, E. M., Mikhailetsky, Z. N., & Chervyakov, E. V. (1974). A scheduling problem in an automated flow line with an automated operator. Computational Mathematics and Computerized Systems, 5, 151–155 (in Russian). |
| [35] | Megiddo, N. (1979). Combinatorial optimization with rational objective functions. Mathematics of Operations Research, 4, 414–424. · Zbl 0425.90076 · doi:10.1287/moor.4.4.414 |
| [36] | Phillips, L. W., & Unger, P. S. (1976). Mathematical programming solution of a hoist scheduling program. AIIE Transactions, 8(2), 219–225. · doi:10.1080/05695557608975070 |
| [37] | Romanovskii, I. V. (1964). Asymptotic behaviour of recurrence relations of dynamic programming and optimal stationary control. Doklady of the Soviet Academy of Sciences, 157(6), 1303–1306 (in Russian). |
| [38] | Romanovskii, I. V. (1967). Optimization of stationary control of a discrete deterministic process. Kybernetika (Cybernetics), 3(2), 66–78. |
| [39] | Suprunenko, D. A., Aizenshtat, V. S., & Metel’sky, A. S. (1962). A multistage technological process. Doklady of the National Academy of Sciences of Belarus, 6(9), 541–522 (in Russian). |
| [40] | Tanaev, V. S. (1964). A scheduling problem for a flowshop line with a single operator. Inzhenerno-Fizicheskii Zhurnal (Journal of Engineering Physics), 7(3), 111–114 (in Russian). |
| [41] | Tanaev, V. S., & Shkurba, V. V. (1975). Introduction to scheduling theory. Moscow: Nauka (in Russian). |
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.
