How do I model a precedence constraint?

Question

How do I model a precedence constraint of 12 tasks distributed among 4 work stations in order to balance the line to obtain the shortest possible cycle time?

#Number of tasks
N = 12
#Number of workstations
W = 4

#D[i] duration of task i
D = [3,6,7,6,4,8,9,11,2,13,4,3]

# Precedence (arcs on the precedence graph)
A = [(1,2),(1,3),
    (2,4),(2,5),(2,6),
    (3,6),(3,7),
    (4,9),
    (5,9),
    (6,8),
    (7,11),
    (11,10), 
    (8,9),(8,10),
    (9,12),
    (10,12)]

Variables:
Xik ={1, if task i = 1,...,N is assigned to station k=1,...,W
0, otherwise
Yik = beginning of task i = 1,...,N on station k =1,...,W
Ej = time at which operations in station k = 1,...,W end

Answer 1

Ok just in general:
Any preceding relation or constraint is modelled as:
$x_{i,k} \le x_{j,k} \ \ \forall j \in\ S_i$ where $S_i=$ set of precedence tasks or whatever for $i$.
Now you have to also ensure once all preceding jobs are assigned $x$ for job $i$ should be assigned. You do that by:
$\sum_{j\in\ S_i} \sum_k x_{j,k} - \vert S_i \vert +1 \le \sum_k x_{i,k} \ \ \forall i$.

There's another constraint to ensure a task $i$ is assigned to just 1 workstation.

Also your starting time $y_i$ is max of start+duration of other preceding jobs.
$y_i \ge (y_j+D_j) \ \ \forall j \in\ S_i \ \ \forall i$

And then you have to link
$\sum_k x_{i,k}\le y_i \le M \sum_k x_{i,k} \ \ \forall i$

Now think duration of which task or workstation will you minimize to optimize the cycle time? Or should you maximize the production rate?

Answer 2

Noted that separate from whether we can solve such a problem, some things should be considered. First, for an assembly line balancing two important factors are the line bottleneck and the required demand that comes from the customer side. The second would be how we can analyze the bottleneck station regarding being a tool/machine/etc. or a human-based station. I assume you analyzed that and now, the only thing is to solve the above problem.

There are many ways to solve an assembly line problem and also its variants. Some cases are:

• A simple random assignment, that almost yields a sub-optimal solution.
• Ranked Positional Weights, which is a well-known heuristic to solve SALBP. Also, a python implementation could be found here.
• COMSOAL algorithm is another very good heuristic to solve SALBPs.
• Mixed-integer linear programming.

The solution for the above problem by using $3$rd and the $4$th mentioned techniques are as follows:

• The $3$rd

As shown in the above results, the assembly line cycle time would be around $20$ mins. Also, from a mathematical point of view, this problem can be formulated as a bin-packing problem by adding the precedence constraint:

• The $4$th $$ \sum_{s \in Station} s x_{i,s} \leq \sum_{s \in Station} s x_{j,s} \quad \forall (i,j) \in PrecedenceTasks $$

Also, The results of the MIP with the objective value equal to $20$ mins would be:

VARIABLE x[i,s]  assignment

          station1    station2    station3    station4

item1        1.000
item2        1.000
item3        1.000
item4                                1.000
item5        1.000
item6                    1.000
item7                                1.000
item8                    1.000
item9                                1.000
item10                                           1.000
item11                                           1.000
item12                                           1.000
 

You can see the result of both methods are very similar. For more details on SALBP please, see this link.