How to solve the problem of assigning products to assembly lines

Question

I have been struggling with this problem from quite a while. Here's how it goes:

• There are N assembly lines having capacity C1, C2, ... CN.
• There are M products P1, P2, ... PM.
• Each product P is a set of Items {I1, I2, I3, ... Ik} which are finite.
• Products can share items.

We need to assign the products on the assembly lines such that following constraints are met:

1. Every product is assigned to exactly one of the lines.
2. Every line is able to accommodate all products assigned so that number of items on it never exceed it's capacity.

Some approaches I tried but didn't reach a satisfactory solution:

1. Started with pair of products with high Jaccard similarity assigned to each line and continued assigning more products on line.
2. Tried using LSH min hash to generate buckets of products with high similarity.

Both the approaches didn't generate a feasible solution. Meaning there were some products left at the end which would not fit on the assembly lines.

I'm only looking for a feasible solution (sub-optimal is fine) in this case and not the most optimised one.

Hoping someone give me more insights into solving this problem.

Answer 1

This problem can be formulated as an integer, linear program, and then solved with any commercial or public-domain ILP solver.

Givens

We are given the following:

• A : the number of assembly lines, indexed by a
• P : the number of products, indexed by p
• I : the number of items, indexed by i
• C_a : the maximum number of items that can be processed by assembly line a
• S_i : the set of products that use item i

The formulation of the ILP model is as follows.

Variables

We define the following variables.

x_pa equals 1 if product p is assigned to assembly line a, else 0, 1 ≤ p ≤ P, 1 ≤ a ≤ A

y_ai equals 1 if item i is processed on assembly line a, else 0, 1 ≤ a ≤ A, 1 ≤ i ≤ I

Constraints

The constraints are as follows:

Each product must be produced

∑_ax_pa = 1, 1 ≤ p ≤ P

Prevent production of a product on a given assembly line if it contains an item that is not permitted on that line

x_pa ≤ y_ai for each i in S_i, 1 ≤ a ≤ A, 1 ≤ i ≤ I

The capacity of each assembly line cannot be exceeded

∑_iy_ai ≤ C_a, for a = 1,...,A

Objective function

There is no objective function to be maximized or minimized as only a feasible solution is required. If the solver does require an objective function, something artificial could be used, such as

min 0x₁₁

---

Optimizing

Suppose now we wish to maximize or minimize some function, not just identify a feasible solution.

As an example, suppose it costs c_a to operate assembly line a and we now want to determine which assembly lines to open to minimize cost. We could do that as follows.

We define the following additional variables.

z_a equals 1 if assembly line is to operate, else 0, 1 ≤ a ≤ A

The revised formulation follows.

min ∑_ac_az_a

subject to:

∑_ax_pa = 1, 1 ≤ p ≤ P

x_pa ≤ y_ai for each i in S_i, 1 ≤ a ≤ A, 1 ≤ i ≤ I

∑_iy_ai - C_az_a ≤ 0, for a = 1,...,A

Answer 2

I was able to solve this problem. I used Python pulp library to solve this.

We need to define following binary variables:
x[i, j] = true, if product i is placed on line j
y[j, k] = true, if item k is placed on line j

Constraints: 
1. Σ y[j, k] <= Cj, where Cj is the capacity of the line j
2. Σ x[i, j] = 1, a product can be assigned to only one line.
3. y[j, k] >= x[i, j], set y[j, k] = true for line j if product x[i, j] = true for line j.

Code:

    from pulp import *
    
    def solve_assembly_line_assignment(capacities, products):
        M = len(products)
        N = len(capacities)
        all_items = set()
        for prod in products:
            all_items = all_items.union(prod)
        K = len(all_items)
    
        # Create a binary variable x[i][j] representing whether product i is assigned to assembly line j
        x = LpVariable.dicts("Product", [(i, j) for i in range(1, M + 1) for j in range(1, N + 1)], 0, 1, LpBinary)
    
        # Create a binary variable y[i][k] representing whether item k is used on assembly line j
        y = LpVariable.dicts("Item", [(j, k) for j in range(1, N + 1) for k in range(1, K + 1)], 0, 1, LpBinary)
    
        # Create the LP problem
        prob = LpProblem("Assembly_Line_Assignment", LpMaximize)
    
        # Objective function: maximize the total assignment value
        # This function is not necessary, as total sum of all products on all lines = total sum of all products in this case.
        prob += lpSum(x[i, j] for i in range(1, M + 1) for j in range(1, N + 1)), "Total_Assignment_Value"
    
        # Constraints: each product is assigned to exactly one assembly line
        for i in range(1, M + 1):
            prob += lpSum(x[i, j] for j in range(1, N + 1)) == 1, f"Product_Assignment_{i}"
    
        # Constraints: assembly line capacity
        for j in range(1, N + 1):
            prob += lpSum(y[j, k] for k in range(1, K + 1)) <= capacities[j - 1], f"Assembly_Line_Capacity_{j}"
    
        # Constraints: link y and x variables
        for i in range(1, M + 1):
            for j in range(1, N + 1):
                for k in range(1, K + 1):
                    # This constraint ensures that when x[i, j] assumes value 1 then it's item also does so.
                    # This helps in checking previous constraint of capacity without double counting.
                    if k in products[i-1]:
                        prob += y[j, k] >= x[i, j], f"Link_{i}_{k}_{j}"
    
        prob.writeLP("assembly_line_model.lp")
    
        # Solve the problem
        prob.solve()
    
        # Print the results
        print(f"Products: {products}")
        print(f"Lines: {capacities}")
        print("Status:", LpStatus[prob.status])
        print("Optimal Assignment:")
        for i in range(1, M + 1):
            for j in range(1, N + 1):
                if value(x[i, j]) == 1:
                    print(f"Product {i} is assigned to Assembly Line {j}")

Example usage:

capacities = [3, 4, 4]  # Capacities of assembly lines
products = [{1, 2, 3}, {2, 3, 4}, {1, 3, 5}, {4, 5}, {1, 2, 4, 5}]  # Products as sets of items
solve_assembly_line_assignment(capacities, products)

Result:

Optimal Assignment:
Product 1 is assigned to Assembly Line 3
Product 2 is assigned to Assembly Line 3
Product 3 is assigned to Assembly Line 1
Product 4 is assigned to Assembly Line 2
Product 5 is assigned to Assembly Line 2