Variable Sets Reduction for Assembly Line Balancing Problem: MILP Model and Case Studies

Line balancing problems consist on assigning tasks to stations and/or workers in a restricted way. Most models deal with simple versions of this problem not taking into account real world restrictions. In this paper we present a new re-balancing model that takes into account assignment restrictions and builds the variable sets in a more efficient way. The model also takes into consideration worker displacement for problems with fewer workers than stations. To measure how constrained a line is in terms of task-stations allocations possibilities, two coefficients are proposed. The model was tested with variations of thee-hundred literature problems, each variation with a different degree of assignment restrictions. The elimination of allocation possibilities, a consequence of real world restrictions, leads to a reduction on processing time. The reduction of the variable sets might be of use for both exact and heuristic algorithms.