An alternative MILP model for makespan minimization on assembly lines

Abstract

The Simple Assembly Line Balancing Problem-2 (SABLP-2) is defined as partitioning the tasks among stations in order to minimize the cycle time given the number of stations. SALBP-2 reduces to the identical parallel machine scheduling problem with makespan minimization (P<inf>m</inf>‖ C<inf>m</inf> <inf>a</inf> <inf>x</inf>) when precedence relations are ignored providing a lower bound. In a certain layout setting tasks revisiting the same station over consecutive tours might be preferable when the sole objective is to minimize the makespan of producing the order quantity. In this study the tradeoff between the makespans obtained from SALBP-2 and (P<inf>m</inf>‖ C<inf>m</inf> <inf>a</inf> <inf>x</inf>) as a function of order quantity is analyzed. A piecewise linear concave makespan function is observed. We developed an alternative model formulation and an iterative solution scheme for makespan minimization for all possible order quantities. The results of our computational experiment indicate that SALBP-2 outperforms for small order quantities whereas (P<inf>m</inf>‖ C<inf>m</inf> <inf>a</inf> <inf>x</inf>) yields the best results for larger order quantities. However there is a certain range of order quantity for which the proposed model dominates the other two. Our results are validated in benchmark instances. © 2017 Elsevier B.V. All rights reserved.