Integer and constraint programming models for the straight and U-shaped assembly line balancing with hierarchical worker assignment problem

ABSTRACT

The solution to the assembly line balancing with the hierarchical worker assignment problem (ALBHWP) provides the optimal allocation of workers and tasks to the stations that minimise the total worker cost. In the ALBHWP, tasks differ in terms of the qualification requirements of workers, and the qualification levels of workers are hierarchical. In the hierarchical workforce structure, a lower qualified worker can be replaced by higher qualified ones with higher costs, while the vice versa is not applicable. This problem has only been studied for straight assembly lines so far. In this paper, we introduce the ALBHWP for U-shaped assembly lines. We developed integer and constraint programming models for solving the ALBHWP and compared their effectiveness using an extensive set of benchmark instances. We solved the ALBHWP for straight and U-shaped assembly lines comparatively. Constraint programming models have been statistically proven to provide better quality solutions faster than integer programming models. Besides, the CP model outperforms the only available metaheuristic in the literature for the S-ALBHWP in almost all problem sizes. Another observation is that a U-shaped line design is more cost-effective than a straight line design, but solving the ALBHWP for U-shaped lines is more difficult regarding computational complexity.

KEYWORDS:

• U-shaped assembly line balancing problem
• straight assembly line
• hierarchical workforce
• integer linear programming
• constraint programming

Disclosure statement

No potential conflict of interest was reported by the author(s).

Data availability statement

All models, and solution results are available on Mendeley Data at https://data.mendeley.com/datasets/ktzy3r6k6r.

Additional information

Notes on contributors

Eyüp Ensar Işık

Eyüp Ensar Işık is a research assistant at Yildiz Technical University, Department of Industrial Engineering, Türkiye. He has received his Master’s degree in Industrial Engineering from Dokuz Eylul University, and he is currently a PhD candidate at Boğaziçi University, Department of Industrial Engineering. His main research interest is using Operations Research techniques like mathematical programming, constraint programming, large-scale optimisation methods, and metaheuristics to solve complex combinatorial optimisation problems such as scheduling, timetabling, lot-sizing, assembly line balancing, etc … 

Seyda Topaloglu Yildiz

Seyda Topaloglu Yildiz is Professor of Industrial Engineering at Dokuz Eylul University (DEU), Türkiye. She received her Master and Ph.D.degrees in Industrial Engineering from DEU. Her research interests include mathematical modelling, constraint programming, metaheuristics, and their applications mainly on scheduling, assembly line balancing, and vehicle routing problems.