Enumerations and stability analysis of feasible and optimal line balances for simple assembly lines

International audienceFor a simple assembly line, it is necessary to minimize a number of the workstations for processing a partially ordered set of the tasks V={1,2,…,n}V={1,2,…,n} within a fixed cycle time (such a problem is denoted as SALBP-1). A dual assembly line balancing problem denoted as SALBP-2 is to minimize a cycle time provided that a number of the workstations is fixed. An initial vector t=(t1,t2,…,tn)t=(t1,t2,…,tn) of the processing times of the tasks V is given for both problems SALBP-1 and SALBP-2. For a subset View the MathML sourceV∼⊆V of the manual tasks View the MathML sourcej∈V∼, the processing times tjtj may vary since operators may have different skills, levels of fatigue, experience, and motivation. For any automated task View the MathML sourcei∈V⧹V∼, the processing time titi cannot vary. We investigate a stability of an optimal line balance for the assembly line with respect to variations of the processing times of the manual tasks (a line balance is stable, if it is optimal for any sufficiently small variation of the processing times). We developed the enumerative algorithms for constructing feasible and stable optimal line balances for the problem SALBP-1 and those for the problem SALBP-2. Computational results for the stability of the assembly line balances showed that there are a lot of unstable optimal line balances for the tested benchmark assembly lines. The simulation for the benchmark assembly line showed that the stable optimal line balance considerably outperforms the unstable ones. The complexity analysis of the assembly line balancing problems with different partial orders given on the task set V has been developed