Computer Science – Discrete Mathematics
Scientific paper
2011-11-03
Computer Science
Discrete Mathematics
16 pages
Scientific paper
Assembly line balancing is a well-known problem in operations research. It consists in finding an assignment of tasks to some arrangement of stations where the tasks are executed. Typical objective functions require to minimize the cycle time for a given number of stations or the number of stations for a given cycle time. Common to all variants of assembly line balancing are the precedence constraints among the tasks. Different inequalities for modeling these constraints have been proposed in the literature and lead to different formulations for problems such as the simple assembly line balancing problem (SALBP). We theoretically compare these formulations in terms of the strength of their linear relaxations. Moreover, we propose two new families of inequalities and a stronger formulation of the station limits for the SALBP and show that one of the resulting formulations dominates all existing ones. We evaluate the efficiency of these formulations experimentally and show that the proposed formulation produces equal or better results than existing formulations.
Costa Alysson M.
Ritt Marcus
No associations
LandOfFree
A comparison of formulations for the simple assembly line balancing problem does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with A comparison of formulations for the simple assembly line balancing problem, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A comparison of formulations for the simple assembly line balancing problem will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-703413