Scribd Logo
Upload

Welcome to Scribd!

  • 12 views

    Exam 140409

    Uploaded by

    Sou Tibon
    This document contains a test with four questions on scheduling problems. Question 1 considers Lawler's algorithm and precedence constraints. Question 2 deals with minimizing maximum lateness on a single machine with release dates. Question 3 covers minimizing late jobs on parallel machines using dynamic programming. Question 4 is about scheduling jobs with subtasks on parallel machines.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd

    Exam 140409

    Uploaded by

    Sou Tibon
    12 views2 pages
    This document contains a test with four questions on scheduling problems. Question 1 considers Lawler's algorithm and precedence constraints. Question 2 deals with minimizing maximum lateness on a single machine with release dates. Question 3 covers minimizing late jobs on parallel machines using dynamic programming. Question 4 is about scheduling jobs with subtasks on parallel machines.

    Original Description:

    Exam Ordo

    Copyright

    © © All Rights Reserved

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    This document contains a test with four questions on scheduling problems. Question 1 considers Lawler's algorithm and precedence constraints. Question 2 deals with minimizing maximum lateness on a single machine with release dates. Question 3 covers minimizing late jobs on parallel machines using dynamic programming. Question 4 is about scheduling jobs with subtasks on parallel machines.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    12 views2 pages

    Exam 140409

    Uploaded by

    Sou Tibon
    This document contains a test with four questions on scheduling problems. Question 1 considers Lawler's algorithm and precedence constraints. Question 2 deals with minimizing maximum lateness on a single machine with release dates. Question 3 covers minimizing late jobs on parallel machines using dynamic programming. Question 4 is about scheduling jobs with subtasks on parallel machines.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    of 2

    Exam Sequencing and scheduling, 2P450,

    April 9, 2014, 14:00-17:00

    This test contains four questions on two pages, with 10 sub-items, for which a total of
    50 points can be scored. Each good answer scores 5 points. The final grade is obtained
    by dividing the amount of points by five. Questions may be answered in English and/or in
    Dutch. Please explain your answers. You are NOT allowed to use the handouts distributed
    in class/or on the web.

    Question 1. Consider the use of Lawler’s algorithm for solving the problem of minimizing
    the maximum cost maxj fj (Cj ) of jobs j scheduled on a single machine.

    (a) State the condition on the functions fj : R+ → R, under which Lawler’s rule applies,
    and state the algorithm.

    (b) Consider the special case in which the functions are given by fj (Cj ) := Cj − dj , for
    j ∈ J , and where there exist precedence relations between the jobs. Explain which
    preprocessing steps are needed to find the optimal schedule with a simple rule.

    Question 2. Consider the problem 1|rj |Lmax of minimizing maximum lateness of jobs sched-
    uled on a single machine under release dates. In particular consider the instance given by

    jobs j 1 2 3 4 5 6 7
    pj 8 18 12 10 10 17 16
    rj 0 11 23 29 40 45 70
    dj 0 18 13 37 34 78 65

    (a) Formulate and apply an appropriate rule ρ for solving the PREEMPTIVE case. Com-
    pute the optimal preemptive schedule for the instance given above, and list the results
    in a table with the following entries:

    jobs j 1 2 3 4 5 6 7
    Cjρ
    Lρj

    (b) Verify optimality of the preemptive schedule by providing a compact proof of optimality
    in the form of a subset S ⊆ J , for which minj∈S rj + p(S) − maxj∈S dj = Lρmax . Explain
    how you found this set S.

    (c) State, for this particular instance, an optimal non-preemptive schedule and give an
    (ad-hoc) reasoning why it should be optimal.

    1
    P
    Question 3. Consider the problem (2|| j Uj ) of minimizing the number of late jobs, on
    TWO parallel identical machines.

    (a) Describe for the general case, how to find the optimal solution, by the use of Dynamic
    Programming. HINT: sort jobs by increasing due date and define M (i, s, t) to be the
    maximum number of on time jobs j with 1 ≤ j ≤ i, with machine load s on machine
    1 and machine load t on machine 2; express the correct recursive relations and clarify
    what you compute to get to the optimal solution.

    (b) In particular we may consider the instance given by the following parameters

    jobs j 1 2 3 4 5 6 7
    pj 6 8 5 7 9 5 10
    dj 8 10 13 14 17 19 23

    Apply the method described in (a) to find the optimal schedule for this instance.

    (c) If the number of machines is equal to ONE, what would then be an easy rule for the
    general case, and what would be the optimal schedule for the instance with the same
    jobs.

    Question 4. Consider the problem of scheduling n jobs on m machines, where each job
    consists of m subtasks, and where for each job j its i-th sub-task has to be processed on
    machine i. Here the processing time required is pij . We consider as objective function
    maxj Cmj , where Cmj denotes the completion time of the last subtask of job j (hence on
    machine m).

    (a) Prove that there exists an optimal schedule in which the jobs are processed on machine
    2 in the same order as on machine 1.

    (b) For the TWO machine case, describe how an optimal schedule can be found in order of
    n log n time.

    You might also like