# How do I model a precedence constraint?

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 = [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

• I think you have at least one typographical error: "Ej = time at which operations in station k ..."
– prubin
Jan 7 at 23:46
• Ek = time at which operations in station k=1,...W end Jan 8 at 0:28
• Cross-posted: here. Jan 8 at 14:07

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?

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.

• Thanks Abbas. It was probably a HW question, otherwise MS Project would do this. Other methods are like schedule the longest task and it's predessesors first and move from there. Jan 8 at 15:12
• @Sutanu, your welcome. 🙏. In the answer I tried to describe a bit around the subject and introducing some of the essential tools to solve such a problem hopefully they will be useful for others that are interested in. Jan 8 at 16:04
• Also, I dopt Ms project can be the right tool to schedule an assembly line. It uses the CPM algorithm to estimate the last task finish time and one can invoke critical pass duration, namely the longest path in the graph, by that. It never has any capabilities to optimize cycle time or something like that. This is why developed special software with customized algorithms to solve these kinds of problems efficiently. Jan 8 at 16:13
• Thank you Sir for the detailed elaboration. Also, I would like to know how to model a constraint of the assembly line where every workstation deals with a single operation at a time. Would I create more variables? Jan 9 at 19:08
• @user11048, I referred you to the bin packing problem. Do you see that? You do not need to introduce any new variable. Only two bin pack constraints. Also, if the answer is what you were looking for, please, accept that. :) Jan 10 at 9:39