Scheduling in Discrete Event Systems

Lecturer:

Tutor:

Supervisor:

Department of Control Engineering

Synopsis:

Classification and formulation of operation 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 heuristic methods. Single processor scheduling problems are solved with criterion of Cmax, Fw and Lmax criterion. 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.

Requirements:

Syllabus of lectures:

1. Scheduling problems in manufacturing - preliminaries

2. Standard notation a/b/g.

3. Complexity of the scheduling problems.

4. Classification and general principles of solution methods

5. Single machine scheduling, minimizing schedule length

6. Single machine scheduling, criterion Fw,

7. Single machine scheduling, criterion Lmax

8. Parallel machine scheduling, criterion Cmax

9. Identical prosessors, list scheduling

10. Uniform processors.

11. Unrelated processors, and preemptive scheduling.

12. Dedicated processors and flow shop scheduling.

13. Dedicated processors and open shop scheduling.

14. Dedicated processors and job shop scheduling.

Syllabus of tutorials:

1. Motivation examples of scheduling problems

2. Seminar task fomulation.

3. Scheduling problem formulation, individual project definition

4. Single machine scheduling problem solution, Cmax criterion

5. Single machine scheduling, Fw, Lmax criterion

6. Parallel machine scheduling problem solution, Cmax criterion

7. Parallel machine scheduling problem solution, Fw, Lmax

8. Flow-shop problem solution

9. Open-shop problem solution

10. Job-shop problem solution, part I

11. Job-shop problem solution, part II

12. Flexible flow-shop problem solution

13. Presentation and formulation of the seminar tasks I.

14. Presentation and formulation of the seminar tasks II.

Study Objective:

Study materials:

1. Blazewicz, J., Ecker, K., Schmidt, G., Weglarz, J. (1993), Scheduling in Computer and Manufacturing Systems, Springer-Verlag, Berlin. ISBN 0-387-55958-2

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)