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

摘要

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.