TORSCHE Scheduling toolbox pro Matlab

http://rtime.felk.cvut.cz/scheduling-toolbox/

Kdo jsme?

Zdeněk Hanzálek
Je vedoucím týmu. Navrhl a vyvinul několik vlastních algoritmů pro rozvrhování se zobecněnými relacemi následností a pro cyklické rozvrhování.

Michal Kutil
Je autor struktury a jádra toolboxu TORSCHE. Dále je autor algoritmů založených na "Boolean satisfiability problem" (SAT).

Přemysl Šůcha
Zabývá se rozvrhováním se zobecněnými relacemi následností a cyklickým rozvrhování. V aplikační oblasti se zaměřuje na optimalizaci iterativních algoritmů prováděných na pipelinovaných jednotkách a na optimalizaci výrobních procesů v průmyslu.

Jan Kelbel
Specializuje se na rozvrhování s využitím programování s omezujícími podmínkami. Je autor vlastních algoritmů pro optimalizaci propustnosti SMT (Surface-Mount Technology) výrobní linky.

Roman Čapek
Zabývá se především rozvrhováním výrobních procesů, především s alternativními výrobními postupy. Je autorem několika algoritmů pro rozvrhování výroby.

 

Jakým výzkumem se zabýváme

Rozvrhování je optimalizační proces, který řeší, jak přiřadit v čase zadané operace (úkoly, výpočty) na zdroje (stroje, lidské zdroje, výpočetní jednotky) tak, aby výsledný rozvrh byl co nejlepší vzhledem ke zvolenému optimalizačnímu kritériu.

Náš tým se zabývá návrhy a aplikací nových algoritmů pro rozvrhování. Vyvinuté algoritmy publikujeme na uznávaných zahraničních konferencích a v impaktovaných časopisech. Naší hlavní snahou je aplikovat tyto algoritmy v praxi. Vedle toho se snažíme předat našim studentům nejnovější poznatky z této oblasti.

K čemu to je

TORSCHE Scheduling toolbox slouží především pro rychlý vývoj rozvrhovacích algoritmů, ale také ke zpřístupnění námi implementovaných algoritmů studentům a vědcům, kteří se zabývají touto problematikou. TORSCHE je vytvořen v prostředí Matlab, jež je vhodné pro rychlý vývoj algoritmů a poskytuje uživateli velký komfort při práci s vektory, maticemi a množinami. TORSCHE navíc rozšiřuje základní funkce Matlabu o grafové algoritmy a nástroje pro matematické programování, které jsou nedílnou součástí rozvrhování. Mimo to v TORSCHE naleznete velmi pokročilé grafické rozhraní jak pro práci s grafy, tak pro zobrazování výsledků rozvrhování ve formě Ganttových diagramů. Další možností je využití simulace pomocí svázání rozvrhu s uživatelsky navrženým 3D prostředím.

Na čem konkrétně pracujeme

Algoritmy navržené pomocí TORSCHE jsme uplatnili například při optimalizaci rychlosti výpočtu ekvalizéru pro GSM bezdrátovou komunikaci. Díky našemu algoritmu jsme na stejné hardwarové architektuře dosáhli zrychlení o 46% oproti původní implementaci. Na jiné aplikaci, filtru pro aktivní potlačování rušivého signálu jsme dosáhli zrychlení 70 %.

Další oblast, ve které jsme dosáhli zajímavého úspěchu byla optimalizace výroby laků. Cílem bylo navrhnout pořadí výroby jednotlivých zakázek tak, abychom minimalizovali případná penále za zpoždění dodání zakázky a zároveň minimalizovali náklady spojené s uskladněním zakázek. V tomto případě jsme oproti původnímu řešení dosáhli o 60 % nižších nákladů na uskladnění a penále.

Mimo to jsme pracovali na optimalizaci propustnosti SMT (Surface-Mount Technology) výrobní linky. Vyrovnáním zátěže strojů na jedné lince jsme zde dosáhli zrychlení výroby o 6 %.

Kdo financuje náš výzkum

  • ARTIST2: Network of Excellence on Embedded Systems Design - 6. rámcový programu IST- EU (IST-004527)
  • Centrum aplikované kybernetiky: Výzkumné centrum MŠMT (LN00B096)

Kde se náš TORSCHE toolbox využívá

