Exact solution approaches for the workload smoothing in assembly lines

Abstract

In this paper, the problem of minimizing the smoothness index for an assembly line given a fixed cycle time and the number of workstations is studied. This problem which is known as the workload smoothing line balancing problem (WSLBP) is a mixed-integer quadratic programming problem. Until recently, this problem has only been tackled using heuristic approaches. Recently, there have been some attempts to solve this problem exactly using mixed-integer linear programming (MILP). The MILP formulations, however, are not usually capable of solving large size problem instances. In this paper, the aim is to solve the WSLBP using mathematical programming formulations by using off-the-shelf solvers. Differently from the literature some non-MILP formulations are also considered for the problem. For this purpose, three MILP formulations, one from the literature, and two non-MILP formulations are compared. The two non-MILP formulations include a mixed-integer second order cone programming formulation and a constraint programming model. The superiority of the non-MILP formulations over the considered MILP formulations is experimentally shown.

Keywords

• Smoothness index
• Assembly line balancing
• Workload smoothing
• Mixed-integer linear programming
• Second order cone programming
• Constraint programming