Scheduling in Discrete Event Systems

The course is a substitute for:

Scheduling in Discrete Event Systems (35RDU)

Lecturer:

Tutor:

Supervisor:

Department of Control Engineering

Synopsis:

Classification and formulation of scheduling problems in computer

and manufacturing systems is shown. It introduces general approaches, namely

based on discrete optimization techniques, for solving scheduling problems.

It is based on the graph theory, branch and bound algorithms, linear

programming and integer linear programming. Single processor scheduling problems are

solved with criterion of Cmax, Fw and Lmax. Parallel machine

scheduling is focused on the tasks with/without precedence constraints and

with/without preemption. Flow-shop, and job-shop on dedicated processors is

presented. Further we deal with periodic scheduling of real-time applications based on fixed priority preemptive operating system. Analysis of timing properties is based on timed automata and temporal logic.

http://dce.felk.cvut.cz/rdu/

Requirements:

linear algebra

Syllabus of lectures:

1. Scheduling problems in manufacturing and computing systems - preliminaries.

2. Standard notation a/b/g.

3. Complexity of the scheduling problems.

4. Single machine scheduling, criterion Cmax, Fw.

5. Single machine scheduling, criterion Lmax.

6. Parallel machine scheduling, criterion Cmax.

7. Identical processors, approximation algorithms, list scheduling

8. Parallel identical processors, precedence relations, preemption.

9. Unrelated processors, and preemptive scheduling.

10. Dedicated processors and flow shop scheduling.

11. Dedicated processors and job shop scheduling.

12. Periodic scheduling of applications based on fixed priority preemptive operating system.

13. Response time analysis.

14. Model checking by timed automata and temporal logic.

Syllabus of tutorials:

1. Scheduling - formulation of problems

2. Scheduling - Parallel processors (List scheduling)

3. Scheduling - Cyclic scheduling on parallel processors

4. Verification - introduction to UPPAAL

5. Verification - synchronization in UPPAAL

6. Last date to specify individual task assignment

7. Verification - advanced features in UPPAAL

8. Test

9. Consultation - processor/task/criterion or model/properties

10. Consultation - algorithm design or model construction

11. Consultation - algorithm implementation or model construction

12. Consultation - experiments

13. Submission of individual task

14. Credits

Study Objective:

Study materials:

1. Blazewicz, J., Ecker, K., Schmidt, G., Weglarz, J.: Scheduling in Computer and Manufacturing Systems, Springer- Verlag, Berlin (1993,1996)

2. Butazzo, G.C.: Hard Real-Time Computing Systems - Periodic Scheduling Algorithms and Applications, Kluwer, (1997)

3. Liu, J.W.S.: Real-Time Systems, Prentice Hall, (2000)

Note:

Further information:

No time-table has been prepared for this course

The course is a part of the following study plans:

• Cybernetics and Measurements - Control Engineering- structured studies (compulsory elective course)
• Cybernetics and Measurements - Artificial Intelligence- structured studies (compulsory elective course)
• Cybernetics and Measurements - Measurement and Instrumentation Systems- structured studies (compulsory elective course)
• Cybernetics and Measurements - Aeronautical Engineering and Control Systems- structured studies (compulsory elective course)