TORSCHE Scheduling toolbox se využívá na několika zahraničních univerzitách (např. University of Houston, Gdansk University of Technology, Hunan University). Mimo to je přiložen na CD ke knize "Scheduling: Theory, Algorithms and Systems", jejíž autorem je Michael Pinedo. Tato kniha je považována za jednu ze základních knih v tomto oboru.

Další významní partneři

  • Signal Processing Group - Institute of Information Theory and Automation - Academy of Sciences of the Czech Republic (http://zs.utia.cas.cz/)
  • Merica, s.r.o. (http://www.merica.cz/)
  • Electric Powersteering Components Europe, s. r. o. (http://www.epceurope.cz/)

Vybrané publikace

  • Šůcha, P. - Hanzálek, Z. - Heřmánek, A. - Schier, J.: Scheduling of Iterative Algorithms with Matrix Operations for Efficient FPGA Design - Implementation of Finite Interval Constant Modulus Algorithm. The Journal of VLSI Signal Processing. 2007, vol. 46, no. 1, s. 35-53. ISSN 0922-5773.
  • Šůcha, P. - Hanzálek, Z.: Deadline Constrained Cyclic Scheduling on Pipelined Dedicated Processors Considering Multiprocessor Tasks and Changeover Times, Mathematical and Computer Modelling, Volume 47, Issues 9-10, May 2008, p. 925-942, doi:10.1016/j.mcm.2007.05.009, Pergamon-Elsevier Science.
  • Šůcha, P. - Kutil, M. - Sojka, M. - Hanzálek, Z.: TORSCHE Scheuling Toolbox for Matlab. In IEEE Symposium on Computer-Aided Control System Design. Piscataway: IEEE, 2006, s. 50-52. ISBN 0-7803-9797-5.
  • Šůcha, P. - Hanzálek, Z.: Cyclic Scheduling of Tasks with Unit Processing Time on Dedicated Sets of Parallel Identical Processors. In Multidisciplinary International Scheduling: Theory and Application (MISTA). Paris: LIP6, 2007.
  • Šůcha, P. - Hanzálek, Z.: A Cyclic Scheduling Problem with an Undetermined Number of Parallel Identical Processors. Computational Optimization and Applications, Volume 48, Number 1, January 2011, doi: 10.1007/s10589-009-9239-4, Springer.
  • Kelbel, J. - Hanzálek, Z.: A Case Study on Earliness/Tardiness Scheduling by Constraint Programming. In Proceedings of the CP 2006 Doctoral Programme. Nantes: Laboratoire D.Informatique de Nantes Atlantique (LINA), 2006, s. 108-113.
  • Kelbel, J. - Hanzálek, Z.: Solving production scheduling with earliness/tardiness penalties by constraint programming. Journal of Intelligent Manufacturing, doi 10.1007/s10845-009-0318-2, article in press, published on-line first in 2010, Springer.
  • Šůcha, P. - Hanzálek, Z. - Pohl, Z.: Scheduling of Iterative Algorithms on FPGA with Pipelined Arithmetic Unit. In Proceedings of the Tenth IEEE Real-Time and Embedded Technology and Applications (RTAS 2004). Los Alamitos: IEEE Computer Society Press, 2004, s. 404-412. ISBN 0-7695-2148-7.
  • Hanzálek, Z. - Burget, P. - Šůcha, P.: Profinet IO IRT Message Scheduling with Temporal Constraints. IEEE Transactions on Industrial Informatics, doi: 10.1109/TII.2010.2052819, Volume 6, Number 3, Pages 369 - 380, August 2010.
  • Hanzálek, Z. - Jurčík, P.: Energy efficient scheduling for cluster-tree Wireless Sensor Networks with time-bounded data flows: application to IEEE 802.15.4/ZigBee. IEEE Transactions on Industrial Informatics. doi: 10.1109/TII.2010.2050144, Volume 6, Number 3, Pages 438 - 450, August 2010.
  • Trdlička, J. - Hanzálek, Z.: Distributed Multi-Commodity Network Flow Algorithm for Energy Optimal Routing in Wireless Sensor Networks. Radioengineering. 2010, vol. 2010, no. 4, p. 579-588. ISSN 1210-2512.
  • Čapek, R. - Šůcha, P. - Hanzálek, Z.: Production Scheduling with Alternative Process Plans. Accepted after Minor revision in European Journal of Operational Research, 2011, Elsevier.

Za obsah odpovídá: RNDr. Patrik Mottl, Ph.D.