Toyota problem
| advisor: | prof. Ing. Edita Pelantová, CSc. |
| e-mail: | show e-mail |
| type: | bachelor thesis, master thesis |
| branch of study: | MI_MM, MINF |
| key words: | balancovaná slova, faktorová komplexita, sturmovské posloupnosti |
| description: | Firma Toyota jako první řešila úlohu navrhnout pořadí výroby mnoha různých součástek na jednom výrobním páse tak, aby se výrobky sestávající z předepsaného počtu jednotlivých součástek daly co nejrychleji zkompletovat a poslat do prodeje, a přitom nebylo třeba skladovat součástky čekající na kompletaci. Tato úloha se dá formulovat v řeči kombinatoriky na slovech jako úkol zkonstruovat nekonečné slovo nad konečnou abecedou (každé písmeno abecedy představuje jeden typ výrobku) tak, aby se četnost písmene v libovolně dlouhém prefixu nekonečného slova co nejméně lišila od předepsané hustoty. Touto vlastností se vyznačují k-balancovaná slova. Úkolem studenta či studentky bude 1) nastudovat vlastnosti balancovaných slov a jejich konstrukci pomocí kolorování sturmovskými posloupnostmi; 2) naprogramovat generování těchto slov pro zadané hustoty písmen; 3) na základě počítačových experimentů nalézt faktorovou komplexitu konstruovaných slov a s využitím známých metod jí dokázat; 4) vytvořit formuli pro délku periody zkonstruovaného slova v případě, že zadané hustoty písmen jsou racionální. |
| references: | N. Brauner and Y. Crama, The maximum deviation just-in-time scheduling Problem, Discrete Applied Mathematics vol. 134 (2004) 25 – 50. G. Steiner and S. Yeomans, Level Schedules for Mixed-Model, Just-in-Time Processes Management Science, vol. 39, issue 6, (1993) 728-735. L. Dvořáková, E. Pelantová, D. Opočenská, A. M. Shur, On minimal critical exponent of balanced sequences. Theor. Comput. Sci. Vol. 922 (2022) 158-169. |
| last update: | 07.09.2022 16:34:16 |
administrator for this page:
Ľubomíra Dvořáková | last update: 09/12/2011