Scribd Logo
Upload

Welcome to Scribd!

  • 12 views

    Exam 130123

    Uploaded by

    Sou Tibon
    Exam Ordo

    Copyright:

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

    Exam 130123

    Uploaded by

    Sou Tibon
    12 views2 pages
    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?

    Exam Ordo

    Copyright:

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

    Exam 130123

    Uploaded by

    Sou Tibon
    Exam Ordo

    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,

    January 23, 2013, 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 problem 1|rj |Lmax of minimizing maximum lateness on a single
    machine under release dates. In particular consider the instance given by

    jobs j 1 2 3 4 5 6 7
    pj 6 18 12 10 10 17 16
    rj 0 0 0 14 25 25 50
    dj 8 33 44 24 90 85 68

    (a) Formulate and apply the preemptive EDD rule. Compute the optimal preemptive sched-
    ule, and list the results in a table with the following entries:

    jobs j 1 2 3 4 5 6 7
    CjpEDD
    dj 8 33 44 24 90 85 68
    pEDD
    Lj

    (b) Prove optimality of your schedule by pointing out the correct critical job subset.

    Question 2. Consider a problem with m uniform machines, with speeds s1 ≥ s2 ≥ . . . ≥


    sm > 0. We have n tasks that may be preempted. The jobs have processing requirements pj
    with p1 ≥ p2 ≥ . . . ≥ pn > 0, for j = 1, . . . , n. That means that if a machine i is to process
    p
    the whole job j, it will take sji time units. We are interested in minimizing the makespan.

    (a) Argue that if, for instance I, a schedule of length ` exists, then, for any integer k,
    0 < k < min{m, n}, there is also a schedule of length ` or less for the instance Ik ,
    defined by considering only the k first machines, and the k first tasks. Use the result
    OPT (I).
    on Ik to express a lower bound LBk (I) on Cmax

    (b) Argue that if a schedule of length ` exists, then


    Pn
    j=1 pj
    ` ≥ max{ Pm , max LBk }
    i=1 si k

    (c) For the following instance on 5 machines and 7 jobs compute the (highest) lower bound
    and find a schedule of the corresponding length. Machine speeds are: s1 = 5, s2 = 4,
    s3 = 3, s4 = 2 and s5 = 1; job requirements are p1 = 470, p2 = 390, p3 = 340, p4 = 160,
    p5 = 60, p6 = 40 and p7 = 20.

    1
    Question 3. Consider the problem (P ): O5||Cmax of minimizing maximum completion time
    on a set of five identical machines. In particular consider the instance I on 6 jobs where
    process requirements are given by

    jobs j 1 2 3 4 5 6
    p1j 1 0 1 0 1 2
    p2j 1 1 2 0 2 0
    p3j 2 1 1 1 1 0
    p4j 1 2 1 2 0 0
    p5j 1 1 0 1 0 2

    We further consider the problem (Q): O5|pmtn|Cmax of minimizing maximum completion


    time on a set of five identical machines, where we allow operations to be preempted.
    Let P (I 0 ) and Q(I 0 ) denote the optimal solution values of the two problems, defined on
    the same instance I 0 .

    (a) How do the values P (I 0 ) and Q(I 0 ) relate, for general instances I 0 ? Justify your claim.

    (b) For the general case I 0 , and for the particular instance I defined above, give a non-trivial
    lower bound on the solution values Q(I 0 ) and Q(I).

    (c) Does there exist a solution of Q with a matching value? If so, compute such a schedule.

    (d) If we would consider instances I” of the open shop problem defined on TWO machines,
    for example on the instance given by

    jobs j 1 2 3 4 5 6
    p1j 4 1 3 1 3 2
    p2j 2 4 2 3 1 2

    what is then the relation between P (I”) and Q(I”), where P and Q refer to the non-
    preemptive and the preemptive version, respectively? Substantiate your answer.

    Question 4.
    Consider the use of the LPT-rule for solving the problem of minimizing makespan on m
    parallel identical machines processing n jobs. We observe the following

    LEMMA: for any instance I of P ||Cmax : if there exists an optimal schedule with at most
    two operations per machine, then LPT when applied on I yields a schedule that has optimal
    length.

    You do not have to prove this lemma!! Give the worst case ratio between the makespans
    LPT (I)
    Cmax OPT (I) in terms of m and prove that ratio making use of the above Lemma.
    and Cmax

    You might also like