Scribd Logo
Upload

Welcome to Scribd!

  • 16 views

    Weqe

    Uploaded by

    Venkat Balaji
    This document discusses dynamic programming and its application to assembly line scheduling problems. It describes how assembly lines work with multiple stations to assemble products sequentially. The assembly line scheduling problem aims to determine the optimal station selection from two parallel assembly lines to minimize the total assembly time. Dynamic programming provides a recursive solution approach by breaking down the problem into subproblems and storing previously computed results in a table to avoid recomputing them.

    Copyright:

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

    Weqe

    Uploaded by

    Venkat Balaji
    16 views12 pages
    This document discusses dynamic programming and its application to assembly line scheduling problems. It describes how assembly lines work with multiple stations to assemble products sequentially. The assembly line scheduling problem aims to determine the optimal station selection from two parallel assembly lines to minimize the total assembly time. Dynamic programming provides a recursive solution approach by breaking down the problem into subproblems and storing previously computed results in a table to avoid recomputing them.

    Original Title

    weqe

    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 discusses dynamic programming and its application to assembly line scheduling problems. It describes how assembly lines work with multiple stations to assemble products sequentially. The assembly line scheduling problem aims to determine the optimal station selection from two parallel assembly lines to minimize the total assembly time. Dynamic programming provides a recursive solution approach by breaking down the problem into subproblems and storing previously computed results in a table to avoid recomputing them.

    Copyright:

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

    Weqe

    Uploaded by

    Venkat Balaji
    This document discusses dynamic programming and its application to assembly line scheduling problems. It describes how assembly lines work with multiple stations to assemble products sequentially. The assembly line scheduling problem aims to determine the optimal station selection from two parallel assembly lines to minimize the total assembly time. Dynamic programming provides a recursive solution approach by breaking down the problem into subproblems and storing previously computed results in a table to avoid recomputing them.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    You are on page 1of 12

    Dynamic Programming

    • Typically applied to optimization problems


    – characterize the structure of an optimal solution
    – recursively define the value of an optimal solution
    – compute optimal value in a bottom-up fashion
    – construct optimal solution steps from computed
    information (if more than the value is required)
    Assembly Line Scheduling
    • Manufacturing of large items like car, trucks etc. generally
    undergoes through multiple station, where each station is
    responsible for assembling particular part only. Entire
    product will be ready after it goes through predefined n
    stations in sequence.
    • For example, manufacturing of car may be done in several
    stages like engine fitting, coloring, light fitting, fixing of
    controlling system, gates, seats and many other things.
    • Particular task is carried out at the station dedicated for
    that task only. Based on requirement, there may be more
    than one assembly line.
    • In case of two assembly lines, if load at station j of
    assembly line 1 is very high, then components are
    transferred to station j of line 2, converse is also true. This
    helps to speed up the manufacturing process.
    Assembly Line Scheduling
    Problem
    • Determine which station should be selected
    from assembly line 1 and which to choose
    from assembly line 2 in order to minimize
    the total time to build the entire product.
    Assembly Line Scheduling
    • There are two “parallel” assembly lines
    – Each assembly line can perform any job
    – There is a cost to switch between assembly lines
    • For a special order item, what is the fastest route?
    • A brute force solution has complexity O(2n)
    •Terminologies are explained here :
    • Sij = Station j on assembly line i.
    • aij = Time needed to assemble the partial
    component at station j on assembly line i.
    • tij = Time required to transfer component
    from one assembly to other from station j to
    (j + 1).
    • ei = Entry time on assembly line i.
    • xi = Exit time from assembly line i.
    A Particular Example
    • For example
    • The cost of switching is shown between the
    assembly lines
    • What is the cost of the minimal solution?
    Optimal Substructure
    • An optimal solution to the entire problem
    depends on optimal solutions to subproblems
    • We formulate a solution for the assembly line
    problem stage-by-stage
    A Recursive Solution
    • After some manipulation, we find the following
    recurrence relation

    • Where fi[j] is the fastest possible time to Si,j


    ti,j is the transfer time from Si,j
    ai,j is the time at Si,j
    ei is the entry time for assembly line i
    • The same subproblems are solved again & again
    • Our improved strategy is to build a table to save
    previous results so that they don’t have to be
    recomputed each time
    The Fastest Way
    • J=1
    • F1[1]=2+7=9
    • F2[1]=4+8=12
    J=2
    F1[2]=min[9+9,12+2+9]
    =min[18,23]
    = 18
    L1[2]=1
    F2[2]=min[12+5,9+2+5]
    min[17,16] l2[2]=1
    =16
    Printing A Solution
    • Printing the solution

    • The values for our particular problem


    This printout is “in reverse”;
    How can the print routine be
    changed to get a printout from
    Station 1 to Station 6 ?

    You might also like