Search
TORSCHE Scheduling toolbox for Matlab
http://rtime.felk.cvut.cz/scheduling-toolbox/
Our team
Zdeněk Hanzálek
Team leader. His main interest is the resource constrained project scheduling. He has developed several algorithms for the scheduling with generalized precedence relations and for the cyclic scheduling.
Michal Kutil
Author of the structure and the core functions of the TORSCHE toolbox. He has also developed several algorithms based on the "Boolean satisfiability problem (SAT).
Přemysl ©ůcha
His main interest is the scheduling with the generalized precedence relations and the cyclic scheduling. In the application area, he focuses on the optimization of the iterative algorithms executed on the pipeline units.
Jan Kelbel
Author of several algorithms for the optimization of throughput of the Surface-Mount Technology (SMT). The algorithms are mainly based on the constraint programming techniques.
Roman Čapek
His main area of research is the production scheduling, especially scheduling with the alternative process plans. He is the author of several algorithms for the scheduling of production processes.
Our research
The main purpose of the scheduling is to assign a given set of tasks (production operations, computations) to a given set of resources (CPU units, machines, workforce) under a set of given constraints (precedence relations, deadlines) such that the objective function of the scheduling is optimized.
The main scope of our group is to design, develop and implement new scheduling algorithms for various types of problems. We dedicate a significant effort to bring the theoretical approaches to the form suitable for the real-world applications. Successful results are presented on the international conferences and published in the impacted journals. Besides the research and projects implementation, we share our experiences with students in the bachelor and master courses.
What is it for
The TORSCHE scheduling toolbox for Matlab serves mainly for the rapid prototyping of the scheduling algorithms and for sharing of algorithms already implemented by our research group with the researchers and students interested in the area of scheduling. The TORSCHE toolbox is implemented in the Matlab environment, which is suitable for the fast design and testing of new algorithms and it offers a great comfort for the computations with vectors, matrices and sets of numbers or variables. The toolbox intensely supports work with graphs, there are many implemented graph algorithms and there is also a powerful user interface for the work with graph objects. Moreover, the TORSCHE toolbox contains many scheduling algorithms and the results can be easily depicted in the form of the Gantt chart or used for the simulation in the user-designed 3D environment.
Successful applications
Algorithms developed in TORSCHE have been used for the optimization of the computation speed of the equalizer for the GSM wireless communication. We have achieved acceleration of 46% using our algorithm compared to the original implementation. With the same algorithm, we have improved the computational speed of the filter for active suppression of interfering signal by 70%.
Another successful application of the algorithms designed using the TORSCHE toolbox is the optimization of the lacquer production where the goal is to schedule the given jobs such that the penalties caused by the tardy jobs and costs given by the storage of the jobs are minimized. We have saved 60% of these costs compared to the previous solution.
We have been also working on the optimization of the throughput of the SMT (Surface-Mount Technology) assembly line. By the balancing of the workload through the working stations, we have accelerated the production by 6%.
Funding for our research
- ARTIST2: Network of Excellence on Embedded Systems Design - 6th general programme IST- EU (IST-004527)
- Centre for applied cybernetics: Research centre of the Ministry of education, youth and sports of the Czech Republic (LN00B096)
Where the TORSCHE toolbox is used
The TORSCHE toolbox is being used on several foreign universities, e.g. University of Houston, Gdansk University of Technology and Hunan University. Moreover, the toolbox is a part of CD attached to the Michael Pinedo's book "Scheduling: Theory, Algorithms and Systems", which is a very important publication in the scheduling area.
Other important partners
- 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/)
Important publications
- ©ů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.