Deterministic Scheduling
              Dr in
. Krzysztof Giaro
            Gdask University of Technology
                          Lecture Plan
        Introduction to deterministic scheduling
        Critical path metod
        Some discrete optimization problems
        Scheduling to minimize C
                             max
        Scheduling to minimize ΣCi
        Scheduling to minimize L
                             max
        Scheduling to minimize number of tardy tasks
        Scheduling on dedicated processors
        Introduction to Deterministic Scheduling
    Our  aim  is  to  schedule  the  given  set  of  tasks  (programs  etc.)  on
    machines (or processors).
    We have  to  construct  a  schedule  that  fulfils  given  constraints  and
    minimizes optimality criterion (objective function).
    Deterministic model: all the parameters of the system and of the tasks
    are known in advance.
    Genesis and practical motivations:
    • scheduling manufacturing processes,
    • project planning,
    • school or conference timetabling,
    • scheduling tasks in multitask operating systems,
    • distributed computing.
                   Introduction to Deterministic Scheduling
           Example 1. Five tasks with processing times p ,...,p =6,9,4,1,4 have to be
                                                              1    5
           scheduled on three processors to minimize schedule length.
                                M
                                 1             J 2
                                M
                                 2         J 1       J 4
                                M       J
                                 3       3          J 5
                                                              9
                        Graphical representation of a schedule - Gantt chart
           Why the above schedule is feasible?
           General constriants in classical scheduling theory:
           • each task is processed by at most one processor at a time,
           • each processor is capable of processing at most one task at a time,
           • other constraints - to be discussed ...