Final published version
Research output: Contribution to Journal/Magazine › Journal article › peer-review
Research output: Contribution to Journal/Magazine › Journal article › peer-review
}
TY - JOUR
T1 - Robust balancing of transfer lines with blocks of uncertain parallel tasks under fixed cycle time and space restrictions
AU - Pirogov, Aleksandr
AU - Gurevsky, Evgeny
AU - Rossi, Andre
AU - Dolgui, Alexandre
PY - 2021/5/1
Y1 - 2021/5/1
N2 - This paper deals with an optimization problem, which arises when a new transfer line has to be designed subject to a limited number of available machines, cycle time constraint, and precedence relations between necessary production tasks. The studied problem consists in assigning a given set of tasks to blocks and then blocks to machines so as to find the most robust line configuration under task processing time uncertainty. The robustness of a given line configuration is measured via its stability radius, i.e., as the maximal amplitude of deviations from the nominal value of the processing time of uncertain tasks that do not violate the solution admissibility. In this work, for considering different hypotheses on uncertainty, the stability radius is based upon the Manhattan and Chebyshev norms. For each norm, the problem is proven to be strongly NP-hard and a mixed-integer linear program (MILP) is proposed for addressing it. To accelerate the seeking of optimal solutions, two variants of a heuristic method as well as several reduction rules are devised for the corresponding MILP. Computational results are reported on a collection of instances derived from classic benchmark data used in the literature for the Transfer Line Balancing Problem.
AB - This paper deals with an optimization problem, which arises when a new transfer line has to be designed subject to a limited number of available machines, cycle time constraint, and precedence relations between necessary production tasks. The studied problem consists in assigning a given set of tasks to blocks and then blocks to machines so as to find the most robust line configuration under task processing time uncertainty. The robustness of a given line configuration is measured via its stability radius, i.e., as the maximal amplitude of deviations from the nominal value of the processing time of uncertain tasks that do not violate the solution admissibility. In this work, for considering different hypotheses on uncertainty, the stability radius is based upon the Manhattan and Chebyshev norms. For each norm, the problem is proven to be strongly NP-hard and a mixed-integer linear program (MILP) is proposed for addressing it. To accelerate the seeking of optimal solutions, two variants of a heuristic method as well as several reduction rules are devised for the corresponding MILP. Computational results are reported on a collection of instances derived from classic benchmark data used in the literature for the Transfer Line Balancing Problem.
KW - Manufacturing
KW - Transfer line
KW - Balancing
KW - Stability radius
KW - Robustness
KW - Uncertainty
KW - Robust optimization
KW - MILP
KW - Heuristics
KW - Pre-processing
U2 - 10.1016/j.ejor.2020.08.038
DO - 10.1016/j.ejor.2020.08.038
M3 - Journal article
VL - 290
SP - 946
EP - 955
JO - European Journal of Operational Research
JF - European Journal of Operational Research
SN - 0377-2217
IS - 3
ER -