Integer based formulation for the simple assembly line balancing problem with multiple identical tasks

- A new MILP formulation for SALBP with repetitive tasks is presented.
- Identical tasks are grouped in a proposed compact precedence diagram.
- Allocation decisions are taken by integer variables rather than binary ones.
- Universal solver with proposed formulation was competitive to a dedicated algorithm.
- Instances based on real welding assembly lines were created and solved.

Assembly lines, especially those with welding procedures, can present several tasks with the same properties. These tasks can be treated as tasks with replicas, simplifying the problem. A Mixed Integer Linear Programming model is presented for the Simple Assembly Line Balancing Problem with Multiple Identical Tasks (or Repeated Tasks). Integer variables were used to define the number of identical tasks performed in each station. Along with variable reduction rules, the compact formulation presents only a fraction of the variables of equivalent binary models when several repeated tasks are present. Three instances inspired in real assembly lines and adapted benchmark problems with repeated tasks are used to compare the formulations. Using a universal solver, the integer formulation outperformed the binary formulation for the vast majority of instances and achieved competitive results in relation to the efficient procedure SALOME-2 (a dedicated algorithm based on branch-and-bound for Simple Assembly Line Balancing Problem). Grouping identical tasks proved to simplify the problem, allowing the procedure to solve larger instances.