Python - Assembly Line Scheduling Problem

Python – Assembly Line Scheduling Problem

The Assembly Line Scheduling Problem is a classic dynamic programming challenge that involves determining the minimum time required to process a product through a series of stations on two assembly lines. Each line has its own processing times, and there are additional transfer times if you switch from one line to the other. This tutorial will explain the problem, provide sample inputs and outputs, outline the solution approach, and offer a complete Python program with detailed explanations for each example.

Problem Statement

Given two assembly lines with n stations each, you are provided with the following information:

Entry Times: e1 and e2 for lines 1 and 2 respectively.
Exit Times: x1 and x2 for lines 1 and 2 respectively.
Processing Times: Two arrays a1[0...n-1] and a2[0...n-1] where a1[i] and a2[i] represent the time taken at station i on lines 1 and 2.
Transfer Times: Two arrays t1[0...n-2] and t2[0...n-2] where t1[i] is the time required to move from station i on line 1 to station i+1 on line 2, and t2[i] is the time required to transfer from station i on line 2 to station i+1 on line 1.

The goal is to determine the minimum total time to process a product through all the stations, considering both the processing and transfer times.

Sample Input and Output

Example:

</>

Copy

# Sample Input:
e1 = 2
e2 = 4
a1 = [7, 9, 3, 4, 8, 4]
a2 = [8, 5, 6, 4, 5, 7]
t1 = [2, 3, 1, 3, 4]  # Transfer times from line 1 to line 2
t2 = [2, 1, 2, 2, 1]  # Transfer times from line 2 to line 1
x1 = 3
x2 = 2

# Expected Output:
38

Explanation: Using the provided input, the dynamic programming approach calculates the minimum time at each station on both lines. After processing all stations and adding the exit times, the minimum total processing time is determined to be 38 units.

Solution Approach

We solve the problem using an iterative dynamic programming strategy. The key idea is to compute two arrays:

Initialization:
- f1[0] = e1 + a1[0] (Time to process the first station on line 1)
- f2[0] = e2 + a2[0] (Time to process the first station on line 2)
Recurrence Relation: For each subsequent station i (from 1 to n-1):
- f1[i] = min( f1[i-1] + a1[i], f2[i-1] + t2[i-1] + a1[i] )
- f2[i] = min( f2[i-1] + a2[i], f1[i-1] + t1[i-1] + a2[i] )
Final Calculation:
- Final time = min(f1[n-1] + x1, f2[n-1] + x2)

This approach ensures that at every station, you choose the optimal path by comparing the cost of staying on the same assembly line versus switching to the other line.

Python Program

</>

Copy

def assembly_line_scheduling(e1, e2, a1, a2, t1, t2, x1, x2):
    """
    Compute the minimum time required to process a product through two assembly lines.
    
    Parameters:
    e1 (int): Entry time for line 1.
    e2 (int): Entry time for line 2.
    a1 (list): Processing times for each station on line 1.
    a2 (list): Processing times for each station on line 2.
    t1 (list): Transfer times from line 1 to line 2.
    t2 (list): Transfer times from line 2 to line 1.
    x1 (int): Exit time for line 1.
    x2 (int): Exit time for line 2.
    
    Returns:
    int: The minimum total processing time.
    """
    n = len(a1)
    
    # Initialize the time arrays for both assembly lines.
    f1 = [0] * n  # f1[i] stores the minimum time to reach station i on line 1.
    f2 = [0] * n  # f2[i] stores the minimum time to reach station i on line 2.
    
    # Base case: Processing the first station on each line.
    f1[0] = e1 + a1[0]
    f2[0] = e2 + a2[0]
    
    # Compute the minimum time for each station from 1 to n-1.
    for i in range(1, n):
        f1[i] = min(f1[i-1] + a1[i], f2[i-1] + t2[i-1] + a1[i])
        f2[i] = min(f2[i-1] + a2[i], f1[i-1] + t1[i-1] + a2[i])
    
    # Add the exit times and return the final minimum time.
    final_time = min(f1[n-1] + x1, f2[n-1] + x2)
    return final_time

# Test the function with the sample input.
e1 = 2
e2 = 4
a1 = [7, 9, 3, 4, 8, 4]
a2 = [8, 5, 6, 4, 5, 7]
t1 = [2, 3, 1, 3, 4]
t2 = [2, 1, 2, 2, 1]
x1 = 3
x2 = 2

result = assembly_line_scheduling(e1, e2, a1, a2, t1, t2, x1, x2)
print("Fastest time:", result)  # Expected Output: 38

Explanation: The program starts by initializing two lists, f1 and f2, to store the minimum time required to reach each station on lines 1 and 2, respectively. It then processes each station iteratively:

For station 0: The time is simply the entry time plus the processing time at the first station.
For subsequent stations: The program calculates the minimum time to reach the current station either by staying on the same line or by switching from the other line (which includes the transfer time).
Final Step: After processing all stations, the exit times are added, and the overall minimum is chosen as the final answer.

This dynamic programming approach guarantees an optimal solution with a time complexity of O(n).

Conclusion

The Assembly Line Scheduling Problem is an excellent example of how dynamic programming can be used to make optimal decisions in complex systems. By breaking the problem into smaller subproblems and using a bottom-up approach, we efficiently determine the minimum processing time. This tutorial provided a step-by-step explanation, sample input/output, and a complete Python implementation suitable for understanding the dynamic programming approach and preparing for technical interviews.

TutorialKart

Python – Assembly Line Scheduling Problem