Constraint programming for solving various assembly line balancing problems
| Autor: | Tal Raviv, Yossi Bukchin |
|---|---|
| Rok vydání: | 2018 |
| Předmět: |
Mathematical optimization
021103 operations research Information Systems and Management Selection (relational algebra) Modeling language Strategy and Management 0211 other engineering and technologies 02 engineering and technology Management Science and Operations Research Solver Set (abstract data type) Task (computing) Simple (abstract algebra) 0202 electrical engineering electronic engineering information engineering Constraint programming 020201 artificial intelligence & image processing Algorithm Integer programming Mathematics |
| Zdroj: | Omega. 78:57-68 |
| ISSN: | 0305-0483 |
| DOI: | 10.1016/j.omega.2017.06.008 |
| Popis: | In this paper, the constraint programming (CP) approach is applied for the simple assembly line balancing problem (SALBP) as well as some of its generalizations. CP is a rich modeling language that enables the formulation of general combinatorial problems and is coupled with a strong set of solution methods that are available through general purpose solvers. The proposed formulations are conversions of well-known mixed integer programming (MILP) formulations to CP, along with a new set of constraints that helps the CP solver to converge faster. As a generic solution method, we compare its performance with the best known generic MILP formulations and show that it consistently outperforms MILP for medium to large problem instances. A comparison with SALOME, a well-known custom-made algorithm for solving the SALBP-1, shows that both approaches are capable of efficiently solving problems with up to 100 tasks. When 1000-task problems are concerned, SALOME provides better performance; however, CP can provide relatively good close to optimal solutions for multiple combinations of problem parameters. Finally, the generality of the CP approach is demonstrated by some adaptations of the proposed formulation to other variants of the assembly line balancing problem including the U-shaped assembly line balancing problem and the task assignment and equipment selection problem. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect